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

You MUST use this main method:

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 you MUST get is this one:

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: