from collections import Counter CUTOFF = 20 def print_collision_counts(hash_func, call_count = 1): print("function %s called %d times" % (hash_func, call_count) ) print("-"*30) for p in range(8, CUTOFF + 1): mask = (1< 1: freq[v] += 1 print("%d bits:" % p) if freq: for k in sorted(freq.keys(), reverse = True): print("%d-collisions happened %d time(s)" % (k, freq[k])) else: print("no collisions happened") print("-" * 15) def previous_lookdict_perturb(hash_val, mask, PERTURB_SHIFT = 1): i = hash_val perturb = hash_val while True: i = mask & (i * 5 + perturb + 1) perturb >>= PERTURB_SHIFT yield i def py3_6_1_lookdict_perturb(hash_val, mask, PERTURB_SHIFT = 1): i = hash_val perturb = hash_val while True: perturb >>= PERTURB_SHIFT i = mask & (i*5 + perturb + 1) yield i def better_lookdict_perturb(hash_val, mask, PERTURB_SHIFT = 1): i = hash_val perturb = hash_val while True: i = mask & (i * 2 + perturb + 1) perturb >>= PERTURB_SHIFT yield i def even_better_lookdict_perturb(hash_val, mask, PERTURB_SHIFT=1): i = hash_val perturb = hash_val yield mask & (i * 2 + perturb + 1) while True: perturb >>= PERTURB_SHIFT i = mask & (i * 5 + perturb + 1) yield i print_collision_counts(previous_lookdict_perturb) print_collision_counts(py3_6_1_lookdict_perturb) print_collision_counts(better_lookdict_perturb) print_collision_counts(even_better_lookdict_perturb) print_collision_counts(previous_lookdict_perturb, 3) print_collision_counts(py3_6_1_lookdict_perturb, 3) print_collision_counts(better_lookdict_perturb, 3) print_collision_counts(even_better_lookdict_perturb, 3)