1) Implement the Hash Table using a DOUBLE HASHING method, instead of linear pro
ID: 3536985 • Letter: 1
Question
1) Implement the Hash Table using a DOUBLE HASHING method, instead of linear probing.
2) To test your implementation you will write a driver program and create a set of objects to be stored in the Hash Table.
3) Write a class called Person. Each object should contain: Last Name, First Name, Age and an ID Number.
4) Create a file containing information for about 30 Person Objects.
5) Write a driver program which creates a Hash Table with capacity of 51. Your Driver should read the file and create 30 Person objects from that data, which will then be put into the Hash Table. Have your code print a message every time a collision occurs.
6) Once the Hash Table has been created, print the entire Table.
7) Your driver program should also include code that searches for several objects %u2013 make sure some you are searching for are NOT in the table.
here it is:
package edu.colorado.collections;
public class Table1<K,E>
{
private int manyItems;
private Object[ ] keys;
private Object[ ] data;
private boolean[ ] hasBeenUsed;
public Table1(int capacity)
{
if (capacity <= 0)
throw new IllegalArgumentException("Capacity is negative");
keys = new Object[capacity];
data = new Object[capacity];
hasBeenUsed = new boolean[capacity];
}
public boolean containsKey(K key)
{
return(findIndex(key)!= -1);
}
private int findIndex(K key)
{
//Postcondition: If the specified key is found in the table, then the return
// value is the index of the specified key. Otherwise, the return value is - 1
int count = 0;
int i = hash(key);
while ((count < data. length) && (hasBeenUsed[i]))
{
if (key . equals (keys[i]))
return i ;
count++;
i = nextIndex(i);
}
return -1;
}
//@SuppressWarnings("unchecked")
public E get(K key)
{
int index = findIndex(key);
if (index == -1)
return null;
else
return (E) data [index] ;
}
private int hash (Object key)
// The return value is a valid index of the table's arrays. The index is calculated as the
//remainder when the absolute value of the key's hash code is divided by the size of the
//table's arrays.
{
return Math.abs(key.hashCode( )) % data.length;
}
private int nextIndex(int i)
// The return value is normally i+1. But if i+1 is data.length, then the return value Is zero //instead,
{
if (i+1 == data.length)
return 0;
else
return i+1;
}
private E put(K key, E element)
{
int index = findIndex(key);
E answer;
if (index!=-1)
{
answer =(E) data[index];
data[index]= element;
return answer;
}
else if (manyItems<data.length)
{
index =hash (key);
while (keys[index] != null)
index =nextIndex (index);
keys[index] = key;
data[index] = element;
hasBeenUsed[index] = true;
manyItems++;
return null;
}
else
{
throw new IllegalStateException("Table is full.");
}
}
private E remove (K key)
{
int index = findIndex(key);
E answer = null;
if (index!=-1)
{
answer =(E) data[index];
keys[index]= null;
data[index] = null;
manyItems--;
}
return answer;
}
}
Explanation / Answer
FOLLOW THIS
I don't think you've missed anything, and in particular the problem arises regardless of table size whenhashFunction2(key) == 0.
Use (hashFunction2(key) % (tableSize - 1) + 1) in place of hashFunction2(key). It's desirable that the stride is a generator of the ring modulo the table size (which is a posh way of saying that your probe eventually covers the whole table), or failing that at least has a large period. Since your table size is prime that just means you have to avoid 0.
I don't think you've missed anything, and in particular the problem arises regardless of table size whenhashFunction2(key) == 0.
Use (hashFunction2(key) % (tableSize - 1) + 1) in place of hashFunction2(key). It's desirable that the stride is a generator of the ring modulo the table size (which is a posh way of saying that your probe eventually covers the whole table), or failing that at least has a large period. Since your table size is prime that just means you have to avoid 0.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.