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
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