Modify the hash.java program to use quadratic probing. // hash.java // demonstra

Question

Modify the hash.java program to use quadratic probing.


// hash.java
// demonstrates hash table with linear probing
// to run this program: C:>java HashTableApp
import java.io.*;
////////////////////////////////////////////////////////////////
class DataItem
{ // (could have more data)
private int iData; // data item (key)
//--------------------------------------------------------------
public DataItem(int ii) // constructor
{ iData = ii; }
//--------------------------------------------------------------
public int getKey()
{ return iData; }
//--------------------------------------------------------------
} // end class DataItem
////////////////////////////////////////////////////////////////
class HashTable
{
private DataItem[] hashArray; // array holds hash table
private int arraySize;
private int count;
private DataItem nonItem; // for deleted items
// -------------------------------------------------------------
public HashTable(int size) // constructor
{
arraySize = size;
count = 0;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
}
public int getCount(){
return count;
}
public int getSize(){
return arraySize;
}
// -------------------------------------------------------------
public void displayTable()
{
System.out.print("Table: ");
for(int j=0; j<arraySize; j++)
{
if(hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}
// -------------------------------------------------------------
public int hashFunc(int key)
{
return key % arraySize; // hash function
}
// -------------------------------------------------------------
public void insert(DataItem item) // insert a DataItem
// (assumes table not full)
{
int key = item.getKey(); // extract key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
//if(count>=arraySize)return;

while(hashArray[hashVal] != null &&
hashArray[hashVal].getKey() != -1)
{
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
}
hashArray[hashVal] = item; // insert item
count++;
} // end insert()
// -------------------------------------------------------------
public DataItem delete(int key) // delete a DataItem
{
int hashVal = hashFunc(key); // hash the key

int start=hashVal;

while(hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if(hashArray[hashVal].getKey() == key)
{
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = nonItem; // delete item
count--;
return temp; // return item
}
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
if(hashVal == start) break;
}
return null; // can't find item
} // end delete()
// -------------------------------------------------------------
public DataItem find(int key) // find item with key
{
int hashVal = hashFunc(key); // hash the key

int start=hashVal;
while(hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
if(hashVal == start) break;
}
return null; // can't find item
}
// -------------------------------------------------------------
} // end class HashTable
////////////////////////////////////////////////////////////////
class HashTableApp
{
public static void main(String[] args) throws IOException
{
DataItem aDataItem;
int aKey, size, n, keysPerCell;
// get sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
// make table
HashTable theHashTable = new HashTable(size);

for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() *
keysPerCell * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
}

while(true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, find or quit: ");
char choice = getChar();
switch(choice)
{
case 'q': return;
case 's':
theHashTable.displayTable();
break;
case 'i':
if(theHashTable.getCount()>=theHashTable.getSize())
{
System.out.println("Hash table is full, cannot insert");
break;
}
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter key value to delete: ");
aKey = getInt();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter key value to find: ");
aKey = getInt();
aDataItem = theHashTable.find(aKey);
if(aDataItem != null)
{
System.out.println("Found " + aKey);
}
else
System.out.println("Could not find " + aKey);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
//--------------------------------------------------------------
} // end class HashTableApp
////////////////////////////////////////////////////////////////

Explanation / Answer

The codes between ******* marks are changes I made.

Here is the wiki for quadratic probing. http://en.wikipedia.org/wiki/Quadratic_probing

Welcome leave comments for any followups and questions.

//hash.java
//demonstrates hash table with linear probing
//to run this program: C:>java HashTableApp
import java.io.*;


class DataItem { // (could have more data)
private int iData; // data item (key)
// --------------------------------------------------------------

public DataItem(int ii) // constructor
{
iData = ii;
}

// --------------------------------------------------------------
public int getKey() {
return iData;
}
// --------------------------------------------------------------
} // end class DataItem
// //////////////////////////////////////////////////////////////

class HashTable {
private DataItem[] hashArray; // array holds hash table
private int arraySize;
private int count;
private DataItem nonItem; // for deleted items
// -------------------------------------------------------------

public HashTable(int size) // constructor
{
arraySize = size;
count = 0;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1); // deleted item key is -1
}

public int getCount() {
return count;
}

public int getSize() {
return arraySize;
}

// -------------------------------------------------------------
public void displayTable() {
System.out.print("Table: ");
for (int j = 0; j < arraySize; j++) {
if (hashArray[j] != null)
System.out.print(hashArray[j].getKey() + " ");
else
System.out.print("** ");
}
System.out.println("");
}

// -------------------------------------------------------------
public int hashFunc(int key) {
return key % arraySize; // hash function
}

// -------------------------------------------------------------
public void insert(DataItem item) // insert a DataItem
// (assumes table not full)
{
int key = item.getKey(); // extract key
int hashVal = hashFunc(key); // hash the key
// until empty cell or -1,
// if(count>=arraySize)return;

// ********************************************************************
//original linear probing
// while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
// ++hashVal; // go to next cell
// hashVal %= arraySize; // wraparound if necessary
// }

//change to quadratic probing
int k = 1;
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
hashVal = (hashVal + k*k) % arraySize;
++k;
}
// ********************************************************************

hashArray[hashVal] = item; // insert item
count++;
} // end insert()
// -------------------------------------------------------------

public DataItem delete(int key) // delete a DataItem
{
int hashVal = hashFunc(key); // hash the key

int start = hashVal;

int k = 1;
while (hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if (hashArray[hashVal].getKey() == key) {
DataItem temp = hashArray[hashVal]; // save item
hashArray[hashVal] = nonItem; // delete item
count--;
return temp; // return item
}
// ********************************************************************
// ++hashVal; // go to next cell
// hashVal %= arraySize; // wraparound if necessary
hashVal = (hashVal + k*k) % arraySize;
++k;
// ********************************************************************
if (hashVal == start)
break;
}
return null; // can't find item
} // end delete()
// -------------------------------------------------------------

public DataItem find(int key) // find item with key
{
int hashVal = hashFunc(key); // hash the key

int start = hashVal;
while (hashArray[hashVal] != null) // until empty cell,
{ // found the key?
if (hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
++hashVal; // go to next cell
hashVal %= arraySize; // wraparound if necessary
if (hashVal == start)
break;
}
return null; // can't find item
}
// -------------------------------------------------------------
} // end class HashTable
// //////////////////////////////////////////////////////////////

class HashTableApp {
public static void main(String[] args) throws IOException {
DataItem aDataItem;
int aKey, size, n, keysPerCell;
// get sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
keysPerCell = 10;
// make table
HashTable theHashTable = new HashTable(size);

for (int j = 0; j < n; j++) // insert data
{
aKey = (int) (java.lang.Math.random() * keysPerCell * size);
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
}

while (true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, find or quit: ");
char choice = getChar();
switch (choice) {
case 'q':
return;
case 's':
theHashTable.displayTable();
break;
case 'i':
if (theHashTable.getCount() >= theHashTable.getSize()) {
System.out.println("Hash table is full, cannot insert");
break;
}
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter key value to delete: ");
aKey = getInt();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter key value to find: ");
aKey = getInt();
aDataItem = theHashTable.find(aKey);
if (aDataItem != null) {
System.out.println("Found " + aKey);
} else
System.out.println("Could not find " + aKey);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
// --------------------------------------------------------------

public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}

// --------------------------------------------------------------
public static char getChar() throws IOException {
String s = getString();
return s.charAt(0);
}

// -------------------------------------------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
// --------------------------------------------------------------
} // end class HashTableApp
// //////////////////////////////////////////////////////////////

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

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