1 package org.apache.lucene.util.collections;
3 import java.util.Arrays;
4 import java.util.Iterator;
7 * Licensed to the Apache Software Foundation (ASF) under one or more
8 * contributor license agreements. See the NOTICE file distributed with
9 * this work for additional information regarding copyright ownership.
10 * The ASF licenses this file to You under the Apache License, Version 2.0
11 * (the "License"); you may not use this file except in compliance with
12 * the License. You may obtain a copy of the License at
14 * http://www.apache.org/licenses/LICENSE-2.0
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
24 * An Array-based hashtable which maps, similar to Java's HashMap, only
25 * performance tests showed it performs better.
27 * The hashtable is constructed with a given capacity, or 16 as a default. In
28 * case there's not enough room for new pairs, the hashtable grows. Capacity is
29 * adjusted to a power of 2, and there are 2 * capacity entries for the hash.
30 * The pre allocated arrays (for keys, values) are at length of capacity + 1,
31 * where index 0 is used as 'Ground' or 'NULL'.
33 * The arrays are allocated ahead of hash operations, and form an 'empty space'
34 * list, to which the <key,value> pair is allocated.
36 * @lucene.experimental
38 public class ArrayHashMap<K,V> implements Iterable<V> {
40 /** Implements an IntIterator which iterates over all the allocated indexes. */
41 private final class IndexIterator implements IntIterator {
43 * The last used baseHashIndex. Needed for "jumping" from one hash entry
46 private int baseHashIndex = 0;
48 /** The next not-yet-visited index. */
49 private int index = 0;
51 /** Index of the last visited pair. Used in {@link #remove()}. */
52 private int lastIndex = 0;
55 * Create the Iterator, make <code>index</code> point to the "first"
56 * index which is not empty. If such does not exist (eg. the map is
57 * empty) it would be zero.
59 public IndexIterator() {
60 for (baseHashIndex = 0; baseHashIndex < baseHash.length; ++baseHashIndex) {
61 index = baseHash[baseHashIndex];
68 public boolean hasNext() {
73 // Save the last index visited
79 // if the next index points to the 'Ground' it means we're done with
80 // the current hash entry and we need to jump to the next one. This
81 // is done until all the hash entries had been visited.
82 while (index == 0 && ++baseHashIndex < baseHash.length) {
83 index = baseHash[baseHashIndex];
89 @SuppressWarnings("unchecked")
90 public void remove() {
91 ArrayHashMap.this.remove((K) keys[lastIndex]);
96 /** Implements an Iterator, used for iteration over the map's keys. */
97 private final class KeyIterator implements Iterator<K> {
98 private IntIterator iterator = new IndexIterator();
102 public boolean hasNext() {
103 return iterator.hasNext();
106 @SuppressWarnings("unchecked")
108 return (K) keys[iterator.next()];
111 public void remove() {
116 /** Implements an Iterator, used for iteration over the map's values. */
117 private final class ValueIterator implements Iterator<V> {
118 private IntIterator iterator = new IndexIterator();
122 public boolean hasNext() {
123 return iterator.hasNext();
126 @SuppressWarnings("unchecked")
128 return (V) values[iterator.next()];
131 public void remove() {
136 /** Default capacity - in case no capacity was specified in the constructor */
137 private static final int DEFAULT_CAPACITY = 16;
140 * Holds the base hash entries. if the capacity is 2^N, than the base hash
146 * The current capacity of the map. Always 2^N and never less than 16. We
147 * never use the zero index. It is needed to improve performance and is also
150 private int capacity;
153 * All objects are being allocated at map creation. Those objects are "free"
154 * or empty. Whenever a new pair comes along, a pair is being "allocated" or
155 * taken from the free-linked list. as this is just a free list.
157 private int firstEmpty;
159 /** hashFactor is always (2^(N+1)) - 1. Used for faster hashing. */
160 private int hashFactor;
162 /** Holds the unique keys. */
166 * In case of collisions, we implement a double linked list of the colliding
167 * hash's with the following next[] and prev[]. Those are also used to store
174 /** Number of currently stored objects in the map. */
177 /** Holds the values. */
180 /** Constructs a map with default capacity. */
181 public ArrayHashMap() {
182 this(DEFAULT_CAPACITY);
186 * Constructs a map with given capacity. Capacity is adjusted to a native
187 * power of 2, with minimum of 16.
189 * @param capacity minimum capacity for the map.
191 public ArrayHashMap(int capacity) {
193 while (this.capacity < capacity) {
194 // Multiply by 2 as long as we're still under the requested capacity
198 // As mentioned, we use the first index (0) as 'Ground', so we need the
199 // length of the arrays to be one more than the capacity
200 int arrayLength = this.capacity + 1;
202 values = new Object[arrayLength];
203 keys = new Object[arrayLength];
204 next = new int[arrayLength];
206 // Hash entries are twice as big as the capacity.
207 int baseHashSize = this.capacity << 1;
209 baseHash = new int[baseHashSize];
211 // The has factor is 2^M - 1 which is used as an "AND" hashing operator.
212 // {@link #calcBaseHash()}
213 hashFactor = baseHashSize - 1;
221 * Adds a pair to the map. Takes the first empty position from the
222 * empty-linked-list's head - {@link firstEmpty}. New pairs are always
223 * inserted to baseHash, and are followed by the old colliding pair.
225 private void prvt_put(K key, V value) {
226 // Hash entry to which the new pair would be inserted
227 int hashIndex = calcBaseHashIndex(key);
229 // 'Allocating' a pair from the "Empty" list.
230 int objectIndex = firstEmpty;
233 firstEmpty = next[firstEmpty];
234 values[objectIndex] = value;
235 keys[objectIndex] = key;
237 // Inserting the new pair as the first node in the specific hash entry
238 next[objectIndex] = baseHash[hashIndex];
239 baseHash[hashIndex] = objectIndex;
241 // Announcing a new pair was added!
245 /** Calculating the baseHash index using the internal internal <code>hashFactor</code>. */
246 protected int calcBaseHashIndex(K key) {
247 return key.hashCode() & hashFactor;
250 /** Empties the map. Generates the "Empty" space list for later allocation. */
251 public void clear() {
252 // Clears the hash entries
253 Arrays.fill(baseHash, 0);
258 // Mark all array entries as empty. This is done with
259 // <code>firstEmpty</code> pointing to the first valid index (1 as 0 is
260 // used as 'Ground').
263 // And setting all the <code>next[i]</code> to point at
265 for (int i = 1; i < capacity;) {
269 // Surly, the last one should point to the 'Ground'.
273 /** Returns true iff the key exists in the map. */
274 public boolean containsKey(K key) {
275 return find(key) != 0;
278 /** Returns true iff the object exists in the map. */
279 public boolean containsValue(Object o) {
280 for (Iterator<V> iterator = iterator(); iterator.hasNext();) {
281 V object = iterator.next();
282 if (object.equals(o)) {
289 /** Returns the index of the given key, or zero if the key wasn't found. */
290 protected int find(K key) {
291 // Calculate the hash entry.
292 int baseHashIndex = calcBaseHashIndex(key);
294 // Start from the hash entry.
295 int localIndex = baseHash[baseHashIndex];
297 // while the index does not point to the 'Ground'
298 while (localIndex != 0) {
299 // returns the index found in case of of a matching key.
300 if (keys[localIndex].equals(key)) {
304 // next the local index
305 localIndex = next[localIndex];
308 // If we got this far, it could only mean we did not find the key we
309 // were asked for. return 'Ground' index.
314 * Finds the actual index of a given key with it's baseHashIndex. Some methods
315 * use the baseHashIndex. If those call {@link #find()} there's no need to
316 * re-calculate that hash.
318 * @return the index of the given key, or 0 if the key wasn't found.
320 private int findForRemove(K key, int baseHashIndex) {
321 // Start from the hash entry.
323 int index = baseHash[baseHashIndex];
325 // while the index does not point to the 'Ground'
327 // returns the index found in case of of a matching key.
328 if (keys[index].equals(key)) {
332 // next the local index
337 // If we got thus far, it could only mean we did not find the key we
338 // were asked for. return 'Ground' index.
342 /** Returns the object mapped with the given key, or null if the key wasn't found. */
343 @SuppressWarnings("unchecked")
344 public V get(K key) {
345 return (V) values[find(key)];
349 * Allocates a new map of double the capacity, and fast-insert the old
352 @SuppressWarnings("unchecked")
353 protected void grow() {
354 ArrayHashMap<K,V> newmap = new ArrayHashMap<K,V>(capacity * 2);
356 // Iterates fast over the collection. Any valid pair is put into the new
357 // map without checking for duplicates or if there's enough space for
359 for (IndexIterator iterator = new IndexIterator(); iterator.hasNext();) {
360 int index = iterator.next();
361 newmap.prvt_put((K) keys[index], (V) values[index]);
364 // Copy that's data into this.
365 capacity = newmap.capacity;
367 firstEmpty = newmap.firstEmpty;
368 values = newmap.values;
371 baseHash = newmap.baseHash;
372 hashFactor = newmap.hashFactor;
375 /** Returns true iff the map is empty. */
376 public boolean isEmpty() {
380 /** Returns an iterator on the mapped objects. */
381 public Iterator<V> iterator() {
382 return new ValueIterator();
385 /** Returns an iterator on the map keys. */
386 public Iterator<K> keyIterator() {
387 return new KeyIterator();
390 /** Prints the baseHash array, used for debugging purposes. */
391 @SuppressWarnings("unused")
392 private void printBaseHash() {
393 for (int i : baseHash) {
394 System.out.println(i + ".\t" + i);
399 * Inserts the <key,value> pair into the map. If the key already exists,
400 * this method updates the mapped value to the given one, returning the old
403 * @return the old mapped value, or null if the key didn't exist.
405 @SuppressWarnings("unchecked")
406 public V put(K key, V e) {
408 int index = find(key);
412 // Set new data and exit.
413 V old = (V) values[index];
418 // Is there enough room for a new pair?
419 if (size == capacity) {
424 // Now that everything is set, the pair can be just put inside with no
432 * Removes a <key,value> pair from the map and returns the mapped value,
433 * or null if the none existed.
435 * @param key used to find the value to remove
436 * @return the removed value or null if none existed.
438 @SuppressWarnings("unchecked")
439 public V remove(K key) {
440 int baseHashIndex = calcBaseHashIndex(key);
441 int index = findForRemove(key, baseHashIndex);
443 // If it is the first in the collision list, we should promote its
444 // next colliding element.
446 baseHash[baseHashIndex] = next[index];
449 next[prev] = next[index];
450 next[index] = firstEmpty;
453 return (V) values[index];
459 /** Returns number of pairs currently in the map. */
465 * Translates the mapped pairs' values into an array of Objects
467 * @return an object array of all the values currently in the map.
469 public Object[] toArray() {
471 Object[] array = new Object[size];
473 // Iterates over the values, adding them to the array.
474 for (Iterator<V> iterator = iterator(); iterator.hasNext();) {
475 array[++j] = iterator.next();
481 * Translates the mapped pairs' values into an array of V
483 * @param a the array into which the elements of the list are to be stored, if
484 * it is big enough; otherwise, use as much space as it can.
485 * @return an array containing the elements of the list
487 public V[] toArray(V[] a) {
489 // Iterates over the values, adding them to the array.
490 for (Iterator<V> iterator = iterator(); j < a.length
491 && iterator.hasNext(); ++j) {
492 a[j] = iterator.next();
502 public String toString() {
503 StringBuffer sb = new StringBuffer();
505 Iterator<K> keyIterator = keyIterator();
506 while (keyIterator.hasNext()) {
507 K key = keyIterator.next();
511 if (keyIterator.hasNext()) {
517 return sb.toString();
521 public int hashCode() {
522 return getClass().hashCode() ^ size();
525 @SuppressWarnings("unchecked")
527 public boolean equals(Object o) {
528 ArrayHashMap<K, V> that = (ArrayHashMap<K,V>)o;
529 if (that.size() != this.size()) {
533 Iterator<K> it = keyIterator();
534 while (it.hasNext()) {
536 V v1 = this.get(key);
537 V v2 = that.get(key);
538 if ((v1 == null && v2 != null) ||
539 (v1 != null && v2 == null) ||