package collections.buckettest;

import java.util.ArrayList;
import java.util.List;

/**
 * Demonstrates the affect that hash code values
 * and initial capacity have on collisions in a HashMap.
 *
 * @author Thomas Rowland
 */
public class SimpleBucketTest {
  static Object[] buckets;    //array of buckets

  //-- Test data - key Objects
  static Integer[] keyvalues = {new Integer(0),
                                new Integer(1),
                                new Integer(2),
                                new Integer(7),
                                new Integer(15),
                                new Integer(16),
                                new Integer(17),
                                new Integer(31),
                                new Integer(32),
                                new Integer(33),
                                new Integer(47),
                                new Integer(48),
                                new Integer(49),
                                new Integer(62),
                                new Integer(63),
                                new Integer(64),
                                new Integer(101),
                                new Integer(102),
                                new Integer(103)};

  public static void main(String[] args) {
    // test for different initial capacity values
    runTest(20);
    runTest(33);
    runTest(65);
    runTest(129);
  }

  private static void runTest(int initialCapacity) {
    //-- Test initial capacity of array of buckets
    System.out.println(
        "\nSpecified Initial Capacity = " + initialCapacity);
    createArray(initialCapacity);
    System.out.println(
        "Real Initial Capacity = " + buckets.length);

    //-- Test index of each populated bucket
    List indices = new ArrayList();
    int collisionCount = 0;

    System.out.println("key " + "\thashcode " + "\tindex");
    for (int i = 0; i < keyvalues.length; i++) {
      Integer k = keyvalues[i];
      int h = k.hashCode();
      int modh = hash(k);
      int idx = indexFor(modh, buckets.length);
      if (indices.contains(new Integer(idx)))
        collisionCount++;   //collision
      indices.add(new Integer(idx));

      System.out.println(k + "\t" + h
                         + "\t\t" + idx);
    }
    System.out.println("Collisions: "
                       + collisionCount);
  }

  /**
   * Creates an array with a capacity
   * of a power of 2 >= initialCapacity
   */
  static void createArray(int initialCapacity) {
    int capacity = 1;
    while (capacity < initialCapacity) {
      capacity <<= 1;
    }
    buckets = new Object[capacity];
  }

  /**
   * Returns index for hash code h.
   */
  static int indexFor(int h, int length) {
    return (h & (length - 1));
  }

  /**
   * Returns a hash value for the specified object.
   * In addition to the object's own hashCode, this
   * method applies a "supplemental hash function,"
   * which defends against poor quality hash functions.
   */
  static int hash(Object key) {
    int h = key.hashCode();

    h += ~(h << 9);
    h ^= (h >>> 14);
    h += (h << 4);
    h ^= (h >>> 10);
    return h;
  }
}