Answer Happy

The code bellow is for linear probing in hash tables. You are
asked to modify insert and delete methods, so they will perform
quadratic probing Instead of linear probing
// ---Do not change DataItem class
----------------------------------
public class DataItem {
private int key; // key to hash
private int value; // (key,value):DataItem
public DataItem(int k) {
this.key=k;
}
public DataItem(int k, int v) {
this.key=k;
this.value=v;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
}
//Modify insert and delete methods only
public class HashTable {
private int arraySize;
private DataItem hashArray[];
private DataItem delItem;
private int nbElem;
//constructor
public HashTable(int s) {
this.arraySize = s ;
this.hashArray = new DataItem[arraySize];
this.delItem=new DataItem(-1); //to mark deleted items
nbElem=0;
}
public int hashFunction(int key) {
return key%arraySize;
}
public void insert(DataItem dItem) {
if(! isFull()) {
int hashValue= hashFunction(dItem.getKey());
while(hashArray[hashValue]!=null &&
hashArray[hashValue].getKey()!=-1) {
hashValue++;
hashValue=hashValue%arraySize;
}
hashArray[hashValue]=dItem;
nbElem++;
}
else
System.out.println("Hash Table is Full");;
}
public DataItem delete(int key) {
int hashValue= hashFunction(key);
while(hashArray[hashValue]!=null) {
if (hashArray[hashValue].getKey()==key) {
DataItem temp=hashArray[hashValue];
hashArray[hashValue]=delItem;
return temp;
}
hashValue++;
hashValue%=arraySize;
}
return null;
}
public void display() {
System.out.print("Hash Table: {");
for(int i=0;i<arraySize-1;i++) {
if(hashArray!=delItem && hashArray!=null) {
System.out.print(hashArray.getKey()+":"+hashArray.getValue()+",
");
}
else if(hashArray==delItem )
System.out.print(" del, ");
else
System.out.print(" null, ");
}
if(hashArray[arraySize-1]!=delItem &&
hashArray[arraySize-1]!=null)
System.out.println(hashArray[arraySize1].getKey()+":"+hashArray[arraySize-1].getValue()+"}
");
else if(hashArray[arraySize-1]==delItem )
System.out.println(" del } ");
else
System.out.println(" null } ");
}
public boolean isFull() {
return nbElem==arraySize;
}
}
// ---------- do not change the HashTableApp class
-------------------
public class HashTableApp {
public static void main(String[] args) {
HashTable myHashTable = new HashTable(7);
System.out.println("Quadratic probing:");
myHashTable.display();
System.out.println("\nInsert 50, 700, 76, 85, 92, 73, 101");
DataItem insItem = new DataItem(50);
myHashTable.insert(insItem);
insItem = new DataItem(700);
myHashTable.insert(insItem);
insItem = new DataItem(76);
myHashTable.insert(insItem);
insItem = new DataItem(85);
myHashTable.insert(insItem);
insItem = new DataItem(92);
myHashTable.insert(insItem);
insItem = new DataItem(73);
myHashTable.insert(insItem);
insItem = new DataItem(101);
myHashTable.insert(insItem);
myHashTable.display();
//700, 50, 85, 73, 101, 92, 76
System.out.println("\nDelete 85:");
myHashTable.delete(85);
myHashTable.display();
System.out.println("\nDelete 92:");
myHashTable.delete(92);
myHashTable.display();
}
}
When run your program needs to generate the following
output.
Output:
Quadratic probing:
Hash Table: {null, null, null, null, null, null, null}
Insert 50, 700, 76, 85, 92, 73, 101
Hash Table: {700:0, 50:0, 85:0, 73:0, 101:0, 92:0, 76:0}
Delete 85:
Hash Table: {700:0, 50:0, del, 73:0, 101:0, 92:0, 76:0}
Delete 92:
Hash Table: {700:0, 50:0, del, 73:0, 101:0, del, 76:0}