logo Hurry, Grab up to 30% discount on the entire course
Order Now logo

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
R. BakerSociology
(5/5)

908 Answers

Hire Me
expert
StatAnalytica ExpertResume writing
(5/5)

560 Answers

Hire Me
expert
Kyle BaileyFinance
(4/5)

813 Answers

Hire Me
expert
Janet FearnleyPsychology
(4/5)

796 Answers

Hire Me
Java Programming

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

{

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

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

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme