Java Reference
In-Depth Information
Display 15.35
Hash Table Demonstration
1
public class
HashTableDemo
2 {
3
public static void
main(String[] args)
4 {
5 HashTable h =
new
HashTable( );
6 System.out.println("Adding dog, cat, turtle, bird");
7 h.put("dog");
8 h.put("cat");
9 h.put("turtle");
10 h.put("bird");
11 System.out.println("Contains dog? " +
12 h.containsString("dog"));
13 System.out.println("Contains cat? " +
14 h.containsString("cat"));
15 System.out.println("Contains turtle? " +
16 h.containsString("turtle"));
17 System.out.println("Contains bird? " +
18
h.containsString("bird"));
19 System.out.println("Contains fish? " +
20 h.containsString("fish"));
21 System.out.println("Contains cow? " +
22
h.containsString("cow"));
23
}
24 }
Sample Dialogue
Adding dog, cat, turtle, bird
Contains dog? true
Contains cat? true
Contains turtle? true
Contains bird? true
Contains fish? false
Contains cow? False
Efficiency of Hash Tables
The efficiency of our hash table depends on several factors. First, let us examine some
extreme cases. The worst-case run-time performance occurs if every item inserted into
the table has the same hash key. Everything will then be stored in a single linked list.
With
n
items, the find operation will require
O
(
n
) steps. Fortunately, if the items that
we insert are somewhat random, the probability that all of them will hash to the same
key is highly unlikely. In contrast, the best-case run-time performance occurs if every
