calc_hash_collision_chance.py

import argparse
import math

if __name__ == "__main__":

    parser = argparse.ArgumentParser(
        description='Truncated hash collision calculator')
    parser.add_argument('--number-packages', type=float, default=1e6)
    parser.add_argument('--truncated-chars-length', type=float, default=16)
    args = parser.parse_args()

    # collision probability: https://stackoverflow.com/questions/51622061/how-can-i-calculate-the-impact-on-collision-probability-when-truncating-a-hash
    # https://preshing.com/20110504/hash-collision-probabilities/
    # chance of collision = 1 - e^(-n^2 / (2 * d))
    # d: 2^(bits_used_for_hash)
    # bits_used_for_hash: 4*truncated_chars_length
    # n: number_packages, number of hashes to check the probability for

    exp_num = -math.pow(args.number_packages, 2.0)
    exp_den = 2.0*math.pow(2.0, 4.0*args.truncated_chars_length)
    exp = math.exp(exp_num/exp_den)
    chance = 100.0*(1.0 - exp)

    print("Given k randomly generated values, where each value is a non-negative integer less than N,"
          "what is the probability that at least two of them are equal?")
    print("{} packages, {} hash characters length. Collision probability: {} %".format(
          args.number_packages, args.truncated_chars_length, chance))