HashMap 总结

HashMap hash过程

DeepinScrot-2941.png

这里先取了key的hashcode, 之后将高16位与低16位进行异或
为什么要这样做呢, 一个object的hashcode范围为-2^32到 2^32 -1, 空间在40多亿,单纯从这个考虑来说不会发生碰撞, 然而实际情况数组大小不可能这个么大, 在确定hashcode对应数组的位置时(n - 1) & hash, n为数组长度, hashmap中, 数组长度为2的整次幂,所以n-1相当于低位掩码, 低位取得的值即为数组下标,单纯考虑地位的话,就会增加碰撞的概率, 所以通过高16位与低16位进行异或,来增加低位的随机性.

HashMap put过程

先检查tab, HashMap 内部的Node数组,如果数组为空,则初始化数组,大小为16, 之后根据
(n - 1) & hash 计算出新节点对应数组的下标, 如果对应位置还没有节点, 则将新节点插入,如果对应节点的键值与原节点的键值相等(引用相同或equals返回true),则替换原有节点的值为新值, 如果不同, 则分两种情况.
节点为树节点,则插入
节点为链表, 则在链表中进行查询,若没有对应的键值,则添加节点到链表末尾, 同时如果插入完以后链表长度大于等于7,会将链表转化为树, 若key已存在, 则替换对应节点的值为新值
若新增节点, 且整个map的大小大于阈值时,会进行扩容

HashMap resize过程

当HashMap 内的元素增加时, 且容量大于阈值(容量 * 0.75)时, 会进行扩容, 初始容量为16, 每次扩容都会使容量加倍, 此时会新建一个长度为新容量的Node数组,并对原来的Node重新计算hash值,并将Node移到对应的位置

HashMap 常用Key

String, Integer, Immutable , hascode, equals 已完整实现, 切有缓存

如何设计Immutable类

mutable字段加final, class 上加final, 不提供setter, consctructor初始化所有字段, clone 提供deep copy
用于做Key 时, 覆写 equals, hashcode, hashcode 做缓存,
equals 满足规则自反, 传递, 对称, 多次调用一致
hashcode 满足规则, 若equals则 hashcode 必相等, 若不equals, 则不强制不等, 最好不等, 可减少在HashMap中冲突

Hashmap tableSize

HashMap的size 为二的幂次方, 当初始化HashMap的时候，传入非二的幂次方capacity会被转化为与其最近的较大的二的幂次方

 static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这里减1是因为，如果cap已经为二的幂次方了，若不减1，会使得cap翻倍。
因为hashmap会在容量达到capacity * threshold（默认0.75）触发扩容，建议在初始化Map时，指定容量为（capacity/0.75） + 1