关于java:追踪解析-Netty-IntObjectHashMap-源码

零后期筹备

0 FBI WARNING

文章异样啰嗦且绕弯。

1 版本

Netty : 5.0.0.Alpha5
IDE : idea 2022.2.4
maven 坐标：

<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 还没有进入生产就绪的状态，不倡议在生产环境应用。

二 Demo

import 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);    }}

三 IntObjectMap

IntObjectMap 是 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);}

四 IntObjectHashMap

1 变量

// 默认容量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 calcMaxSize

private 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 hashIndex

private int hashIndex(int key) {    return hashCode(key) & mask;}private static int hashCode(int key) {   return (int) key;}

这两个办法的外围是制作 hash 碰撞，而后指定一个在数组长度内的插槽。

3.2 toInternal 和 toExternal

private 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 growSize

private 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 probeNext

private 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，更加抠内存

零 后期筹备