[Python] Seeking an Efficient Perfect Hashing Function integer keys running on a small MCU?

I am developing a CANopen slave stack on a 200 MHz microcontroller and require a highly efficient lookup method to match a 16-bit object index (e.g., 0x603d) with a table index where the objects are stored. The expected range for used objects is between 200 and 400.

Although I considered using a perfect hashing function with a 16-bit table, the fill factor for this hash map would be only 400 / (2**16 - 1) * 100, or approximately 0.6%. I believe my challenge lies in finding a code generator for a perfect hashing function for 16-bit integers. I've explored options like MPHF, BBHash, gperf, and CMPH. Most of these either work primarily with strings or they offer O(1) lookup time but involve complex algorithms that are not suitable for my embedded application.

As an alternative, I experimented with a brute force technique using two different typical xor/shift hashing functions. By iterating over the seed, I search for a minimal collision ratio to then build an open addressing hash map table.

Here is a snippet of the Python code I used:

def hash32(key, seed):
h = seed
h ^= ((h << 7) ^ key * (h >> 3) ^ (~((h << 11) + (key ^ (h >> 5))))) & 0xFFFFFFFF
h = (~h + (h << 15)) & 0xFFFFFFFF
h ^= (h >> 11) & 0xFFFFFFFF
h = ((h + (h << 3)) + (h << 8)) & 0xFFFFFFFF
h ^= (h >> 13) & 0xFFFFFFFF
h = ((h + (h << 2)) + (h << 4)) & 0xFFFFFFFF
h ^= (h >> 17) & 0xFFFFFFFF
h = (h + (h << 15)) & 0xFFFFFFFF
return h

def fatou(key, seed=0):
return ((key ^ seed) * 0x45d9f3b) & 0xFFFFFFFF

# Some data
data = [4096, 4097, 4098, 4099, 5120, 5121, 5122, 5123, 5632, 5633, 5634, 5635,
6147, 8710, 8711, 8712, 4112, 4113, 8720, 8721, 8723, 16400, 16401, 4119,
4120, 4121, 8728, 8729, 16403, 16404, 16405, 16406, 8736, 8737, 8738, 8741,
4137, 9474, 25858, 9475, 24639, 24640, 24641, 24666, 16402, 24669, 24672,
24673, 24674, 24676, 24677, 24678, 24679, 24680, 24683, 24684, 24685, 24686,
24687, 24688, 24689, 24690, 24691, 24692, 24693, 24694, 24695, 24696, 24697,
24698, 24700, 24701, 24702, 24703, 24704, 20480, 24705, 24707, 24708, 24709,
20481, 24711, 24719, 24721, 24722, 24728, 24729, 24730, 24744, 24745, 24746,
24747, 6144, 24773, 6145, 24774, 6146, 6656, 6657, 6658, 6659, 24803, 24818,
24824, 24831, 8448, 8449, 8450, 8451, 8960, 8961, 8962, 8963, 9472, 8964,
9473, 8965, 8966, 9476, 9477, 8704, 8705, 8706, 8707, 9216, 8708, 9217,
9728, 9220, 9729, 9221, 8713, 9222, 9223, 9224, 8722, 12288, 26622]


def countCollisions(data, seed, map_size, hf):
""" Count collisions in a hash map for a given hash function and seed"""
max_collisions = 0
collisions = 0

m = [0] * map_size
for key in data:
m[hf(key, seed) % map_size] += 1

for i in range(map_size):
max_collisions = m if m > max_collisions else max_collisions
collisions += m - 1 if m > 1 else 0

return collisions, max_collisions


def findBestSeed(data, mapsize, hh):
""" Find the best seed for a given hash function and data"""
print("Finding best seed...")
m = len(data)
s = 0
for i in range(0xffff):
c, cc = countCollisions(data, i, mapsize, hh)
if c < m:
m = c
s = i
print(f" Found seed {s} with {m} collisions, worse case with a maximum of {cc} elements per bucket")
if c == 0:
break
return s, m


def buildOpenAdressingMap(data, seed, mapsize, hh):
""" Build an open addressing hash map for a given hash function and seed"""
d = [None] * mapsize
for key in data:
index = hh(key, seed) % mapsize
while d[index] is not None:
index += 1
d[index] = key
return d

fill_factor = 0.5
map_size = int(len(data) / fill_factor)
hfunc = fatou

seed, collisions = findBestSeed(data, map_size, hfunc)
print(f"Best seed {seed} with {collisions} collisions")
hm = buildOpenAdressingMap(data, seed, map_size, hfunc)


The output is:

Finding best seed...
Found seed 0 with 14 collisions, worse case with a maximum of 2 elements per bucket
Found seed 4 with 12 collisions, worse case with a maximum of 2 elements per bucket
Found seed 7 with 11 collisions, worse case with a maximum of 2 elements per bucket
Found seed 768 with 8 collisions, worse case with a maximum of 2 elements per bucket
Found seed 4316 with 7 collisions, worse case with a maximum of 2 elements per bucket
Found seed 16428 with 6 collisions, worse case with a maximum of 2 elements per bucket
Found seed 16430 with 4 collisions, worse case with a maximum of 2 elements per bucket
Found seed 16431 with 3 collisions, worse case with a maximum of 2 elements per bucket
Best seed 16431 with 3 collisions


Interestingly, the hash32 function is less efficient than the fatou function when translated into ARM 32-bit assembly, which consists of 19 instructions versus just 5 for fatou.

Given that even with a fill factor of 0.5, I still encounter three collisions, I am seeking a hashing function that could potentially achieve a 1.0 fill factor with zero collisions. Ideally, the hashing function should be executable in fewer than ten assembly instructions.

Fatou's assembly:

eors r0, r0, r1
movw r3, #40763
movt r3, 1117
mul r0, r3, r0
bx lr


This answer looks interesting, but I don't really understand how I can store data in my buckets. I tried to build something (with great help of ChatGPT) but it doesn't give me unique buckets indices.

import sys
import random
from collections import defaultdict


def generate_constants():
return random.randint(1, sys.maxsize), random.randint(1, sys.maxsize)


class HashTable:
def __init__(self, list_of_keys, retry_limit=10):
self.m = len(list_of_keys) # Define table size based on the number of keys
attempt = 0
while attempt < retry_limit:
self.C1, self.C2 = generate_constants()
self.graph, self.edges = self.create_graph(list_of_keys)
if not self.is_cyclic(self.graph):
self.setup_hash_table(self.edges)
return
attempt += 1
raise Exception("Failed to create an acyclic graph after several attempts.")

def setup_hash_table(self, edges):
table1 = [None] * self.m
table2 = [None] * self.m
for key, (index1, index2) in edges.items():
if table1[index1] is None and table2[index2] is None:
assign_value = random.randint(0, 100)
table1[index1] = assign_value
table2[index2] = key - assign_value
elif table1[index1] is not None:
table2[index2] = key - table1[index1]
elif table2[index2] is not None:
table1[index1] = key - table2[index2]
self.table1 = table1
self.table2 = table2


def h1(self, key):
return ((key * self.C1) + (self.C1 >> 5)) % self.m


def h2(self, key):
return ((key * self.C2) + (self.C2 >> 5)) % self.m


def __call__(self, key):
return self.table1[self.h1(key)] + self.table2[self.h2(key)]


def create_graph(self, list_of_keys):
graph = defaultdict(list)
edges = {}
for key in list_of_keys:
index1 = self.h1(key)
index2 = self.h2(key)
graph[index1].append(index2)
graph[index2].append(index1)
edges[key] = (index1, index2)
return graph, edges


def is_cyclic(self, graph):
visited = [False] * self.m
rec_stack = [False] * self.m

def dfs(node, parent):
visited[node] = True
rec_stack[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif rec_stack[neighbor] and neighbor != parent:
return True
rec_stack[node] = False
return False

for i in range(self.m):
if not visited:
if dfs(i, -1):
print("Cycle detected involving node", i)
return True
return False


keys = [4, 8, 15, 16, 23, 42]
hf = HashTable(keys)

for key in keys:
print(key, hf(key))


Is there a different approach, a parametric hashing function suitable for brute force exploration to achieve zero collisions and a 100% fill factor? What would you recommend for this application?

Continue reading...