Sunday, June 17, 2012

Hash table drill program

import java.util.Random;
import java.io.*;
import java.util.Scanner;

public class HashDrill
{  // Selection the hash function for int hash()
   static private int   option = 0;

   static private boolean[] displaced;

   // Seeded in main, used in fillTable
   static Random generator = new Random();

   static Scanner console = new Scanner(System.in);

// Hash function, based on the selection option
   private static int hash ( int value, int size )
   {  int d1 = Math.abs(value),
          d0 = d1 % 10;
      int key = d1 % size;   // Used for single-digit value

      // More than one digit; isolate d1 and compute.
      if ( d1 != d0 )
      {  while ( d1 > 9 )
            d1 /= 10;
         if ( option == 0 )
            key = (d1*10 + d0) % size;
         else
            key = (d1 * d0) % size;
      }
      return key;
   }

   // Fill table[], val[] and key[]
   private static void fillTable ( int[] table, int[] val, int[] key )
   {  int j, k,
          size = table.length;

      // Initialize the table to empty (-1 throughout)
      for ( j = 0; j < size; j++ )
         table[j] = -1;

      // Generate the values, then place them into the table
      for ( j = 0; j < val.length; j++ )
      {  k = generator.nextInt(4) + 1;
         val[j] = generator.nextInt((int)Math.pow(10,k));
         k = hash(val[j], size);
         key[j] = k;

         // Linear probe for an available cell
         while ( table[k] != -1 )
            k = (k+1) % size;
         // Position the value into the table
         table[k] = val[j];
         displaced[k] = k != hash(val[j], size);
      }
   }

   // Display table[], val[] and key[]
   private static void showTable ( int[] table, int[] val, int[] key )
   {  int j;

      System.out.println ("\nd1 is the leading digit, d0 the trailing." +
         "\nHash function:  " +
         ( option == 0 ? "(d1*10 + d0) % " : "(d1 * d0) % " ) +
         table.length );

      System.out.println ("\nindex    value  key");
      for ( j = 0; j < val.length; j++ )
         System.out.printf ("%5d %8d %4d\n", j, val[j], key[j]);

      System.out.print ("\nPress enter to see the hash table.");
      console.nextLine();

      System.out.println ("\nindex    table");
      for ( j = 0; j < table.length; j++ )
      {  System.out.printf ("%5d %8d", j, table[j]);
         if (displaced[j]) System.out.print("  *");
         System.out.println();
      }
   }

   public static void main ( String[] args )
   {  long   seed = generator.nextLong();
      int    size = -1;
      int[]  table;
      int[]  val = new int[10];
      int[]  key = new int[10];
      int    j, k;

      System.out.print ("Size:  ");
      if ( args.length > 0 )
      {  try
         {  size = Integer.parseInt(args[0].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println(size);
      }
      else
      {  size = console.nextInt();  console.nextLine();  }
      table = new int[size];
      displaced = new boolean[size];

      if ( args.length > 1 )
      {  try
         {  option = Integer.parseInt(args[1].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
      }

      if ( args.length > 2 )
      {  try
         {  seed = Long.parseLong(args[2].trim());  }
         catch (Exception e)
         {  System.out.println(e);  System.exit(-1);  }
         System.out.println("Setting seed to " + seed);
      }
      generator.setSeed(seed);

      fillTable(table, val, key);

      showTable(table, val, key);
      System.out.print ("\nPress enter to exit.");
      console.nextLine();
   }
}


OUTPUT

Size:  10

d1 is the leading digit, d0 the trailing.
Hash function:  (d1*10 + d0) % 10

index    value  key
    0      501    1
    1      997    7
    2     3252    2
    3      624    4
    4      939    9
    5       46    6
    6      923    3
    7        8    8
    8       99    9
    9        8    8

Press enter to see the hash table.

index    table
    0       99  *
    1      501
    2     3252
    3      923
    4      624
    5        8  *
    6       46
    7      997
    8        8
    9      939