1: //OpenAddressingHashTable.java (from zyDE 5.10.1)
3: public abstract class OpenAddressingHashTable extends HashTable
4: {
5: protected OpenAddressingBucket[] table;
7: public OpenAddressingHashTable(int initialCapacity)
8: {
9: table = new OpenAddressingBucket[initialCapacity];
10: for (int i = 0; i < table.length; i++)
11: {
12: table[i] = OpenAddressingBucket.EMPTY_SINCE_START;
13: }
14: }
16: protected abstract int probe(Object key, int i);
18: // Inserts the specified key/value pair. If the key already exists, the
19: // corresponding value is updated. If inserted or updated, true is returned.
20: // If not inserted, then false is returned.
21: @Override
22: public boolean insert(Object key, Object value)
23: {
24: // First search for the key in the table. If found, update bucket's value.
25: for (int i = 0; i < table.length; i++)
26: {
27: int bucketIndex = probe(key, i);
29: // An empty-since-start bucket implies the key is not in the table
30: if (table[bucketIndex] == OpenAddressingBucket.EMPTY_SINCE_START)
31: {
32: break;
33: }
35: if (table[bucketIndex] != OpenAddressingBucket.EMPTY_AFTER_REMOVAL)
36: {
37: // Check if the non-empty bucket has the key
38: if (key.equals(table[bucketIndex].key))
39: {
40: // Update the value
41: table[bucketIndex].value = value;
42: return true;
43: }
44: }
45: }
47: // The key is not in the table, so insert into first empty bucket
48: for (int i = 0; i < table.length; i++)
49: {
50: int bucketIndex = probe(key, i);
51: if (table[bucketIndex].isEmpty())
52: {
53: table[bucketIndex] = new OpenAddressingBucket(key, value);
54: return true;
55: }
56: }
58: return false; // no empty bucket found
59: }
61: // Searches for the specified key. If found, the key/value pair is removed
62: // from the hash table and true is returned. If not found, false is returned.
63: @Override
64: public boolean remove(Object key)
65: {
66: for (int i = 0; i < table.length; i++)
67: {
68: int bucketIndex = probe(key, i);
70: // An empty-since-start bucket implies the key is not in the table
71: if (table[bucketIndex] == OpenAddressingBucket.EMPTY_SINCE_START)
72: {
73: return false;
74: }
76: if (table[bucketIndex] != OpenAddressingBucket.EMPTY_AFTER_REMOVAL)
77: {
78: // Check if the non-empty bucket has the key
79: if (key.equals(table[bucketIndex].key))
80: {
81: // Remove by setting the bucket to empty-after-removal
82: table[bucketIndex] = OpenAddressingBucket.EMPTY_AFTER_REMOVAL;
83: return true;
84: }
85: }
86: }
88: return false; // key not found
89: }
91: // Searches for the key, returning the corresponding value if found, null if
92: // not found.
93: @Override
94: public Object search(Object key)
95: {
96: for (int i = 0; i < table.length; i++)
97: {
98: int bucketIndex = probe(key, i);
100: // An empty-since-start bucket implies the key is not in the table
101: if (table[bucketIndex] == OpenAddressingBucket.EMPTY_SINCE_START)
102: {
103: return null;
104: }
106: if (table[bucketIndex] != OpenAddressingBucket.EMPTY_AFTER_REMOVAL)
107: {
108: // Check if the non-empty bucket has the key
109: if (key.equals(table[bucketIndex].key))
110: {
111: return table[bucketIndex].value;
112: }
113: }
114: }
116: return null; // key not found
117: }
119: @Override
120: public String toString()
121: {
122: String result = "";
123: for (int i = 0; i < table.length; i++)
124: {
125: result += (i + ": ");
126: if (table[i] == OpenAddressingBucket.EMPTY_SINCE_START)
127: {
128: result += "EMPTY_SINCE_START\n";
129: }
130: else if (table[i] == OpenAddressingBucket.EMPTY_AFTER_REMOVAL)
131: {
132: result += "EMPTY_AFTER_REMOVAL\n";
133: }
134: else
135: {
136: result += String.format("%s, %s\n", table[i].key.toString(),
137: table[i].value.toString());
138: }
139: }
140: return result;
141: }
142: }