零 前期准备0 FBI WARNING文章异常啰嗦且绕弯。1 版本Netty : 5.0.0.Alpha5IDE : idea 2022.2.4maven 坐标：<dependency> <groupId>io.netty</groupId> <artifactId>netty5-all</artifactId> <version>5.0.0.Alpha5</version></dependency>一 简介IntObjectHashMap 是 netty 封装的，key 必须是 int 的 HashMap 容器。在 netty 4 中，该类位于 netty-all 包下的 io.netty.util.collection 路径下；在 netty 5 中，该类位于 netty5-common 包下的 io.netty5.util.collection 路径下。本文使用 netty 5 进行源码跟踪。值得注意的是，截止到 2022 年 12 月，netty 5 还没有进入生产就绪的状态，不建议在生产环境使用。二 Demoimport io.netty5.util.collection.IntObjectHashMap;import io.netty5.util.collection.IntObjectMap;public class IntHashMapTest { public static void main(String[] args) { // 创建一个容器 // Map<Integer, String> map = new IntObjectHashMap<>(); IntObjectMap<String> map = new IntObjectHashMap<>(); // 存值 map.put(1, "t1"); map.put(2, "t2"); // 输出 t2 System.out.println(map.get(2)); // 删除 map.remove(2); }}三 IntObjectMapIntObjectMap 是 IntObjectHashMap 的顶层接口。package io.netty5.util.collection;import java.util.Map;/** * IntObjectMap 继承了 map，但是 key 必须是 int */public interface IntObjectMap<V> extends Map<Integer, V> { /** * PrimitiveEntry 是 IntObjectMap 内部定义的 Entry 类，相比 Entry 功能更为简单 * 它的实现在 IntObjectHashMap 中 */ interface PrimitiveEntry<V> { /** 获取 key */ int key(); /** 获取 value */ V value(); /** 存入 value */ void setValue(V value); } /** 根据 key 获取值 */ V get(int key); /** 存入键值对 */ V put(int key, V value); /** 删除键值对，并返回值 */ V remove(int key); /** 获取 Entry 的迭代器 */ Iterable<PrimitiveEntry<V>> entries(); /** 判断是否存在键值对 */ boolean containsKey(int key);}四 IntObjectHashMap1 变量// 默认容量public static final int DEFAULT_CAPACITY = 8;// 用来 rehash 的 load 因子数public static final float DEFAULT_LOAD_FACTOR = 0.5f;// 当插入的 value 是 null 的时候，会塞入一个填充对象private static final Object NULL_VALUE = new Object();// 能实现的最大值private int maxSize;// rehash 的 load 因子数，会影响 maxSizeprivate final float loadFactor;// key 的集合private int[] keys;// value 的集合private V[] values;// 当前的 sizeprivate int size;// 数组最大的 index，等于 array.length - 1private int mask;// key 的集合 setprivate final Set<Integer> keySet = new KeySet();// k-v 的集合 setprivate final Set<Entry<Integer, V>> entrySet = new EntrySet();// 迭代器private final Iterable<PrimitiveEntry<V>> entries = new Iterable<PrimitiveEntry<V>>() { @Override public Iterator<PrimitiveEntry<V>> iterator() { return new PrimitiveIterator(); }};2 构造器/** 使用默认容量和 load 因子的构造器 */public IntObjectHashMap() { this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);}/** 使用 load 因子的构造器 */public IntObjectHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}public IntObjectHashMap(int initialCapacity, float loadFactor) { // 有效性验证 if (loadFactor <= 0.0f || loadFactor > 1.0f) { throw new IllegalArgumentException("loadFactor must be > 0 and <= 1"); } // 存入 load 因子 this.loadFactor = loadFactor; // 存入容量 int capacity = safeFindNextPositivePowerOfTwo(initialCapacity); // 数组最大 size mask = capacity - 1; // keys keys = new int[capacity]; // values @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" }) V[] temp = (V[]) new Object[capacity]; values = temp; // 最大容量 maxSize = calcMaxSize(capacity);}2.1 safeFindNextPositivePowerOfTwo用来计算最大容量的方法，在 io.netty5.util.internal.MathUtil 里。public static int safeFindNextPositivePowerOfTwo(final int value) { return value <= 0 ? 1 : value >= 0x40000000 ? 0x40000000 : findNextPositivePowerOfTwo(value);}public static int findNextPositivePowerOfTwo(final int value) { assert value > Integer.MIN_VALUE && value < 0x40000000; return 1 << (32 - Integer.numberOfLeadingZeros(value - 1));}这两个数学方法用以获取比输入数字更大的一个 2 的幂数。举例来说：输入 1， 返回 1；输入 2， 返回 2；输入 3， 返回 4；输入 55， 返回 64；输入 100，返回 128；输入 513，返回 1024。2.2 calcMaxSizeprivate int calcMaxSize(int capacity) { int upperBound = capacity - 1; // 比较 cap - 1 和 cap * load 哪个比较小，取小的那个座位 maxSize 返回 return Math.min(upperBound, (int) (capacity * loadFactor));}3 put@Overridepublic V put(int key, V value) { // 使用 key 计算一个 hash 值作为起始 hash 值 int startIndex = hashIndex(key); int index = startIndex; // 死循环 for (;;) { if (values[index] == null) { // 如果 hash 值对应的 value 槽里没有值，就将新值插进去 // 插入 key keys[index] = key; // 插入值 values[index] = toInternal(value); // 判断是否需要扩容数组，如果需要的话在这里会动态扩容 growSize(); return null; } // 到此处，说明 hash 值对应的 value 槽里有东西了 if (keys[index] == key) { // 此处说明， key 对应的这个插槽里就似乎当前的 key V previousValue = values[index]; // 用新值代替旧值 values[index] = toInternal(value); // 返回原来的值 return toExternal(previousValue); } // 此处会将 index 挪到下一个槽里，继续此循环 if ((index = probeNext(index)) == startIndex) { // 如果下一个 index 槽就是当前，说明死循环了，抛错 throw new IllegalStateException("Unable to insert"); } }}3.1 hashIndexprivate int hashIndex(int key) { return hashCode(key) & mask;}private static int hashCode(int key) { return (int) key;}这两个方法的核心是制造 hash 碰撞，然后指定一个在数组长度内的插槽。3.2 toInternal 和 toExternalprivate static <T> T toExternal(T value) { assert value != null : "null is not a legitimate internal value. Concurrent Modification?"; return value == NULL_VALUE ? null : value;}@SuppressWarnings("unchecked")private static <T> T toInternal(T value) { return value == null ? (T) NULL_VALUE : value;}这两个方法主要是杜绝 value 为 null 的情况，将 value 包装成一个 object 再存入数组中。// NULL_VALUE 是一个 Object 对象private static final Object NULL_VALUE = new Object();3.3 growSizeprivate void growSize() { size ++; if (size > maxSize) { if(keys.length == Integer.MAX_VALUE) { throw new IllegalStateException("Max capacity reached at size=" + size); } // 如果 size 比 maxSize 大，则说明所有的槽都被占满了，此处需要 rehash // rehash 方法会将 maxSize 扩大一倍 rehash(keys.length << 1); }}private void rehash(int newCapacity) { int[] oldKeys = keys; V[] oldVals = values; // 此处创建两个新的数组 keys = new int[newCapacity]; @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" }) V[] temp = (V[]) new Object[newCapacity]; values = temp; // 重新计算 maxSize maxSize = calcMaxSize(newCapacity); mask = newCapacity - 1; // 将原来的数据重新插入到新的数组里 // 具体过程和 put 方法差不多 for (int i = 0; i < oldVals.length; ++i) { V oldVal = oldVals[i]; if (oldVal != null) { int oldKey = oldKeys[i]; int index = hashIndex(oldKey); for (;;) { if (values[index] == null) { keys[index] = oldKey; values[index] = oldVal; break; } index = probeNext(index); } } }}3.4 probeNextprivate int probeNext(int index) { return (index + 1) & mask;}获取下一个位置。4 get@Overridepublic V get(int key) { int index = indexOf(key); return index == -1 ? null : toExternal(values[index]);}和 put 方法基本类似，也是通过 indexOf 方法获取一个 key 所对应的槽，然后去直接读取 value 并返回。4.1 get 的 Map 接口方法demo:// 在这种方式下会强制 IntObjectHashMap 使用 Map 接口提供的 get 方法String val = map.get(new Integer(2));实现为：@Overridepublic V get(Object key) { return get(objectToKey(key));}// 默认输入的 key 只能是 Integer 类型的，然后将其转为 int 类型private int objectToKey(Object key) { return (int) ((Integer) key).intValue();}get(Object key) 这个方法是 java.util.Map 接口里带的方法，这里 IntObjectHashMap 做了兼容。5 remove@Overridepublic V remove(int key) { // 确定 index int index = indexOf(key); if (index == -1) { return null; } // 获取原来的值 V prev = values[index]; // 删除值 removeAt(index); // 返回原来的值 return toExternal(prev);}private boolean removeAt(final int index) { --size; // 还原这两个数组槽内的值 keys[index] = 0; values[index] = null; // 这里需要将当前卡槽后偏移的数据挪回来，避免槽内出现太多的空缺，影响查询效率 int nextFree = index; int i = probeNext(index); for (V value = values[i]; value != null; value = values[i = probeNext(i)]) { int key = keys[i]; int bucket = hashIndex(key); if (i < bucket && (bucket <= nextFree || nextFree <= i) || bucket <= nextFree && nextFree <= i) { // 此时的 i = probeNext(nextFree) // 也就是说，i 是 nextFree 的下一次偏移 // 这里将 i 对应的 key 和 value 转换到 nextFree 对应的槽里 keys[nextFree] = key; values[nextFree] = value; keys[i] = 0; values[i] = null; nextFree = i; } } return nextFree != index;}四 总结IntObjectHashMap 没有和 jdk HashMap 一样，使用链表法来解决 hash 冲突，而是使用了开放地址法由于使用了开放地址法，实际上在 hash 碰撞较为严重的场合，其查询性能比 HashMap 会更好，但是其扩缩容的代价会比 HashMap 更大，性能更糟不适合数据量较大的场景，适合数据量较小且查询速度要求较高的场景将 int 作为 key，更加抠内存
