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<<p) - 1
        c = Counter()
        for n in range(1<<p):
            g = hash_func(n, mask)
            for _ in range(call_count):
                c[next(g)] += 1
        freq = Counter()
        for v in c.values():
            if v > 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)