public class HashedDictionary
1: import java.util.Iterator;
2: import java.util.NoSuchElementException;
4: /**
5: A class that implements the ADT dictionary by using hashing and
6: linear probing to resolve collisions.
7: The dictionary is unsorted and has distinct search keys.
8: Search keys and associated values are not null.
9:
10: Notes: Uses probe for add, but locate for remove and getValue.
11: Uses linear probing, but includes code for quadratic probing.
12: Has a display method for illustration and testing.
14: @author Frank M. Carrano
15: @author Timothy M. Henry
16: @version 5.0
17: */
18: public class HashedDictionary<K, V> implements DictionaryInterface<K, V>
19: {
20: // The dictionary:
21: private int numberOfEntries;
22: private static final int DEFAULT_CAPACITY = 5; // Must be prime
23: private static final int MAX_CAPACITY = 10000;
24:
25: // The hash table:
26: private Entry<K, V>[] hashTable;
27: private int tableSize; // Must be prime
28: private static final int MAX_SIZE = 2 * MAX_CAPACITY;
29: private boolean integrityOK = false;
30: private static final double MAX_LOAD_FACTOR = 0.5; // Fraction of hash table
31: // that can be filled
32: protected final Entry<K, V> AVAILABLE = new Entry<>(null, null);
33:
34: public HashedDictionary()
35: {
36: this(DEFAULT_CAPACITY); // Call next constructor
37: } // end default constructor
38:
39: public HashedDictionary(int initialCapacity)
40: {
41: initialCapacity = checkCapacity(initialCapacity);
42: numberOfEntries = 0; // Dictionary is empty
43:
44: // Set up hash table:
45: // Initial size of hash table is same as initialCapacity if it is prime;
46: // otherwise increase it until it is prime size
47: int tableSize = getNextPrime(initialCapacity);
48: checkSize(tableSize); // Check that size is not too large
49:
50: // The cast is safe because the new array contains null entries
51: @SuppressWarnings("unchecked")
52: Entry<K, V>[] temp = (Entry<K, V>[])new Entry[tableSize];
53: hashTable = temp;
54: integrityOK = true;
55: } // end constructor
57: /* Implementations of methods in DictionaryInterface are here.
58: . . .
60: Implementations of private methods are here.
61: . . . */
63: protected final class Entry<S, T>
64: {
65: /* See Listing 21-1 in Chapter 21.
66: . . . */
67: } // end Entry
68: } // end HashedDictionary