public class HashedDictionary
1: import java.util.Arrays;
2: import java.util.Iterator;
3: import java.util.NoSuchElementException;
4:
5: /**
6: A class that implements the ADT dictionary by using hashing and
7: linear probing to resolve collisions.
8: The dictionary is unsorted and has distinct search keys.
9: Notes: Uses probe for add, but locate for remove and getValue.
10: Uses linear probing, but includes code for quadratic probing.
11: Has a display method for illustration and testing.
12:
13: @author Frank M. Carrano
14: @author Timothy M. Henry
15: @version 4.0
16: */
17: public class HashedDictionary<K, V> implements DictionaryInterface<K, V>
18: {
19: // The dictionary:
20: private int numberOfEntries;
21: private static final int DEFAULT_CAPACITY = 5; // Must be prime
22: private static final int MAX_CAPACITY = 10000;
23:
24: // The hash table:
25: private TableEntry<K, V>[] hashTable;
26: private int tableSize; // Must be prime
27: private static final int MAX_SIZE = 2 * MAX_CAPACITY;
28: private boolean initialized = false;
29: private static final double MAX_LOAD_FACTOR = 0.5; // Fraction of hash table
30: // that can be filled
31:
32: public HashedDictionary()
33: {
34: this(DEFAULT_CAPACITY); // Call next constructor
35: } // end default constructor
36:
37: public HashedDictionary(int initialCapacity)
38: {
39: checkCapacity(initialCapacity);
40: numberOfEntries = 0; // Dictionary is empty
41:
42: // Set up hash table:
43: // Initial size of hash table is same as initialCapacity if it is prime;
44: // otherwise increase it until it is prime size
45: int tableSize = getNextPrime(initialCapacity);
46: checkSize(tableSize);
47:
48: // The cast is safe because the new array contains null entries
49: @SuppressWarnings("unchecked")
50: TableEntry<K, V>[] temp = (TableEntry<K, V>[])new TableEntry[tableSize];
51: hashTable = temp;
52:
53: initialized = true;
54: } // end constructor
55:
56: /* < Implementations of methods in DictionaryInterface are here. >
57: . . .
58:
59: < Implementations of private methods are here. >
60: . . . */
61:
62: private class TableEntry<S, T>
63: {
64: private S key;
65: private T value;
66: private States state; // Flags whether this entry is in the hash table
67: private enum States {CURRENT, REMOVED} // Possible values of state
68:
69: private TableEntry(S searchKey, T dataValue)
70: {
71: key = searchKey;
72: value = dataValue;
73: state = States.CURRENT;
74: } // end constructor
75:
76: /* < The methods getKey, getValue, setValue, isIn, isRemoved, setToIn,
77: and setToRemoved are here. >
78: . . . */
79:
80: } // end TableEntry
81: } // end HashedDictionary