/*
 * [Collisions.java]
 *
 * Summary: Calculates expected collisions (two items with same hash).
 *
 * Copyright: (c) 2014-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 2014-04-21 initial version
 */
package com.mindprod.example;

import com.mindprod.common18.ST;

import static java.lang.System.*;

/**
 * Calculates expected collisions (two items with same hash).
 * <p/>
 * Based on work of Ran Huo
 * http://www.quora.com/Computer-Programming/How-can-I-calculate-the-expected-number-of-cache-hits
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.0 2014-04-21 initial version
 * @since 2014-04-21
 */
public class Collisions
    {
    /**
     * Calculates expected collisions (two items with same hash)
     * <p/>
     * presuming perfectly random distribution of hashes,
     * when hash has m possible values and n items calculated.
     * It takes 2 parms m and n on the command line.
     * m does not have to be a power of two.
     * 8-bit = 256 poss values
     * 16-bit = 65,536 poss values
     * 32-bit = 4,294,967,296 poss values
     * 64-bit = 18,446,744,073,709,551,616 values
     */
    public static void main( String[] args )
        {
        // strip out commas and underscores
        final double m = Double.parseDouble( ST.stripNaughtyCharacters( args[ 0 ], ",_" ) );
        final double n = Double.parseDouble( ST.stripNaughtyCharacters( args[ 1 ], ",_" ) );
        final double expectedCollisions = m - n * Math.pow( ( m - 1 ) / m, n );
        out.println( "m = " + m + " possible hash values" );
        out.println( "n = " + n + " items" );
        out.println( "expected collisions = " + expectedCollisions + " items" );
        }
    }