Programming Excercise 20.18 ~Java Perform simulations to compare the observed pe

Question

Programming Excercise 20.18 ~Java

Perform simulations to compare the observed performance of hashing with the theoretical results. Declare a probing hash table, insert 10,000 randomly generated integers into the table, and count the average number of probes used. This number is the average cost of a successful search. Repeat the test several times for a good average. Run it for both linear probing and quadratic probing, and do it for ?nal load factors 0.1, 0.2, ..., 0.9. Always declare the table so that no rehashing is needed. Thus the test for load factor 0.4 would declare a table of size approximately 25,000 (adjusted to be prime).

Explanation / Answer

/**
* Java Program to implement Linaer and Quadratic Probing Hash Table
**/

import java.util.Scanner;

class Table
{   
private int currentSize, maxSize;
private String[] keys;
private String[] vals;   

/** Constructor **/
public Table(int capacity)
{
currentSize = 0;
maxSize = capacity;
keys = new String[maxSize];
vals = new String[maxSize];
}  

/** Function to clear hash table **/
public void makeEmpty()
{
currentSize = 0;
keys = new String[maxSize];
vals = new String[maxSize];
}

/** Function to get size of hash table **/
public int getSize()
{
return currentSize;
}

/** Function to check if hash table is full **/
public boolean isFull()
{
return currentSize == maxSize;
}

/** Function to check if hash table is empty **/
public boolean isEmpty()
{
return getSize() == 0;
}

/** Fucntion to check if hash table contains a key **/
public boolean contains(String key)
{
return get(key) != null;
}

/** Functiont to get hash code of a given key **/
private int hash(String key)
{
return key.hashCode() % maxSize;
}   

/** Function to insert key-value pair **/
public void insert(String key, String val)
{   
int tmp = hash(key);
int i = tmp, h = 1;
do
{
if (keys[i] == null)
{
keys[i] = key;
vals[i] = val;
currentSize++;
return;
}
if (keys[i].equals(key))
{
vals[i] = val;
return;
}   
i = (i + h * h++) % maxSize;   
} while (i != tmp);
}

/** Function to get value for a given key **/
public String get(String key)
{
int i = hash(key), h = 1;
while (keys[i] != null)
{
if (keys[i].equals(key))
return vals[i];
i = (i + h * h++) % maxSize;
System.out.println("i "+ i);
}   
return null;
}

/** Function to remove key and its value **/
public void remove1(String key)
{
if (!contains(key))
return;

/** find position key and delete **/
int i = hash(key), h = 1;
while (!key.equals(keys[i]))
i = (i + h * h++) % maxSize;   
keys[i] = vals[i] = null;

/** rehash all keys **/   
for (i = (i + h * h++) % maxSize; keys[i] != null; i = (i + h * h++) % maxSize)
{
String tmp1 = keys[i], tmp2 = vals[i];
keys[i] = vals[i] = null;
currentSize--;  
insert(tmp1, tmp2);   
}
currentSize--;   
}

public void remove2(String key)
{
if (!contains(key))
return;

/** find position key and delete **/
int i = hash(key);
while (!key.equals(keys[i]))
i = (i + 1) % maxSize;   
keys[i] = vals[i] = null;

/** rehash all keys **/   
for (i = (i + 1) % maxSize; keys[i] != null; i = (i + 1) % maxSize)
{
String tmp1 = keys[i], tmp2 = vals[i];
keys[i] = vals[i] = null;
currentSize--;  
insert(tmp1, tmp2);   
}
currentSize--;   
}
  

/** Function to print HashTable **/
public void printHashTable()
{
System.out.println(" Hash Table: ");
for (int i = 0; i < maxSize; i++)
if (keys[i] != null)
System.out.println(keys[i] +" "+ vals[i]);
System.out.println();
}
}

public class Test
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Hash Table Test ");
System.out.println("Enter size");

Table qpht = new Table(10000 );

char ch;
/** Perform ProbingHashTable operations **/
do   
{
System.out.println(" Hash Table Operations ");
System.out.println("1. insert ");
System.out.println("2. remove Using Linear Probing");
System.out.println("3. remove Using Quadratic Probing");
System.out.println("4. get");   
System.out.println("5. clear");
System.out.println("6. size");

int choice = scan.nextInt();   
switch (choice)
{
case 1 :
System.out.println("Enter key and value");
qpht.insert(scan.next(), scan.next() );
break;   
case 2 :
System.out.println("Enter key");
qpht.remove1( scan.next() );
break;   
case 3 :
System.out.println("Enter key");
qpht.remove2( scan.next() );
break;   

case 4 :
System.out.println("Enter key");
System.out.println("Value = "+ qpht.get( scan.next() ));
break;
case 5 :
qpht.makeEmpty();
System.out.println("Hash Table Cleared ");
break;
case 6 :
System.out.println("Size = "+ qpht.getSize() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
/** Display hash table **/
qpht.printHashTable();  

System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);   
} while (ch == 'Y'|| ch == 'y');  
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.