共计 6713 个字符，预计需要花费 17 分钟才能阅读完成。
零 后期筹备
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，更加抠内存
正文完
