package doublehashing;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2002</p>
 * <p>Company: </p>
 * @author unascribed
 * @version 1.0
 */

public class DoubleHashing {

  public static
  void main(String[] args) {
      int [] x = { 16, 20, 33, 97, 22, 21, 32, 66, 78, 101, 40 } ;
      HashTable ht = new HashTable(4) ; // size 16
      for ( int i=0; i<x.length; i++ ) {
         System.out.println("\nInsert "+x[i]) ;
         ht.insert( new Integer(x[i]) );
         ht.printHashTable() ;
      }
  }
}


class HashTable {

    final static int HASH_TABLE_SIZE = 3 ;
    int hashTableSize ;
    Object [] hashTable ;
    int elementsHashed ;

    public HashTable() {
       this(HASH_TABLE_SIZE) ;
    }

    public HashTable(int k) {
       if ( (k<2) || (k>30 ) ) k = HASH_TABLE_SIZE ;
       hashTableSize = 1<<k ;
       hashTable = new Object[hashTableSize] ;
    }

    int hashValue(Object o) {
       return ( 0x7ffff & o.hashCode()) % hashTableSize ;
    }
    int secondaryHashValue(Object o) {
       return 2*(( 0x7ffff & o.hashCode())%7) + 1 ;
    }

   void insert(Object o) {
       if ( elementsHashed>(hashTableSize-2) ) return ;
       // ASSERT at least 2 open spots in hash table
       int hv = hashValue(o) ;
       int shv = secondaryHashValue(o) ;
       while ( hashTable[hv] != null ) {
          hv = (hv+shv) % hashTableSize ;
       }
       hashTable[hv] = o ;
       elementsHashed++ ;
   }

   void printHashTable() {
      System.out.println("\nHash Table:") ;
      for ( int i=0; i<hashTable.length; i++ ) {
         System.out.println("h["+i+"] = "+hashTable[i]) ;
      }
   }

}