Question: In hash table, chaining approach, long linked list needs more time to
ID: 662308 • Letter: Q
Question
Question:
In hash table, chaining approach, long linked list needs more time to be searched to find or delete an element. To enhance this structure, you need to add a new method called to hash table (chaining) called duplicate that receives an integer number represents the max. average number of nodes in each chain. Your method will calculate the average number of nodes currently in the table (total number of nodes divided by table size), if this average is greater than received parameter, your method should duplicate the table size, and rehash all elements according to the new table, otherwise, this method does nothing.
Hint: similar to what we did when duplicating hash table in linear probing approach, you need to use a temporary array to hold current table elements, the n create new one (with duplicated size) and assign it to the name of the old array in order not to change other methods ( remove, find) which use old name, same thing is applied to array size variable.
CODE:
// hashChain.java
// demonstrates hash table with separate chaining
// to run this program: C:>java HashChainApp
import java.io.*;
////////////////////////////////////////////////////////////////
class Link
{ // (could be other items)
private int iData; // data item
public Link next; // next link in list
// -------------------------------------------------------------
public Link(int it) // constructor
{ iData= it; }
// -------------------------------------------------------------
public int getKey()
{ return iData; }
// -------------------------------------------------------------
public void displayLink() // display this link
{ System.out.print(iData + " "); }
} // end class Link
////////////////////////////////////////////////////////////////
class SortedList
{
private Link first; // ref to first list item
// -------------------------------------------------------------
public void SortedList() // constructor
{ first = null; }
// -------------------------------------------------------------
public void insert(Link theLink) // insert link, in order
{
int key = theLink.getKey();
Link previous = null; // start at first
Link current = first;
// until end of list,
while( current != null && key > current.getKey() )
{ // or current > key,
previous = current;
current = current.next; // go to next item
}
if(previous==null) // if beginning of list,
first = theLink; // first --> new link
else // not at beginning,
previous.next = theLink; // prev --> new link
theLink.next = current; // new link --> current
} // end insert()
// -------------------------------------------------------------
public void delete(int key) // delete link
{ // (assumes non-empty list)
Link previous = null; // start at first
Link current = first;
// until end of list,
while( current != null && key != current.getKey() )
{ // or key == current,
previous = current;
current = current.next; // go to next link
}
// disconnect link
if(previous==null) // if beginning of list
first = first.next; // delete first link
else // not at beginning
previous.next = current.next; // delete current link
} // end delete()
// -------------------------------------------------------------
public Link find(int key) // find link
{
Link current = first; // start at first
// until end of list,
while(current != null && current.getKey() <= key)
{ // or key too small,
if(current.getKey() == key) // is this the link?
return current; // found it, return link
current = current.next; // go to next item
}
return null; // didn't find it
} // end find()
// -------------------------------------------------------------
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning of list
while(current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
} // end class SortedList
////////////////////////////////////////////////////////////////
class CHashTable
{
private SortedList[] hashArray; // array of lists
private int arraySize;
// -------------------------------------------------------------
public CHashTable(int size) // constructor
{
arraySize = size;
hashArray = new SortedList[arraySize]; // create array
for(int j=0; j<arraySize; j++) // fill array
hashArray[j] = new SortedList(); // with lists
}
// -------------------------------------------------------------
public void displayTable()
{
for(int j=0; j<arraySize; j++) // for each cell,
{
System.out.print(j + ". "); // display cell number
hashArray[j].displayList(); // display list
}
}
// -------------------------------------------------------------
public int hashFunc(int key) // hash function
{
return key % arraySize;
}
// -------------------------------------------------------------
public void insert(Link theLink) // insert a link
{
int key = theLink.getKey();
int hashVal = hashFunc(key); // hash the key
hashArray[hashVal].insert(theLink); // insert at hashVal
} // end insert()
// -------------------------------------------------------------
public void delete(int key) // delete a link
{
int hashVal = hashFunc(key); // hash the key
hashArray[hashVal].delete(key); // delete link
} // end delete()
// -------------------------------------------------------------
public Link find(int key) // find link
{
int hashVal = hashFunc(key); // hash the key
Link theLink = hashArray[hashVal].find(key); // get link
return theLink; // return link
}
// -------------------------------------------------------------
} // end class HashTable
////////////////////////////////////////////////////////////////
class HashChainApp
{
public static void main(String[] args) throws IOException
{
int aKey;
Link aDataItem;
int size, n, keysPerCell = 100;
// get sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
// make table
CHashTable theHashTable = new CHashTable(size);
for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() *
keysPerCell * size);
aDataItem = new Link(aKey);
theHashTable.insert(aDataItem);
}
while(true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, or find: ");
char choice = getChar();
switch(choice)
{
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new Link(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 HashChainApp
////////////////////////////////////////////////////////////////
Explanation / Answer
// hashChain.java
// demonstrates hash table with separate chaining
// to run this program: C:>java HashChainApp
import java.io.*;
import java.util.ArrayList;
////////////////////////////////////////////////////////////////
class Link
{ // (could be other items)
private int iData; // data item
public Link next; // next link in list
// -------------------------------------------------------------
public Link(int it) // constructor
{ iData= it; }
// -------------------------------------------------------------
public int getKey()
{ return iData; }
// -------------------------------------------------------------
public void displayLink() // display this link
{ System.out.print(iData + " "); }
} // end class Link
////////////////////////////////////////////////////////////////
class SortedList
{
private Link first; // ref to first list item
// -------------------------------------------------------------
public SortedList() // constructor
{ first = null; }
// -------------------------------------------------------------
public void insert(Link theLink) // insert link, in order
{
int key = theLink.getKey();
Link previous = null; // start at first
Link current = first;
// until end of list,
while( current != null && key > current.getKey() )
{ // or current > key,
previous = current;
current = current.next; // go to next item
}
if(previous==null) // if beginning of list,
first = theLink; // first --> new link
else // not at beginning,
previous.next = theLink; // prev --> new link
theLink.next = current; // new link --> current
} // end insert()
// -------------------------------------------------------------
public void delete(int key) // delete link
{ // (assumes non-empty list)
Link previous = null; // start at first
Link current = first;
// until end of list,
while( current != null && key != current.getKey() )
{ // or key == current,
previous = current;
current = current.next; // go to next link
}
// disconnect link
if(previous==null) // if beginning of list
first = first.next; // delete first link
else // not at beginning
previous.next = current.next; // delete current link
} // end delete()
// -------------------------------------------------------------
public Link find(int key) // find link
{
Link current = first; // start at first
// until end of list,
while(current != null && current.getKey() <= key)
{ // or key too small,
if(current.getKey() == key) // is this the link?
return current; // found it, return link
current = current.next; // go to next item
}
return null; // didn't find it
} // end find()
// -------------------------------------------------------------
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning of list
while(current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
//get all elements fro mthe array
public ArrayList<Integer> getList()
{
ArrayList<Integer> d = new ArrayList<Integer>();
Link current = first; // start at beginning of list
while(current != null) // until end of list,
{
d.add(current.getKey());
current = current.next; // move to next link
}
return d;
}
} // end class SortedList
////////////////////////////////////////////////////////////////
class CHashTable
{
private SortedList[] hashArray; // array of lists
private int arraySize;
private int arrayElements;
// -------------------------------------------------------------
public CHashTable(int size) // constructor
{
arrayElements = 0;
arraySize = size;
hashArray = new SortedList[arraySize]; // create array
for(int j=0; j<arraySize; j++) // fill array
hashArray[j] = new SortedList(); // with lists
}
public void duplicate(int maxAvgNodes)
{
int avgNodes = arrayElements/arraySize;
if(avgNodes > maxAvgNodes)
{
ArrayList<Integer> data = new ArrayList<Integer>();
for(int i=0; i<arraySize; i++)
{
data.addAll(hashArray[i].getList());
}
arrayElements = 0;
arraySize = arraySize*2;
hashArray = new SortedList[arraySize]; // create array
for(int j=0; j<arraySize; j++) // fill array
hashArray[j] = new SortedList();
for (Integer d : data) {
Link aDataItem = new Link(d);
this.insert(aDataItem);
}
System.out.println(" Hash table resized successfully !!");
}
else
{
System.out.println(" No need to resize the table");
}
}
// -------------------------------------------------------------
public void displayTable()
{
for(int j=0; j<arraySize; j++) // for each cell,
{
System.out.print(j + ". "); // display cell number
hashArray[j].displayList(); // display list
}
//System.out.println("Total elements: "+arrayElements);
}
// -------------------------------------------------------------
public int hashFunc(int key) // hash function
{
return key % arraySize;
}
// -------------------------------------------------------------
public void insert(Link theLink) // insert a link
{
int key = theLink.getKey();
int hashVal = hashFunc(key); // hash the key
hashArray[hashVal].insert(theLink); // insert at hashVal
arrayElements++;
} // end insert()
// -------------------------------------------------------------
public void delete(int key) // delete a link
{
int hashVal = hashFunc(key); // hash the key
hashArray[hashVal].delete(key); // delete link
arrayElements--;
} // end delete()
// -------------------------------------------------------------
public Link find(int key) // find link
{
int hashVal = hashFunc(key); // hash the key
Link theLink = hashArray[hashVal].find(key); // get link
return theLink; // return link
}
// -------------------------------------------------------------
} // end class HashTable
////////////////////////////////////////////////////////////////
class HashChainApp
{
public static void main(String[] args) throws IOException
{
int aKey;
Link aDataItem;
int size, n, keysPerCell = 100;
// get sizes
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter initial number of items: ");
n = getInt();
// make table
CHashTable theHashTable = new CHashTable(size);
for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() *
keysPerCell * size);
aDataItem = new Link(aKey);
theHashTable.insert(aDataItem);
}
while(true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, find or reDuplicateTable: ");
char choice = getChar();
switch(choice)
{
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter key value to insert: ");
aKey = getInt();
aDataItem = new Link(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;
case 'r':
System.out.print("Enter maximum average number of Nodes in chain: ");
int max = getInt();
theHashTable.duplicate(max);
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 HashChainApp
////////////////////////////////////////////////////////////////
------------------------------------------------------------------------------------------------------------------------------
OUTPUT
------------------------------------------------------------------------------------------------------------------------------
Enter size of hash table: 4
Enter initial number of items: 12
Enter first letter of show, insert, delete, find or duplicate: s
0. List (first-->last): 140 300 312
1. List (first-->last): 125
2. List (first-->last): 50 194 314 326 346
3. List (first-->last): 247 267 375
Enter first letter of show, insert, delete, find or duplicate: r
Hash table resized successfully
Enter first letter of show, insert, delete, find or duplicate: s
0. List (first-->last): 312
1. List (first-->last):
2. List (first-->last): 50 194 314 346
3. List (first-->last): 267
4. List (first-->last): 140 300
5. List (first-->last): 125
6. List (first-->last): 326
7. List (first-->last): 247 375
Enter first letter of show, insert, delete, find or duplicate: r
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.