create a hash table that is an array of trees you can use the hashChain.java program as a starting point and the Tree class from the tree.java program to display a small tree-based hash table

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

• //  ------------------------------------------------------------- public Link(int it) // constructor

{ iData= it; }

• //  -------------------------------------------------------------

public int getKey() { return iData; }

• //  ------------------------------------------------------------- public void displayLink() // display this link

{ 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; }

• //  ------------------------------------------------------------- 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() )

 

{
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

• //  ------------------------------------------------------------- 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

{

Attachments:

Expert's Answer

706 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of