1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
package com.jclark.util;
/**
* A more efficient version of <code>java.util.Hashtable</code>
* It is not synchronized. It only performs allocation when
* the hash table is resized.
*/
public class Hashtable extends java.util.Dictionary {
// The first half of table contains the keys, the second half the values.
// The value for a key at index i is at index i + halfTableLength
private Object[] table;
private int halfTableLength;
private int used;
private int usedLimit;
private static final int INIT_SIZE = 16;
private static final float LOAD_FACTOR = 0.5f;
private final int nextIndex(int i) {
return i == 0 ? halfTableLength - 1 : i - 1;
}
// It might be a good idea to multiple the hashCode by a large prime.
private final int firstIndex(Object key) {
return key.hashCode() & (halfTableLength - 1);
}
public Hashtable() { }
/**
* Creates a hash table with the specified initial capacity.
*/
public Hashtable(int n) {
n = (int)((n + 1)/LOAD_FACTOR);
halfTableLength = 1;
while (halfTableLength < n)
halfTableLength <<= 1;
table = new Object[halfTableLength << 1];
usedLimit = (int)(n * LOAD_FACTOR);
}
public final int size() {
return used;
}
public final boolean isEmpty() {
return used == 0;
}
public final Object get(Object key) {
if (used != 0) {
for (int i = firstIndex(key); table[i] != null; i = nextIndex(i))
if (table[i].equals(key))
return table[i | halfTableLength];
}
return null;
}
public final Object put(Object key, Object value) {
if (value == null)
throw new NullPointerException();
int h;
if (table == null) {
table = new Object[INIT_SIZE];
halfTableLength = INIT_SIZE >> 1;
usedLimit = (int)((INIT_SIZE >> 1) * LOAD_FACTOR);
h = firstIndex(key);
}
else {
for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
if (key.equals(table[h])) {
h |= halfTableLength;
Object tem = table[h];
table[h] = value;
return tem;
}
}
if (used >= usedLimit) {
// rehash
halfTableLength = table.length;
usedLimit = (int)(halfTableLength * LOAD_FACTOR);
Object[] oldTable = table;
table = new Object[halfTableLength << 1];
for (int i = oldTable.length >> 1; i > 0;) {
--i;
if (oldTable[i] != null) {
int j;
for (j = firstIndex(oldTable[i]); table[j] != null; j = nextIndex(j))
;
table[j] = oldTable[i];
// copy the value
table[j | halfTableLength] = oldTable[i + (oldTable.length >> 1)];
}
}
for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
;
}
used++;
table[h] = key;
table[h | halfTableLength] = value;
return null;
}
private static class Enumerator implements java.util.Enumeration {
private final Object[] table;
private final int add;
private int i;
Enumerator(Object[] table, int add) {
this.table = table;
this.add = add;
if (table == null)
i = -1;
else {
i = (table.length >> 1);
while (--i >= 0 && table[i] == null)
;
}
}
public boolean hasMoreElements() {
return i >= 0;
}
public Object nextElement() {
if (i < 0)
throw new java.util.NoSuchElementException();
Object tem = table[i + add];
while (--i >= 0 && table[i] == null)
;
return tem;
}
}
public final java.util.Enumeration keys() {
return new Enumerator(table, 0);
}
public final java.util.Enumeration elements() {
return new Enumerator(table, halfTableLength);
}
/**
* Removes the object with the specified key from the table.
* Returns the object removed or null if there was no such object
* in the table.
*/
public final Object remove(Object key) {
if (used > 0) {
for (int i = firstIndex(key); table[i] != null; i = nextIndex(i))
if (table[i].equals(key)) {
Object obj = table[i];
do {
table[i] = null;
table[i | halfTableLength] = null;
int j = i;
int r;
do {
i = nextIndex(i);
if (table[i] == null)
break;
r = firstIndex(table[i]);
} while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
table[j] = table[i];
table[j | halfTableLength] = table[i | halfTableLength];
} while (table[i] != null);
--used;
return obj;
}
}
return null;
}
/**
* Removes all objects from the hash table, so that the hash table
* becomes empty.
*/
public final void clear() {
int i = halfTableLength;
while (--i >= 0) {
table[i] = null;
table[i | halfTableLength] = null;
}
used = 0;
}
}
|
