Solve this question using the Main provided and make sure that you get the same output that i have posted. Post comple program and output please. THANK YOU

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 inorder 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

// 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; // didnt 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 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

// ------------------------------------------------------------- public void displayTable() { for(int j=0; j

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 HashTable theHashTable = new HashTable(size); for(int j=0; j

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

Use this main provided below. You MUST use it so you can get the output that is posted further below.

public static void main(String[] args) throws IOException

{

int aKey, aDataItem;

int size, n, keysPerCell = 10;

// get sizes

System.out.print("Enter size of hash table: ");

size = getInt();

System.out.print("Enter initial number of items: ");

n = getInt();

// make table

HashTable theHashTable = new HashTable(size);

for(int j=0; j

{

aDataItem = (int)(java.lang.Math.random() *

keysPerCell * size);

theHashTable.insert(aDataItem);

}

while(true) // interact with user

{

System.out.print("Enter first letter of ");

System.out.print("show, insert, or find: ");

char choice = getChar();

switch(choice)

{

case 's':

theHashTable.displayTable();

break;

case 'i':

System.out.print("Enter key value to insert: ");

aDataItem = getInt();

theHashTable.insert(aDataItem);

break;

case 'f':

System.out.print("Enter key value to find: ");

aKey = getInt();

aDataItem = theHashTable.find(aKey);

if(aDataItem != -1)

System.out.println("Found " + aDataItem);

else

System.out.println("Could not find " + aKey);

break;

default:

System.out.print("Invalid entry ");

} // end switch

} // end while

} // end main()

The output MUST be this one below. It has to be the exact same one. Make sure you post the whole complete program and the output display.

Enter size of hash table: 10

Enter initial number of items: 20

Duplicate key

Duplicate key

Duplicate key

Duplicate key

Enter first letter of show, insert, or find: s

0. 20 70

1. 1

2. 42 82

3. 53

4. 54

5. 75 85

6. 56 86

7. 47 67 97

8. 8 78

9.

Enter first letter of show, insert, or find: i

Enter key value to insert: 10

Enter first letter of show, insert, or find: s

0. 10 20 70

1. 1

2. 42 82

3. 53

4. 54

5. 75 85

6. 56 86

7. 47 67 97

8. 8 78

9.

Enter first letter of show, insert, or find: f

Enter key value to find: 8

Found 8

Enter first letter of show, insert, or find: f

Enter key value to find: 9

Could not find 9

Enter first letter of show, insert, or find: