from collections import Counter

PERTURB_SHIFT = 5
CUTOFF = 10

def print_collision_counts(hash_func):
    print("function %s" % hash_func)
    print("-"*30)
    for p in range(3, CUTOFF + 1):
        mask = (1<<p) - 1
        c = Counter()
        for n in range(1<<p):
            c[hash_func(n, mask)] += 1
        freq = Counter()
        for v in c.values():
            if v > 1:
                freq[v] += 1

        print("%d bits (dict_size = %d):" % (p, 1<<p) )
        if freq:
            for k in sorted(freq.keys(), reverse = True):
                print("there were %d times when %d different primary indexes resulted in the same 1st secondary indexes" % (freq[k], k))
        else:
            print("no collisions happened")
        print("-" * 15)

def previous_lookdict_perturb(hash_val, mask):
    i = hash_val
    perturb = hash_val

    i = mask & (i * 5 + perturb + 1)
    perturb >>= PERTURB_SHIFT
    return i

def py3_6_1_lookdict_perturb(hash_val, mask):
    i = hash_val
    perturb = hash_val

    perturb >>= PERTURB_SHIFT
    i = mask & (i*5 + perturb + 1)
    return i

def better_lookdict_perturb(hash_val, mask):
    i = hash_val
    perturb = hash_val

    i = mask & (i * 2 + perturb + 1)
    perturb >>= PERTURB_SHIFT
    return i

print_collision_counts(previous_lookdict_perturb)
print_collision_counts(py3_6_1_lookdict_perturb)
print_collision_counts(better_lookdict_perturb)