关于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 因子数，会影响 maxSize
private final float loadFactor;
// key 的汇合
private int[] keys;
// value 的汇合
private V[] values;
// 以后的 size
private int size;
// 数组最大的 index，等于 array.length - 1
private int mask;

// key 的汇合 set
private final Set<Integer> keySet = new KeySet();
// k-v 的汇合 set
private 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

@Override
public 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

@Override
public 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));

实现为：

@Override
public 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

@Override
public 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，更加抠内存