public class ChainingHashTable extends HashTable
1: //ChainingHashTable.java (from zyDE 5.10.1)
3: public class ChainingHashTable extends HashTable
4: {
5: private ChainingHashTableItem[] table;
7: public ChainingHashTable(int initialCapacity)
8: {
9: table = new ChainingHashTableItem[initialCapacity];
10: }
12: public ChainingHashTable()
13: {
14: // Initialize with an initial capacity of 11
15: this(11);
16: }
18: // Inserts the specified key/value pair. If the key already exists,
19: // the corresponding value is updated. If inserted or updated, true
20: // is returned. If not inserted, then false is returned.
21: @Override
22: public boolean insert(Object key, Object value)
23: {
24: // Hash the key to get the bucket index
25: int bucketIndex = hash(key) % table.length;
27: // Traverse the linked list, searching for the key. If the key exists
28: // in an item, the value is replaced. Otherwise a new item is appended.
29: ChainingHashTableItem item = table[bucketIndex];
30: ChainingHashTableItem previous = null;
31: while (item != null)
32: {
33: if (key.equals(item.key))
34: {
35: item.value = value;
36: return true;
37: }
39: previous = item;
40: item = item.next;
41: }
43: // Append to the linked list
44: if (table[bucketIndex] == null)
45: {
46: table[bucketIndex] = new ChainingHashTableItem(key, value);
47: }
48: else
49: {
50: previous.next = new ChainingHashTableItem(key, value);
51: }
52: return true;
53: }
55: // Searches for the specified key. If found, the key/value pair is removed
56: // from the hash table and true is returned. Otherwise, false is returned.
57: @Override
58: public boolean remove(Object key)
59: {
60: // Hash the key to get the bucket index
61: int bucketIndex = hash(key) % table.length;
63: // Search the bucket's linked list for the key
64: ChainingHashTableItem item = table[bucketIndex];
65: ChainingHashTableItem previous = null;
66: while (item != null)
67: {
68: if (key.equals(item.key))
69: {
70: if (previous == null)
71: {
72: // Remove linked list's first item
73: table[bucketIndex] = item.next;
74: }
75: else
76: {
77: previous.next = item.next;
78: }
79: return true;
80: }
82: previous = item;
83: item = item.next;
84: }
86: return false; // key not found
87: }
89: // Searches for the key, returning the corresponding value if found,
90: // null if not found.
91: @Override
92: public Object search(Object key)
93: {
94: // Hash the key to get the bucket index
95: int bucketIndex = hash(key) % table.length;
97: // Search the bucket's linked list for the key
98: ChainingHashTableItem item = table[bucketIndex];
99: while (item != null)
100: {
101: if (key.equals(item.key))
102: {
103: return item.value;
104: }
105: item = item.next;
106: }
108: return null; // key not found
109: }
111: @Override
112: public String toString()
113: {
114: String result = "";
115: for (int i = 0; i < table.length; i++)
116: {
117: result += (i + ": ");
119: if (table[i] == null)
120: {
121: result += "(empty)\n";
122: }
123: else
124: {
125: ChainingHashTableItem item = table[i];
126: while (item != null)
127: {
128: result += String.format("%s, %s --> ", item.key.toString(),
129: item.value.toString());
130: item = item.next;
131: }
132: result += "\n";
133: }
134: }
135: return result;
136: }
137: }