Write a Java program to implement 2 hash tables, one using separate chaining and
ID: 3711611 • Letter: W
Question
Write a Java program to implement 2 hash tables, one using separate chaining and one using quadratic probing, using N%tablesize as the hash function. The user should specify the size of the two tables, which should be the same, and less than 500. The program should then generate enough random integers between 0 and 500 to fill the tables up to 90% capacity, inserting the same sequence of numbers into the two tables. Your program should count the numbers of collisions for each table, and report the number of collisions for each table when they are 30%, 40%, 50%, 60%, 70%, 80% and 90% full.
Explanation / Answer
ANS:-
PROGRAM :-
import java.util.ArrayList;
import java.util.Scanner;
class HashNode<K, V>
{
K key;
V value;
HashNode<K, V> next;
// Constructor
public HashNode(K key, V value)
{
this.key = key;
this.value = value;
}
}
class Map<K, V>
{
private ArrayList<HashNode<K, V>> bucketArray;
private int numBuckets;
private int size;
public Map()
{
bucketArray = new ArrayList<>();
numBuckets = 10;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
}
public int size() { return size; }
public boolean isEmpty() { return size() == 0; }
private int getBucketIndex(K key)
{
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index;
}
public V remove(K key)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
HashNode<K, V> prev = null;
while (head != null)
{
if (head.key.equals(key))
break;
prev = head;
head = head.next;
}
if (head == null)
return null;
size--;
if (prev != null)
prev.next = head.next;
else
bucketArray.set(bucketIndex, head.next);
return head.value;
}
public V get(K key)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
while (head != null)
{
if (head.key.equals(key))
return head.value;
head = head.next;
}
return null;
}
public void add(K key, V value)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
while (head != null)
{
if (head.key.equals(key))
{
head.value = value;
return;
}
head = head.next;
}
size++;
head = bucketArray.get(bucketIndex);
HashNode<K, V> newNode = new HashNode<K, V>(key, value);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
if ((1.0*size)/numBuckets >= 0.7)
{
ArrayList<HashNode<K, V>> temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
for (HashNode<K, V> headNode : temp)
{
while (headNode != null)
{
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
class QuadraticProbingHashTable
{
private int currentSize, maxSize;
private String[] keys;
private String[] vals;
public QuadraticProbingHashTable(int capacity)
{
currentSize = 0;
maxSize = capacity;
keys = new String[maxSize];
vals = new String[maxSize];
}
public void makeEmpty()
{
currentSize = 0;
keys = new String[maxSize];
vals = new String[maxSize];
}
public int getSize()
{
return currentSize;
}
public boolean isFull()
{
return currentSize == maxSize;
}
public boolean isEmpty()
{
return getSize() == 0;
}
public boolean contains(String key)
{
return get(key) != null;
}
private int hash(String key)
{
return key.hashCode() % maxSize;
}
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);
}
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 remove(String key)
{
if (!contains(key))
return;
int i = hash(key), h = 1;
while (!key.equals(keys[i]))
i = (i + h * h++) % maxSize;
keys[i] = vals[i] = null;
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 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 static void main(String[] args)
{
Map<String, Integer>map = new Map<>();
map.add("this",1 );
map.add("coder",2 );
map.add("this",4 );
map.add("hi",5 );
System.out.println(map.size());
System.out.println(map.remove("this"));
System.out.println(map.remove("this"));
System.out.println(map.size());
System.out.println(map.isEmpty());
Scanner scan = new Scanner(System.in);
System.out.println("Hash Table Test ");
System.out.println("Enter size");
QuadraticProbingHashTable qpht = new QuadraticProbingHashTable(scan.nextInt() );
char ch;
do
{
System.out.println(" Hash Table Operations ");
System.out.println("1. insert ");
System.out.println("2. remove");
System.out.println("3. get");
System.out.println("4. clear");
System.out.println("5. 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.remove( scan.next() );
break;
case 3 :
System.out.println("Enter key");
System.out.println("Value = "+ qpht.get( scan.next() ));
break;
case 4 :
qpht.makeEmpty();
System.out.println("Hash Table Cleared ");
break;
case 5 :
System.out.println("Size = "+ qpht.getSize() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.