main.py

def mk_hash(multiplier, shift, nr_buckets):
    def hash(n):
        h1 = (n * multiplier) >> (2 + shift)
        h2 = h1 >> shift
        return (h1 ^ h2) % nr_buckets

    return hash


def run_test(hash_fn, nr_buckets, stride):
    counts = [0 for _ in range(nr_buckets)]

    for b in [b * stride for b in range(1024 * 16)]:
        bucket = hash_fn(b)
        counts[bucket] += 1

    return counts


def main():
    strides = [2**n for n in range(12)]
    multipliers = [(2**32) - n for n in [5, 17, 65, 99, 107, 135, 153, 185, 209, 267]]
    shifts = [6]
    nr_buckets = [16, 32, 64]

    for m in multipliers:
        for s in strides:
            for shift in shifts:
                for nr in nr_buckets:
                    hash_fn = mk_hash(m, shift, nr)
                    counts = run_test(hash_fn, nr, s)

                    min_c = min(counts)
                    max_c = max(counts)
                    print(
                        f"{s}/{m}/{shift}/{nr}: {max_c - min_c} {int((max_c + min_c) / 2.0)}"
                    )


main()