前言

参考SpringSide-Util中提到的特殊Map，在特殊场景中性能较HashMap更优。IntObjectHashMap移植自Netty的工具类中，旨在优化性能。
IntObjectHashMap采用Int类型的开放地址而非使用链表来设计Key, 减少内存占用. 在数组中使用线性探测来解决Hash冲突。删除节点时需要压缩数组，
因此时间消耗解决O(N), 因此推荐使用偏小的负载因子(默认0.5)

源码解读

接口设计

  1. public interface IntObjectMap<V> extends Map<Integer, V> {
  3.     /**
  4.      * 基础Int类型的Entry
  5.      */
  6.     interface PrimitiveEntry<V> {
  8.         int key();
  10.         V value();
  12.         void setValue(V value);
  13.     }
  14.   }
  16. V get(int key);
  18. V put(int key, V value);
  20. V remove(int key);
  22. Iterable<PrimitiveEntry<V>> entries();
  24. boolean containsKey(int key);

IntObjectHashMap源码解释

  2. public class IntObjectHashMap<V> implements IntObjectMap<V> {
  4.   默认初始容量为8
  5.     public static final int DEFAULT_CAPACITY = 8;
  7.   默认加载因子
  8.     public static final float DEFAULT_LOAD_FACTOR = 0.5f;
  10.   null值的占位符,避免在数组中存储null.
  11.     private static final Object NULL_VALUE = new Object();
  13.   最大的容量
  14.     private int maxSize;
  16.   加载因子
  17.     private final float loadFactor;
  19.   Key数组
  20.     private int[] keys;
  22.   Value数组
  23.     private V[] values;
  25.   实际元素数量，Map的大小
  26.     private int size;
  28.   掩码,大小为数组的length-1, 用以与hash值作与运算, 比直接取模性能更加
  29.     private int mask;
  31.   Key视图
  32.     private final Set<Integer> keySet = new KeySet();
  34.   Entry视图
  35.     private final Set<Entry<Integer, V>> entrySet = new EntrySet();
  37.   当前Map迭代器
  38.     private final Iterable<PrimitiveEntry<V>> entries = new Iterable<PrimitiveEntry<V>>() {
  39.         @Override
  40.         public Iterator<PrimitiveEntry<V>> iterator() {
  41.             return new PrimitiveIterator();
  42.         }
  43.     };
  45.   默认构造方法
  46.     public IntObjectHashMap() {
  47.         this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
  48.     }
  50.     public IntObjectHashMap(int initialCapacity) {
  51.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  52.     }
  54.     public IntObjectHashMap(int initialCapacity, float loadFactor) {
  55.         if (loadFactor <= 0.0f || loadFactor > 1.0f) {
  56.             // Cannot exceed 1 because we can never store more than capacity elements;
  57.             // using a bigger loadFactor would trigger rehashing before the desired load is reached.
  58.             throw new IllegalArgumentException("loadFactor must be > 0 and <= 1");
  59.         }
  61.         this.loadFactor = loadFactor;
  63.         调整容量为2的N次方
  64.         int capacity = MathUtil.nextPowerOfTwo(initialCapacity);
  65.         mask = capacity - 1;
  67.         分配Key数组,Value数组
  68.         keys = new int[capacity];
  69.         @SuppressWarnings({ "unchecked" })
  70.         V[] temp = (V[]) new Object[capacity];
  71.         values = temp;
  73.         实际的容量为数组最大的容量 * 负载因子
  74.         maxSize = calcMaxSize(capacity);
  75.     }
  77.   把取出的数据对外作空转换
  78.     private static <T> T toExternal(T value) {
  79.         return value == NULL_VALUE ? null : value;
  80.     }
  82.   如果写入null,对内转换为NULL_VALUE存储
  83.     @SuppressWarnings("unchecked")
  84.     private static <T> T toInternal(T value) {
  85.         return value == null ? (T) NULL_VALUE : value;
  86.     }
  88.     @Override
  89.     public V get(int key) {
  90.     根据当前key找到对应的索引,如果有冲突，则继续找下一个, 如果冲突的key对应的索引中的实际Key相同,则查找成功
  91.         int index = indexOf(key);
  92.         return index == -1 ? null : toExternal(values[index]);
  93.     }
  95.     @Override
  96.     public V put(int key, V value) {
  97.         int startIndex = hashIndex(key);
  98.         int index = startIndex;
  100.         for (;;) {
  101.       未冲突，写入当前kv
  102.             if (values[index] == null) {
  103.                 // Found empty slot, use it.
  104.                 keys[index] = key;
  105.                 values[index] = toInternal(value);
  106.                 growSize();
  107.                 return null;
  108.             }
  110.       当前key已存在,用新value覆盖原值
  111.             if (keys[index] == key) {
  112.                 // Found existing entry with this key, just replace the value.
  113.                 V previousValue = values[index];
  114.                 values[index] = toInternal(value);
  115.                 return toExternal(previousValue);
  116.             }
  118.             继续找下个非空的value索引
  119.             if ((index = probeNext(index)) == startIndex) {
  120.                 // Can only happen if the map was full at MAX_ARRAY_SIZE and couldn't grow.
  121.                 throw new IllegalStateException("Unable to insert");
  122.             }
  123.         }
  124.     }
  126.     @Override
  127.     public void putAll(Map<? extends Integer, ? extends V> sourceMap) {
  128.         if (sourceMap instanceof IntObjectHashMap) {
  129.             优化版本
  130.             @SuppressWarnings("unchecked")
  131.             IntObjectHashMap<V> source = (IntObjectHashMap<V>) sourceMap;
  132.             for (int i = 0; i < source.values.length; ++i) {
  133.                 V sourceValue = source.values[i];
  134.                 if (sourceValue != null) {
  135.            逐个put
  136.                     put(source.keys[i], sourceValue);
  137.                 }
  138.             }
  139.             return;
  140.         }
  142.         逐个添加Entry
  143.         for (Entry<? extends Integer, ? extends V> entry : sourceMap.entrySet()) {
  144.             put(entry.getKey(), entry.getValue());
  145.         }
  146.     }
  149.   1. 如果key对应value不存在,返回null
  150.   2. 找到对应的索引
  151.     @Override
  152.     public V remove(int key) {
  153.         int index = indexOf(key);
  154.         if (index == -1) {
  155.             return null;
  156.         }
  157.     找到目标值
  158.         V prev = values[index];
  159.         removeAt(index);
  160.         return toExternal(prev);
  161.     }
  163.     @Override
  164.     public int size() {
  165.         return size;
  166.     }
  168.     @Override
  169.     public boolean isEmpty() {
  170.         return size == 0;
  171.     }
  173.   数组清0
  174.     @Override
  175.     public void clear() {
  176.         Arrays.fill(keys, 0);
  177.         Arrays.fill(values, null);
  178.         size = 0;
  179.     }
  181.     @Override
  182.     public boolean containsKey(int key) {
  183.         return indexOf(key) >= 0;
  184.     }
  186.     @Override
  187.     public boolean containsValue(Object value) {
  188.         @SuppressWarnings("unchecked")
  189.         V v1 = toInternal((V) value);
  190.         for (V v2 : values) {
  191.             // The map supports null values; this will be matched as NULL_VALUE.equals(NULL_VALUE).
  192.             if (v2 != null && v2.equals(v1)) {
  193.                 return true;
  194.             }
  195.         }
  196.         return false;
  197.     }
  199.     @Override
  200.     public Iterable<PrimitiveEntry<V>> entries() {
  201.         return entries;
  202.     }
  204.     @Override
  205.     public Collection<V> values() {
  206.         return new AbstractCollection<V>() {
  207.             @Override
  208.             public Iterator<V> iterator() {
  209.                 return new Iterator<V>() {
  210.                     final PrimitiveIterator iter = new PrimitiveIterator();
  212.                     @Override
  213.                     public boolean hasNext() {
  214.                         return iter.hasNext();
  215.                     }
  217.                     @Override
  218.                     public V next() {
  219.                         return iter.next().value();
  220.                     }
  222.                     @Override
  223.                     public void remove() {
  224.                         throw new UnsupportedOperationException();
  225.                     }
  226.                 };
  227.             }
  229.             @Override
  230.             public int size() {
  231.                 return size;
  232.             }
  233.         };
  234.     }
  236.     @Override
  237.     public int hashCode() {
  238.         // Hashcode is based on all non-zero, valid keys. We have to scan the whole keys
  239.         // array, which may have different lengths for two maps of same size(), so the
  240.         // capacity cannot be used as input for hashing but the size can.
  241.         int hash = size;
  242.         for (int key : keys) {
  243.             // 0 can be a valid key or unused slot, but won't impact the hashcode in either case.
  244.             // This way we can use a cheap loop without conditionals, or hard-to-unroll operations,
  245.             // or the devastatingly bad memory locality of visiting value objects.
  246.             // Also, it's important to use a hash function that does not depend on the ordering
  247.             // of terms, only their values; since the map is an unordered collection and
  248.             // entries can end up in different positions in different maps that have the same
  249.             // elements, but with different history of puts/removes, due to conflicts.
  250.             hash ^= hashCode(key);
  251.         }
  252.         return hash;
  253.     }
  255.     @Override
  256.     public boolean equals(Object obj) {
  257.         if (this == obj) {
  258.             return true;
  259.         }
  260.         if (!(obj instanceof IntObjectMap)) {
  261.             return false;
  262.         }
  263.         @SuppressWarnings("rawtypes")
  264.         IntObjectMap other = (IntObjectMap) obj;
  265.         if (size != other.size()) {
  266.             return false;
  267.         }
  268.         for (int i = 0; i < values.length; ++i) {
  269.             V value = values[i];
  270.             if (value != null) {
  271.                 int key = keys[i];
  272.                 Object otherValue = other.get(key);
  273.                 if (value == NULL_VALUE) {
  274.                     if (otherValue != null) {
  275.                         return false;
  276.                     }
  277.                 } else if (!value.equals(otherValue)) {
  278.                     return false;
  279.                 }
  280.             }
  281.         }
  282.         return true;
  283.     }
  285.     @Override
  286.     public boolean containsKey(Object key) {
  287.         return containsKey(objectToKey(key));
  288.     }
  290.     @Override
  291.     public V get(Object key) {
  292.         return get(objectToKey(key));
  293.     }
  295.     @Override
  296.     public V put(Integer key, V value) {
  297.         return put(objectToKey(key), value);
  298.     }
  300.     @Override
  301.     public V remove(Object key) {
  302.         return remove(objectToKey(key));
  303.     }
  305.     @Override
  306.     public Set<Integer> keySet() {
  307.         return keySet;
  308.     }
  310.     @Override
  311.     public Set<Entry<Integer, V>> entrySet() {
  312.         return entrySet;
  313.     }
  315.     private int objectToKey(Object key) {
  316.         return ((Integer) key).intValue();
  317.     }
  320.   根据Key定位具体的索引, 采用双Hash来探测,返回Key对应的下标索引，如果当前Keys中还没有Key,则返回-1
  321.     private int indexOf(int key) {
  322.     默认情况下的初始索引
  323.         int startIndex = hashIndex(key);
  324.         int index = startIndex;
  326.         for (;;) {
  327.             if (values[index] == null) {
  328.                 当前Key对应的索引，其关联的Value为空，说明此位置未产生冲突,返回-1.表示此索引可用
  329.                 return -1;
  330.             }
  331.       当前key已经存在，返回对应的索引
  332.             if (key == keys[index]) {
  333.                 return index;
  334.             }
  336.             key冲突，根据当前Key的索引找到下一个非空的索引
  337.             if ((index = probeNext(index)) == startIndex) {
  338.                 return -1;
  339.             }
  340.         }
  341.     }
  343.     根据Key计算Key在数组的下标
  344.     private int hashIndex(int key) {
  345.         // The array lengths are always a power of two, so we can use a bitmask to stay inside the array bounds.
  346.         return hashCode(key) & mask;
  347.     }
  349.     int类型的Key其Hash值为原生值
  350.     private static int hashCode(int key) {
  351.         return key;
  352.     }
  355.   探测下一个索引位置,
  356.     private int probeNext(int index) {
  357.         // The array lengths are always a power of two, so we can use a bitmask to stay inside the array bounds.
  358.         return (index + 1) & mask;
  359.     }
  361.     新增Key-Value后，递增Size.如果超过阈值,做扩容
  362.     private void growSize() {
  363.         size++;
  365.         if (size > maxSize) {
  366.             if (keys.length == Integer.MAX_VALUE) {
  367.                 throw new IllegalStateException("Max capacity reached at size=" + size);
  368.             }
  370.             基于当前数组大小的2倍
  371.             rehash(keys.length << 1);
  372.         }
  373.     }
  376.   删除索引对应的Key,Value, 如果存在冲突，则打破冲突位置
  377.     private boolean removeAt(final int index) {
  378.         --size;
  379.     建议清除key。
  380.         keys[index] = 0;
  381.         values[index] = null;
  383.         boolean movedBack = false;
  384.         int nextFree = index;
  385.         for (int i = probeNext(index); values[i] != null; i = probeNext(i)) {
  386.             int bucket = hashIndex(keys[i]);
  387.       当前的删除的index右边还存在冲突的Key, 该Key需要向左移动.目的是降低冲突的位置
  388.             if (i < bucket && (bucket <= nextFree || nextFree <= i) || bucket <= nextFree && nextFree <= i) {
  389.                 // Move the displaced entry "back" to the first available position.
  390.                 keys[nextFree] = keys[i];
  391.                 values[nextFree] = values[i];
  392.                 movedBack = true;
  393.                 // Put the first entry after the displaced entry
  394.                 keys[i] = 0;
  395.                 values[i] = null;
  396.                 nextFree = i;
  397.             }
  398.         }
  399.         return movedBack;
  400.     }
  402.     在rehash之前计算最大的数组实际容量
  403.     private int calcMaxSize(int capacity) {
  404.     调整一下大小,以避免loadFactor为1,保证还有可用的槽
  405.         int upperBound = capacity - 1;
  406.         return Math.min(upperBound, (int) (capacity * loadFactor));
  407.     }
  409.     rehash数组,转移数据,扩容或缩容
  410.     private void rehash(int newCapacity) {
  411.         int[] oldKeys = keys;
  412.         V[] oldVals = values;
  414.         keys = new int[newCapacity];
  415.         @SuppressWarnings({ "unchecked" })
  416.         V[] temp = (V[]) new Object[newCapacity];
  417.         values = temp;
  419.         maxSize = calcMaxSize(newCapacity);
  420.         mask = newCapacity - 1;
  423.         for (int i = 0; i < oldVals.length; ++i) {
  424.             V oldVal = oldVals[i];
  425.             if (oldVal != null) {
  426.                 // Inlined put(), but much simpler: we don't need to worry about
  427.                 // duplicated keys, growing/rehashing, or failing to insert.
  428.         内联put方法的逻辑并作冲突检测
  429.                 int oldKey = oldKeys[i];
  430.                 int index = hashIndex(oldKey);
  432.                 for (;;) {
  433.                     if (values[index] == null) {
  434.                         keys[index] = oldKey;
  435.                         values[index] = oldVal;
  436.                         break;
  437.                     }
  438.           在新数组中存在冲突, 寻址下一个位置
  439.                     // Conflict, keep probing. Can wrap around, but never reaches startIndex again.
  440.                     index = probeNext(index);
  441.                 }
  442.             }
  443.         }
  444.     }
  446.     @Override
  447.     public String toString() {
  448.         if (isEmpty()) {
  449.             return "{}";
  450.         }
  451.         StringBuilder sb = new StringBuilder(4 * size);
  452.         sb.append('{');
  453.         boolean first = true;
  454.         for (int i = 0; i < values.length; ++i) {
  455.             V value = values[i];
  456.             if (value != null) {
  457.                 if (!first) {
  458.                     sb.append(", ");
  459.                 }
  460.                 sb.append(keyToString(keys[i])).append('=').append(value == this ? "(this Map)" : toExternal(value));
  461.                 first = false;
  462.             }
  463.         }
  464.         return sb.append('}').toString();
  465.     }
  467.     /**
  468.      * Helper method called by {@link #toString()} in order to convert a single map key into a string. This is protected
  469.      * to allow subclasses to override the appearance of a given key.
  470.      */
  471.     protected String keyToString(int key) {
  472.         return Integer.toString(key);
  473.     }
  475.     /**
  476.      * Set implementation for iterating over the entries of the map.
  477.      */
  478.     private final class EntrySet extends AbstractSet<Entry<Integer, V>> {
  479.         @Override
  480.         public Iterator<Entry<Integer, V>> iterator() {
  481.             return new MapIterator();
  482.         }
  484.         @Override
  485.         public int size() {
  486.             return IntObjectHashMap.this.size();
  487.         }
  488.     }
  490.     /**
  491.      * Set implementation for iterating over the keys.
  492.      */
  493.     private final class KeySet extends AbstractSet<Integer> {
  494.         @Override
  495.         public int size() {
  496.             return IntObjectHashMap.this.size();
  497.         }
  499.         @Override
  500.         public boolean contains(Object o) {
  501.             return IntObjectHashMap.this.containsKey(o);
  502.         }
  504.         @Override
  505.         public boolean remove(Object o) {
  506.             return IntObjectHashMap.this.remove(o) != null;
  507.         }
  509.         @Override
  510.         public boolean retainAll(Collection<?> retainedKeys) {
  511.             boolean changed = false;
  512.             for (Iterator<PrimitiveEntry<V>> iter = entries().iterator(); iter.hasNext();) {
  513.                 PrimitiveEntry<V> entry = iter.next();
  514.                 if (!retainedKeys.contains(entry.key())) {
  515.                     changed = true;
  516.                     iter.remove();
  517.                 }
  518.             }
  519.             return changed;
  520.         }
  522.         @Override
  523.         public void clear() {
  524.             IntObjectHashMap.this.clear();
  525.         }
  527.         @Override
  528.         public Iterator<Integer> iterator() {
  529.             return new Iterator<Integer>() {
  530.                 private final Iterator<Entry<Integer, V>> iter = entrySet.iterator();
  532.                 @Override
  533.                 public boolean hasNext() {
  534.                     return iter.hasNext();
  535.                 }
  537.                 @Override
  538.                 public Integer next() {
  539.                     return iter.next().getKey();
  540.                 }
  542.                 @Override
  543.                 public void remove() {
  544.                     iter.remove();
  545.                 }
  546.             };
  547.         }
  548.     }
  550.     /**
  551.      * Iterator over primitive entries. Entry key/values are overwritten by each call to {@link #next()}.
  552.      */
  553.     private final class PrimitiveIterator implements Iterator<PrimitiveEntry<V>>, PrimitiveEntry<V> {
  554.         private int prevIndex = -1;
  555.         private int nextIndex = -1;
  556.         private int entryIndex = -1;
  558.         private void scanNext() {
  559.             for (;;) {
  560.                 if (++nextIndex == values.length || values[nextIndex] != null) {
  561.                     break;
  562.                 }
  563.             }
  564.         }
  566.         @Override
  567.         public boolean hasNext() {
  568.             if (nextIndex == -1) {
  569.                 scanNext();
  570.             }
  571.             return nextIndex < keys.length;
  572.         }
  574.         @Override
  575.         public PrimitiveEntry<V> next() {
  576.             if (!hasNext()) {
  577.                 throw new NoSuchElementException();
  578.             }
  580.             prevIndex = nextIndex;
  581.             scanNext();
  583.             // Always return the same Entry object, just change its index each time.
  584.             entryIndex = prevIndex;
  585.             return this;
  586.         }
  588.         @Override
  589.         public void remove() {
  590.             if (prevIndex < 0) {
  591.                 throw new IllegalStateException("next must be called before each remove.");
  592.             }
  593.             if (removeAt(prevIndex)) {
  594.                 // removeAt may move elements "back" in the array if they have been displaced because their spot in the
  595.                 // array was occupied when they were inserted. If this occurs then the nextIndex is now invalid and
  596.                 // should instead point to the prevIndex which now holds an element which was "moved back".
  597.                 nextIndex = prevIndex;
  598.             }
  599.             prevIndex = -1;
  600.         }
  602.         // Entry implementation. Since this implementation uses a single Entry, we coalesce that
  603.         // into the Iterator object (potentially making loop optimization much easier).
  605.         @Override
  606.         public int key() {
  607.             return keys[entryIndex];
  608.         }
  610.         @Override
  611.         public V value() {
  612.             return toExternal(values[entryIndex]);
  613.         }
  615.         @Override
  616.         public void setValue(V value) {
  617.             values[entryIndex] = toInternal(value);
  618.         }
  619.     }
  621.     /**
  622.      * Iterator used by the {@link Map} interface.
  623.      */
  624.     private final class MapIterator implements Iterator<Entry<Integer, V>> {
  625.         private final PrimitiveIterator iter = new PrimitiveIterator();
  627.         @Override
  628.         public boolean hasNext() {
  629.             return iter.hasNext();
  630.         }
  632.         @Override
  633.         public Entry<Integer, V> next() {
  634.             if (!hasNext()) {
  635.                 throw new NoSuchElementException();
  636.             }
  638.             iter.next();
  640.             return new MapEntry(iter.entryIndex);
  641.         }
  643.         @Override
  644.         public void remove() {
  645.             iter.remove();
  646.         }
  647.     }
  649.     /**
  650.      * A single entry in the map.
  651.      */
  652.     final class MapEntry implements Entry<Integer, V> {
  653.         private final int entryIndex;
  655.         MapEntry(int entryIndex) {
  656.             this.entryIndex = entryIndex;
  657.         }
  659.         @Override
  660.         public Integer getKey() {
  661.             verifyExists();
  662.             return keys[entryIndex];
  663.         }
  665.         @Override
  666.         public V getValue() {
  667.             verifyExists();
  668.             return toExternal(values[entryIndex]);
  669.         }
  671.         @Override
  672.         public V setValue(V value) {
  673.             verifyExists();
  674.             V prevValue = toExternal(values[entryIndex]);
  675.             values[entryIndex] = toInternal(value);
  676.             return prevValue;
  677.         }
  679.         private void verifyExists() {
  680.             if (values[entryIndex] == null) {
  681.                 throw new IllegalStateException("The map entry has been removed");
  682.             }
  683.         }
  684.     }
  685. }