View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5    * "License"); you may not use this file except in compliance with the License. You may obtain a
6    * copy of the License at:
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software distributed under the License
11   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12   * or implied. See the License for the specific language governing permissions and limitations under
13   * the License.
14   */
15  
16  package io.netty.util.collection;
17  
18  import java.lang.reflect.Array;
19  import java.util.AbstractCollection;
20  import java.util.Arrays;
21  import java.util.Collection;
22  import java.util.Iterator;
23  import java.util.NoSuchElementException;
24  
25  /**
26   * A hash map implementation of {@link IntObjectMap} that uses open addressing for keys.
27   * To minimize the memory footprint, this class uses open addressing rather than chaining.
28   * Collisions are resolved using linear probing. Deletions implement compaction, so cost of
29   * remove can approach O(N) for full maps, which makes a small loadFactor recommended.
30   *
31   * @param <V> The value type stored in the map.
32   */
33  public class IntObjectHashMap<V> implements IntObjectMap<V>, Iterable<IntObjectMap.Entry<V>> {
34  
35      /** Default initial capacity. Used if not specified in the constructor */
36      private static final int DEFAULT_CAPACITY = 11;
37  
38      /** Default load factor. Used if not specified in the constructor */
39      private static final float DEFAULT_LOAD_FACTOR = 0.5f;
40  
41      /**
42       * Placeholder for null values, so we can use the actual null to mean available.
43       * (Better than using a placeholder for available: less references for GC processing.)
44       */
45      private static final Object NULL_VALUE = new Object();
46  
47      /** The maximum number of elements allowed without allocating more space. */
48      private int maxSize;
49  
50      /** The load factor for the map. Used to calculate {@link #maxSize}. */
51      private final float loadFactor;
52  
53      private int[] keys;
54      private V[] values;
55      private Collection<V> valueCollection;
56      private int size;
57  
58      public IntObjectHashMap() {
59          this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
60      }
61  
62      public IntObjectHashMap(int initialCapacity) {
63          this(initialCapacity, DEFAULT_LOAD_FACTOR);
64      }
65  
66      public IntObjectHashMap(int initialCapacity, float loadFactor) {
67          if (initialCapacity < 1) {
68              throw new IllegalArgumentException("initialCapacity must be >= 1");
69          }
70          if (loadFactor <= 0.0f || loadFactor > 1.0f) {
71              // Cannot exceed 1 because we can never store more than capacity elements;
72              // using a bigger loadFactor would trigger rehashing before the desired load is reached.
73              throw new IllegalArgumentException("loadFactor must be > 0 and <= 1");
74          }
75  
76          this.loadFactor = loadFactor;
77  
78          // Adjust the initial capacity if necessary.
79          int capacity = adjustCapacity(initialCapacity);
80  
81          // Allocate the arrays.
82          keys = new int[capacity];
83          @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
84          V[] temp = (V[]) new Object[capacity];
85          values = temp;
86  
87          // Initialize the maximum size value.
88          maxSize = calcMaxSize(capacity);
89      }
90  
91      private static <T> T toExternal(T value) {
92          return value == NULL_VALUE ? null : value;
93      }
94  
95      @SuppressWarnings("unchecked")
96      private static <T> T toInternal(T value) {
97          return value == null ? (T) NULL_VALUE : value;
98      }
99  
100     @Override
101     public V get(int key) {
102         int index = indexOf(key);
103         return index == -1 ? null : toExternal(values[index]);
104     }
105 
106     @Override
107     public V put(int key, V value) {
108         int startIndex = hashIndex(key);
109         int index = startIndex;
110 
111         for (;;) {
112             if (values[index] == null) {
113                 // Found empty slot, use it.
114                 keys[index] = key;
115                 values[index] = toInternal(value);
116                 growSize();
117                 return null;
118             }
119             if (keys[index] == key) {
120                 // Found existing entry with this key, just replace the value.
121                 V previousValue = values[index];
122                 values[index] = toInternal(value);
123                 return toExternal(previousValue);
124             }
125 
126             // Conflict, keep probing ...
127             if ((index = probeNext(index)) == startIndex) {
128                 // Can only happen if the map was full at MAX_ARRAY_SIZE and couldn't grow.
129                 throw new IllegalStateException("Unable to insert");
130             }
131         }
132     }
133 
134     private int probeNext(int index) {
135         return index == values.length - 1 ? 0 : index + 1;
136     }
137 
138     @Override
139     public void putAll(IntObjectMap<V> sourceMap) {
140         if (sourceMap instanceof IntObjectHashMap) {
141             // Optimization - iterate through the arrays.
142             IntObjectHashMap<V> source = (IntObjectHashMap<V>) sourceMap;
143             for (int i = 0; i < source.values.length; ++i) {
144                 V sourceValue = source.values[i];
145                 if (sourceValue != null) {
146                     put(source.keys[i], sourceValue);
147                 }
148             }
149             return;
150         }
151 
152         // Otherwise, just add each entry.
153         for (Entry<V> entry : sourceMap.entries()) {
154             put(entry.key(), entry.value());
155         }
156     }
157 
158     @Override
159     public V remove(int key) {
160         int index = indexOf(key);
161         if (index == -1) {
162             return null;
163         }
164 
165         V prev = values[index];
166         removeAt(index);
167         return toExternal(prev);
168     }
169 
170     @Override
171     public int size() {
172         return size;
173     }
174 
175     @Override
176     public boolean isEmpty() {
177         return size == 0;
178     }
179 
180     @Override
181     public void clear() {
182         Arrays.fill(keys, 0);
183         Arrays.fill(values, null);
184         size = 0;
185     }
186 
187     @Override
188     public boolean containsKey(int key) {
189         return indexOf(key) >= 0;
190     }
191 
192     @Override
193     public boolean containsValue(V value) {
194         V v1 = toInternal(value);
195         for (V v2 : values) {
196             // The map supports null values; this will be matched as NULL_VALUE.equals(NULL_VALUE).
197             if (v2 != null && v2.equals(v1)) {
198                 return true;
199             }
200         }
201         return false;
202     }
203 
204     @Override
205     public Iterable<Entry<V>> entries() {
206         return this;
207     }
208 
209     @Override
210     public Iterator<Entry<V>> iterator() {
211         return new IteratorImpl();
212     }
213 
214     @Override
215     public int[] keys() {
216         int[] outKeys = new int[size()];
217         int targetIx = 0;
218         for (int i = 0; i < values.length; ++i) {
219             if (values[i] != null) {
220                 outKeys[targetIx++] = keys[i];
221             }
222         }
223         return outKeys;
224     }
225 
226     @Override
227     public V[] values(Class<V> clazz) {
228         @SuppressWarnings("unchecked")
229         V[] outValues = (V[]) Array.newInstance(clazz, size());
230         int targetIx = 0;
231         for (V value : values) {
232             if (value != null) {
233                 outValues[targetIx++] = value;
234             }
235         }
236         return outValues;
237     }
238 
239     @Override
240     public Collection<V> values() {
241         Collection<V> valueCollection = this.valueCollection;
242         if (valueCollection == null) {
243             this.valueCollection = valueCollection = new AbstractCollection<V>() {
244                 @Override
245                 public Iterator<V> iterator() {
246                     return new Iterator<V>() {
247                         final Iterator<Entry<V>> iter = IntObjectHashMap.this.iterator();
248                         @Override
249                         public boolean hasNext() {
250                             return iter.hasNext();
251                         }
252 
253                         @Override
254                         public V next() {
255                             return iter.next().value();
256                         }
257 
258                         @Override
259                         public void remove() {
260                             throw new UnsupportedOperationException();
261                         }
262                     };
263                 }
264 
265                 @Override
266                 public int size() {
267                     return size;
268                 }
269             };
270         }
271 
272         return valueCollection;
273     }
274 
275     @Override
276     public int hashCode() {
277         // Hashcode is based on all non-zero, valid keys. We have to scan the whole keys
278         // array, which may have different lengths for two maps of same size(), so the
279         // capacity cannot be used as input for hashing but the size can.
280         int hash = size;
281         for (int key : keys) {
282             // 0 can be a valid key or unused slot, but won't impact the hashcode in either case.
283             // This way we can use a cheap loop without conditionals, or hard-to-unroll operations,
284             // or the devastatingly bad memory locality of visiting value objects.
285             // Also, it's important to use a hash function that does not depend on the ordering
286             // of terms, only their values; since the map is an unordered collection and
287             // entries can end up in different positions in different maps that have the same
288             // elements, but with different history of puts/removes, due to conflicts.
289             hash ^= key;
290         }
291         return hash;
292     }
293 
294     @Override
295     public boolean equals(Object obj) {
296         if (this == obj) {
297             return true;
298         }
299         if (!(obj instanceof IntObjectMap)) {
300             return false;
301         }
302         @SuppressWarnings("rawtypes")
303         IntObjectMap other = (IntObjectMap) obj;
304         if (size != other.size()) {
305             return false;
306         }
307         for (int i = 0; i < values.length; ++i) {
308             V value = values[i];
309             if (value != null) {
310                 int key = keys[i];
311                 Object otherValue = other.get(key);
312                 if (value == NULL_VALUE) {
313                     if (otherValue != null) {
314                       return false;
315                     }
316                 } else if (!value.equals(otherValue)) {
317                     return false;
318                 }
319             }
320         }
321         return true;
322     }
323 
324     /**
325      * Locates the index for the given key. This method probes using double hashing.
326      *
327      * @param key the key for an entry in the map.
328      * @return the index where the key was found, or {@code -1} if no entry is found for that key.
329      */
330     private int indexOf(int key) {
331         int startIndex = hashIndex(key);
332         int index = startIndex;
333 
334         for (;;) {
335             if (values[index] == null) {
336                 // It's available, so no chance that this value exists anywhere in the map.
337                 return -1;
338             }
339             if (key == keys[index]) {
340                 return index;
341             }
342 
343             // Conflict, keep probing ...
344             if ((index = probeNext(index)) == startIndex) {
345                 return -1;
346             }
347         }
348     }
349 
350     /**
351      * Returns the hashed index for the given key.
352      */
353     private int hashIndex(int key) {
354         // Allowing for negative keys by adding the length after the first mod operation.
355         return (key % keys.length + keys.length) % keys.length;
356     }
357 
358     /**
359      * Grows the map size after an insertion. If necessary, performs a rehash of the map.
360      */
361     private void growSize() {
362         size++;
363 
364         if (size > maxSize) {
365             // Need to grow the arrays. We take care to detect integer overflow,
366             // also limit array size to ArrayList.MAX_ARRAY_SIZE.
367             rehash(adjustCapacity((int) Math.min(keys.length * 2.0, Integer.MAX_VALUE - 8)));
368         } else if (size == keys.length) {
369             // Open addressing requires that we have at least 1 slot available. Need to refresh
370             // the arrays to clear any removed elements.
371             rehash(keys.length);
372         }
373     }
374 
375     /**
376      * Adjusts the given capacity value to ensure that it's odd. Even capacities can break probing.
377      */
378     private static int adjustCapacity(int capacity) {
379         return capacity | 1;
380     }
381 
382     /**
383      * Removes entry at the given index position. Also performs opportunistic, incremental rehashing
384      * if necessary to not break conflict chains.
385      *
386      * @param index the index position of the element to remove.
387      */
388     private void removeAt(int index) {
389         --size;
390         // Clearing the key is not strictly necessary (for GC like in a regular collection),
391         // but recommended for security. The memory location is still fresh in the cache anyway.
392         keys[index] = 0;
393         values[index] = null;
394 
395         // In the interval from index to the next available entry, the arrays may have entries
396         // that are displaced from their base position due to prior conflicts. Iterate these
397         // entries and move them back if possible, optimizing future lookups.
398         // Knuth Section 6.4 Algorithm R, also used by the JDK's IdentityHashMap.
399 
400         int nextFree = index;
401         for (int i = probeNext(index); values[i] != null; i = probeNext(i)) {
402             int bucket = hashIndex(keys[i]);
403             if (i < bucket && (bucket <= nextFree || nextFree <= i) ||
404                 bucket <= nextFree && nextFree <= i) {
405                 // Move the displaced entry "back" to the first available position.
406                 keys[nextFree] = keys[i];
407                 values[nextFree] = values[i];
408                 // Put the first entry after the displaced entry
409                 keys[i] = 0;
410                 values[i] = null;
411                 nextFree = i;
412             }
413         }
414     }
415 
416     /**
417      * Calculates the maximum size allowed before rehashing.
418      */
419     private int calcMaxSize(int capacity) {
420         // Clip the upper bound so that there will always be at least one available slot.
421         int upperBound = capacity - 1;
422         return Math.min(upperBound, (int) (capacity * loadFactor));
423     }
424 
425     /**
426      * Rehashes the map for the given capacity.
427      *
428      * @param newCapacity the new capacity for the map.
429      */
430     private void rehash(int newCapacity) {
431         int[] oldKeys = keys;
432         V[] oldVals = values;
433 
434         keys = new int[newCapacity];
435         @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
436         V[] temp = (V[]) new Object[newCapacity];
437         values = temp;
438 
439         maxSize = calcMaxSize(newCapacity);
440 
441         // Insert to the new arrays.
442         for (int i = 0; i < oldVals.length; ++i) {
443             V oldVal = oldVals[i];
444             if (oldVal != null) {
445                 // Inlined put(), but much simpler: we don't need to worry about
446                 // duplicated keys, growing/rehashing, or failing to insert.
447                 int oldKey = oldKeys[i];
448                 int index = hashIndex(oldKey);
449 
450                 for (;;) {
451                     if (values[index] == null) {
452                         keys[index] = oldKey;
453                         values[index] = toInternal(oldVal);
454                         break;
455                     }
456 
457                     // Conflict, keep probing. Can wrap around, but never reaches startIndex again.
458                     index = probeNext(index);
459                 }
460             }
461         }
462     }
463 
464     /**
465      * Iterator for traversing the entries in this map.
466      */
467     private final class IteratorImpl implements Iterator<Entry<V>>, Entry<V> {
468         private int prevIndex = -1;
469         private int nextIndex = -1;
470         private int entryIndex = -1;
471 
472         private void scanNext() {
473             for (;;) {
474                 if (++nextIndex == values.length || values[nextIndex] != null) {
475                     break;
476                 }
477             }
478         }
479 
480         @Override
481         public boolean hasNext() {
482             if (nextIndex == -1) {
483                 scanNext();
484             }
485             return nextIndex < keys.length;
486         }
487 
488         @Override
489         public Entry<V> next() {
490             if (!hasNext()) {
491                 throw new NoSuchElementException();
492             }
493 
494             prevIndex = nextIndex;
495             scanNext();
496 
497             // Always return the same Entry object, just change its index each time.
498             entryIndex = prevIndex;
499             return this;
500         }
501 
502         @Override
503         public void remove() {
504             if (prevIndex < 0) {
505                 throw new IllegalStateException("next must be called before each remove.");
506             }
507             removeAt(prevIndex);
508             prevIndex = -1;
509         }
510 
511         // Entry implementation. Since this implementation uses a single Entry, we coalesce that
512         // into the Iterator object (potentially making loop optimization much easier).
513 
514         @Override
515         public int key() {
516             return keys[entryIndex];
517         }
518 
519         @Override
520         public V value() {
521             return toExternal(values[entryIndex]);
522         }
523 
524         @Override
525         public void setValue(V value) {
526             values[entryIndex] = toInternal(value);
527         }
528     }
529 
530     @Override
531     public String toString() {
532         if (size == 0) {
533             return "{}";
534         }
535         StringBuilder sb = new StringBuilder(4 * size);
536         for (int i = 0; i < values.length; ++i) {
537             V value = values[i];
538             if (value != null) {
539                 sb.append(sb.length() == 0 ? "{" : ", ");
540                 sb.append(keyToString(keys[i])).append('=').append(value == this ? "(this Map)" : value);
541             }
542         }
543         return sb.append('}').toString();
544     }
545 
546     /**
547      * Helper method called by {@link #toString()} in order to convert a single map key into a string.
548      */
549     protected String keyToString(int key) {
550         return Integer.toString(key);
551     }
552 }