1 /*
2 * Copyright (c) 1994, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.lang;
27
28 import java.util.Arrays;
29
30 /**
31 * Linear-probe hash table.
32 * <p/>
33 * Modeled by the {@link java.util.IdentityHashMap}, but using overriddable
34 * {@link #equals(Object, Object) equals} / {@link #hashCode(Object) hashCode}
35 * to compare/locate elements. The API of this class is similar
36 * in function and form to {@link java.util.Map}, but doesn't use separate keys
37 * and values. In this API an <b>element</b> is a key and a value at the same time.
38 * An element is always non-null, so the return values are unambiguous.
39 * <p/>
40 * Because this is a linear-probe hash table and there are no
41 * {@link java.util.Map.Entry} objects involved, the underlying
42 * data structure is very simple and memory efficient.
43 * It is just a sparse array of elements with length that
44 * is always a power of two and larger than 3 * {@link #size()} / 2.
45 *
46 * @param <T> Type of elements contained in the HashArray.
47 */
48 class HashArray<T> {
49 /**
50 * The minimum capacity, used if a lower value is implicitly specified.
51 * The value 2 corresponds to an expected maximum size of 1,
52 * given a load factor of 2/3. MUST be a power of two.
53 */
54 private static final int MINIMUM_CAPACITY = 2;
55
56 /**
57 * The maximum capacity.
58 * <p/>
59 * In fact, the HashArray can hold no more than MAXIMUM_CAPACITY-1 elements
60 * because it has to have at least one slot == null
61 * in order to avoid infinite loops in get() and put().
62 */
63 private static final int MAXIMUM_CAPACITY = 1 << 30;
64
65 /**
66 * The table, re-sized as necessary.
67 * Length MUST always be a power of two.
68 */
69 private T[] table;
70
71 /**
72 * The number of elements contained in this HashArray.
73 */
74 private int size;
75
76 /**
77 * Constructor with {@code expectedSize} pre-allocates the
78 * {@link #table}.
79 *
80 * @param expectedMaxSize expected number of elements new HashArray
81 * will hold.
82 */
83 @SuppressWarnings("unchecked")
84 public HashArray(int expectedMaxSize) {
85 if (expectedMaxSize < 0)
86 throw new IllegalArgumentException("expectedMaxSize is negative: "
87 + expectedMaxSize);
88 table = (T[]) new Object[capacity(expectedMaxSize)];
89 }
90
91 /**
92 * Returns the appropriate capacity for the given expected maximum size.
93 * Returns the smallest power of two between MINIMUM_CAPACITY and
94 * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
95 * expectedMaxSize)/2, if such a number exists. Otherwise returns
96 * MAXIMUM_CAPACITY.
97 */
98 private static int capacity(int expectedMaxSize) {
99 // assert expectedMaxSize >= 0;
100 return
101 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
102 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
103 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
104 }
105
106 /**
107 * Returns a hash code value for an element of this HashArray or a
108 * lookup object.
109 * <p/>
110 * By default it returns:
111 * <pre>
112 * obj.{@link Object#hashCode() hashCode()}
113 * </pre>
114 * But can be overridden in subclasses.
115 *
116 * @param obj an element of this HashArray or a lookup object
117 * @return a hash code value for an element or lookup object.
118 * @see #equals(Object, Object)
119 */
120 protected int hashCode(Object obj) {
121 return obj.hashCode();
122 }
123
124 /**
125 * Indicates whether an element of this HashArray is "equal to"
126 * a lookup object or another element.
127 * <p/>
128 * By default it returns:
129 * <pre>
130 * element.{@link Object#equals(Object) equals(obj)}
131 * </pre>
132 * But can be overridden in subclasses.
133 *
134 * @param element an element of this HashArray
135 * @param obj a lookup object or another element
136 * @return {@code true} if an element is the same
137 * as a lookup object or another element;
138 * {@code false} otherwise.
139 * @see #hashCode(Object)
140 */
141 protected boolean equals(T element, Object obj) {
142 return element.equals(obj);
143 }
144
145 /**
146 * Returns index for Object x.
147 */
148 private int hash(Object x, int length) {
149 int h = hashCode(x);
150 return (h ^ (h >>> 16)) & (length - 1);
151 }
152
153 /**
154 * Circularly traverses table of size length (which is a power of 2).
155 */
156 private static int nextKeyIndex(int i, int length) {
157 return (i + 1) & (length - 1);
158 }
159
160 /**
161 * @return Number of elements contained in this HashArray.
162 */
163 public int size() {
164 return size;
165 }
166
167 /**
168 * @param lookupObj a non-null lookup object
169 * @return The element which is equal to specified {@code lookupObj}
170 * if it exists in this HashArray or null if it doesn't.
171 * (There can be at most one such element.)
172 * @throws NullPointerException if {@code lookupObj} is null
173 */
174 @SuppressWarnings("unchecked")
175 public T get(Object lookupObj) {
176 if (lookupObj == null) throw new NullPointerException();
177 final T[] tab = table;
178 int i = hash(lookupObj, tab.length);
179 while (true) {
180 T element = tab[i];
181 if (element == null) {
182 return null;
183 }
184 if (equals(element, lookupObj)) {
185 return element;
186 }
187 i = nextKeyIndex(i, tab.length);
188 }
189 }
190
191 /**
192 * Adds {@code newElement} if an element equal to it is not present in
193 * this HashArray and returns null, or returns the existing element and
194 * replaces it with {@code newElement} if such element is present.
195 *
196 * @param newElement new element to put into this HashArray
197 * @return previous element if there was one or null if there was none
198 */
199 public T put(T newElement) {
200 return put(newElement, true);
201 }
202
203 /**
204 * Adds {@code newElement} if an element equal to it is not present in
205 * this HashArray and returns null, or returns the existing element and
206 * doesn't modify HashArray if such element is present.
207 *
208 * @param newElement new element to put into this HashArray
209 * @return previous element if there was one or null if there was none
210 */
211 public T putIfAbsent(T newElement) {
212 return put(newElement, false);
213 }
214
215 private T put(T newElement, boolean replace) {
216 if (newElement == null) throw new NullPointerException();
217 for (; ; ) {
218 final T[] tab = table;
219 int i = hash(newElement, tab.length);
220
221 for (
222 T element; (element = tab[i]) != null;
223 i = nextKeyIndex(i, tab.length)
224 ) {
225 if (equals(element, newElement)) {
226 if (replace) {
227 tab[i] = newElement;
228 }
229 return element;
230 }
231 }
232
233 final int s = size + 1;
234 // Use optimized form of 3 * s / 2.
235 // Next capacity is 2 * current capacity.
236 if (s + (s >> 1) > tab.length && resize(tab.length << 1))
237 continue;
238
239 tab[i] = newElement;
240 size = s;
241 return null;
242 }
243 }
244
245 /**
246 * Resizes the table if necessary to hold given capacity.
247 */
248 private boolean resize(int newLength) {
249 T[] oldTable = table;
250 int oldLength = oldTable.length;
251 if (oldLength == MAXIMUM_CAPACITY) { // can't expand any further
252 if (size == MAXIMUM_CAPACITY - 1)
253 throw new IllegalStateException("Capacity exhausted.");
254 return false;
255 }
256 if (oldLength >= newLength)
257 return false;
258
259 @SuppressWarnings("unchecked")
260 T[] newTable = (T[]) new Object[newLength];
261
262 for (int j = 0; j < oldLength; j++) {
263 T element = oldTable[j];
264 if (element != null) {
265 oldTable[j] = null;
266 int i = hash(element, newLength);
267 while (newTable[i] != null)
268 i = nextKeyIndex(i, newLength);
269 newTable[i] = element;
270 }
271 }
272 table = newTable;
273 return true;
274 }
275
276 /**
277 * Removes the element equal to {@code lookupObj} and
278 * returns it if present or returns null if not present.
279 *
280 * @param lookupObj a non-null lookup object
281 * @return the removed element if there was one or null if
282 * there was none
283 * @throws NullPointerException if {@code lookupObj} is null
284 */
285 public T remove(Object lookupObj) {
286 if (lookupObj == null) throw new NullPointerException();
287 T[] tab = table;
288 int i = hash(lookupObj, tab.length);
289
290 while (true) {
291 T element = tab[i];
292 if (element == null) {
293 return null;
294 }
295 if (equals(element, lookupObj)) {
296 size--;
297 tab[i] = null;
298 closeDeletion(tab, i);
299 return element;
300 }
301 i = nextKeyIndex(i, tab.length);
302 }
303 }
304
305 /**
306 * Rehash all possibly-colliding elements following a
307 * deletion. This preserves the linear-probe
308 * collision properties required by get, putIfAbsent, remove.
309 *
310 * @param d the index of a newly empty deleted slot
311 */
312 private void closeDeletion(Object[] tab, int d) {
313 // Adapted from Knuth Section 6.4 Algorithm R
314
315 // Look for elements to swap into newly vacated slot
316 // starting at index immediately following deletion,
317 // and continuing until a null slot is seen, indicating
318 // the end of a run of possibly-colliding elements.
319 Object element;
320 for (
321 int i = nextKeyIndex(d, tab.length); (element = tab[i]) != null;
322 i = nextKeyIndex(i, tab.length)
323 ) {
324 // The following test triggers if the element at slot i (which
325 // hashes to be at slot r) should take the spot vacated by d.
326 // If so, we swap it in, and then continue with d now at the
327 // newly vacated i. This process will terminate when we hit
328 // the null slot at the end of this run.
329 // The test is messy because we are using a circular table.
330 int r = hash(element, tab.length);
331 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
332 tab[d] = element;
333 tab[i] = null;
334 d = i;
335 }
336 }
337 }
338
339 /**
340 * Removes all of the elements from this HashArray.
341 */
342 public void clear() {
343 Arrays.fill(table, null);
344 size = 0;
345 }
346 }