Programming Project 11.5. (Using BST to resolve collision in the hash table)
Read the description very carefully. You have to practically combine the code that is already provided in the book and program the solution for this problem.
11.5 Instead of using a linked list to resolve collisions, as in separate chaining, use a binary search tree. That is, create a hash table that is an array of trees. You can use the hashChain.java program (Listing 11.3) as a starting point and the Tree class from the tree.java program (Listing 8.1) in Chapter 8. To display a small tree-based hash table, you could use an in-order traversal of each tree.
The advantage of a tree over a linked list is that it can be searched in O(logN) instead of O(N) time. This time savings can be a significant advantage if very high load factors are encountered. Checking 15 items takes a maximum of 15 comparisons in a list but only 4 in a tree.
Duplicates can present problems in both trees and hash tables, so add some code that prevents a duplicate key from being inserted in the hash table. (Beware: The find() method in Tree assumes a non-empty tree.) To shorten the listing for this program, you can forget about deletion, which for trees requires a lot of code.
LISTING 11.3 The hashChain.java Program
// hashChain.java
// demonstrates hash table with separate chaining
// to run this program: C:>java HashChainApp
import java.io.*; //////////////////////////////////////////////////////////////// class Link
Separate Chaining 555
{
private int iData; public Link next;
// (could be other items) // data item
// next link in list
{ iData= it; }
public int getKey() { return iData; }
{ System.out.print(iData + “ “); }
556 CHAPTER 11 Hash Tables
LISTING 11.3 Continued
} // end class Link //////////////////////////////////////////////////////////////// class SortedList
{
private Link first; // ref to first list item
public void SortedList() // constructor { first = null; }
{
int key = theLink.getKey();
Link previous = null; // start at first Link current = first;
// until end of list, while( current != null && key > current.getKey() )
{
previous = current; current = current.next; }
if(previous==null) first = theLink;
else
previous.next = theLink;
theLink.next = current;
} // end insert()
// -------------------------------------------------------------
public void delete(int key) {
Link previous = null; Link current = first;
// delete link
// (assumes non-empty list) // start at first
// until end of list, while( current != null && key != current.getKey() )
{
previous = current; current = current.next; }
if(previous==null) first = first.next;
else
// or key == current,
// go to next link
// disconnect link
// if beginning of list // delete first link // not at beginning
// or
// go
current > key,
to next item
// if
//
// not at beginning,
// prev --> new link // new link --> current
beginning of list, first --> new link
LISTING 11.3 Continued
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)
}
return null;
} // end find()
// didn’t find it
// ------------------------------------------------------------- public void displayList()
{
System.out.print(“List (first-->last): “);
Link current = first; while(current != null)
{
current.displayLink();
current = current.next; // move to next link }
System.out.println(“”);
}
} // end class SortedList
//////////////////////////////////////////////////////////////// class HashTable
{
private SortedList[] hashArray; // array of lists private int arraySize;
// ------------------------------------------------------------- public HashTable(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 }
// start at beginning of list // until end of list,
// print data
Separate Chaining 557
{ // if(current.getKey() == key)
or key too small,
// is this the link? found it, return link go to next item
return current =
current; // current.next; //
558 CHAPTER 11 Hash Tables
LISTING 11.3 Continued
{
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()
{
int hashVal = hashFunc(key); // hash the key hashArray[hashVal].delete(key); // delete link } // end delete()
{
int hashVal = hashFunc(key); // hash the key
Link theLink = hashArray[hashVal].find(key); // get link return theLink; // return link
}
//////////////////////////////////////////////////////////////// class HashChainApp
{
public static void main(String[] args) throws IOException
{
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
