hash_collision.py

hash_collision.py

#!/usr/bin/env python3
import math
import sys

def main():
    if len(sys.argv) != 3:
        print(f"Usage: {sys.argv[0]} <num_items> <bits>")
        print("Example: ./hash_collision.py 1000000000 72")
        sys.exit(1)

    # Parse arguments
    num_items = int(sys.argv[1])
    bits = int(sys.argv[2])

    # Total number of hash values
    space_size = 2 ** bits

    # Birthday bound ratio
    ratio = 2 * space_size / (num_items ** 2)

    # Collision probability (approximation)
    prob_collision = 1 - math.exp(-1 / ratio)

    # Pretty print results
    print(f"Number of items (N):      {num_items:,}")
    print(f"Hash space size (2^{bits}): {space_size:,}")
    print(f"Ratio (2M / N^2):         {ratio:.6e}")
    print(f"Collision probability:    {prob_collision:.6%}")

if __name__ == "__main__":
    main()