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