目录

ThasBlog

学无止境

X

Java8 HashMap

HashMap

Map 意思是映射, 从key映射到value.

HashMap 就是基于hash的key来实现映射关系.

数组是在连续的固定大小的内存空间上顺序且紧凑地存储元素的集合. 数组支持随机读写, 其本质原因就是紧凑存储. 通过数组头部位置+索引就可以直接获得指定元素的地址, 对该地址直接进行读写. 但紧凑存储同时带来另一弊端, 为了保证数组元素紧凑, 每次在数组中间增删元素时都需要挪动数组元素以保证数组中间没有空缺.

数组索引 = 元素在数组中的位置, 数组索引是顺序的且永远不会重复.

Hash表继承了数组的优点, 支持随机读写, 又不需要(频繁)挪动元素. 牺牲了少量额外内存空间和散列计算开销.

Hash索引 = 散列函数(元素), Hash索引不是顺序的, 只与元素本身相关, 但是是可能重复的.

当Hash索引重复时, 一个索引会对应多个元素, 这就是Hash碰撞, 这时Hash表随机读写的优势就会降低. 适当的增加Hash表分配的内存空间可以减少Hash碰撞几率, 所以Hash表通常会有额外的未利用内存空间.

链地址法(拉链法): 冲突的地方转为链表, HashMap采用此种方式.

开放定址法: 对Hash值再次Hash, 得到新的索引.

再哈希法: 内置多个Hash算法, 冲突时则切换另一个Hash算法, 直至不冲突.

公共溢出区法: 建立公共溢出表, 所有冲突的元素放到该表.

HashMap源码

重要内部成员

Node<K,V>[] table: HashMap中用于实现存放元素的地方, 连续的内存空间(用数组来实现), 但存放的元素并不要求紧凑存储. Hash索引映射到数组中即为数组索引.

int size: 实际存储的元素数量, 区别于数组长度.

int threshold: 可容纳元素数量(table.length * loadFactor), 区别于数组长度.

float loadFactor: threshold/table.length, 负载因子. 如果Hash表内存空间分配过大(数组长度过长), 碰撞概率降低, 随机读写性能提高, 但是造成过多的内存浪费; 如果内存分配过小(数组长度过短), 节省了内存, 但是碰撞概率增大, 极端时退化为链表. 负载因子0.75可以适用于大部分场景.

int capacity: 数组大小(table.length), 这只是一个术语, 并不是一个字段, 但是确容易误解. HashMap的构造函数有这样一句:

this.threshold = tableSizeFor(initialCapacity);

其中tableSizeFor函数是用来优化数组容量的, 当容量为2的幂时, 可以通过简单的位运算获得Hash索引.

容量为2的幂的二进制数形式为:

10000000

如果要获得一个数在该数组中的索引, 只需取模即可. 将1000000000 - 1得到

01111111

那么余数就是

01111111
& 11010101
= 01010101

即抹掉高位.

继续, 构造函数中该语句的含义就等于this.threshold = capacity, 很让人误解threshold和capacity, 这是个坑, 在resize函数中可以找到答案:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
          ...
          // 当数组已被初始化时 做些处理
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 当数组未被初始化, 且设置了初始threshold时, capacity = threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
            // 将threshold调整为正常的capacity * loadFactor
        }
        threshold = newThr;
        ...
    }

也就是说, 只有通过构造函数设置初始容量时, threshold才会被赋值为capacity, 但当真正初始化table时, capacity = threshold, threshold = capacity * loadFactor 恢复正常.

这样做的目的其实是Java做的一个延迟初始化优化工作, 当HashMap刚刚创建时, 并不初始化table, 等到真正要存放元素, 才初始化. 但是上面也提到capacity这个术语并没有真正定义为内部字段(不需要定义, 因为capacity = table.length), 所以就借助threshold临时充当了capacity. 观察构造函数的参数名, 也可以发现, 本身期望参数就是capacity:

public HashMap(int initialCapacity)

阿里巴巴编码规约要求, 实例化HashMap时应当指定容量, 这个容量并不是你实际要存放的元素个数, 而应当根据期望存放数量(threshold)和负载因子计算容量(capacity)大小.

Node即为存放Key-Value元素的载体, 本身是一个链表节点实现, 为Hash碰撞做准备. HashMap前半段Hash指Hash表, 后半段Map代表映射, HashMap的实现除了存放Key的集合外, 每个Key还可以附带一个Value(映射), 这就是HashMap的两层含义.

核心接口

Entry接口: 对于外部使用者而言, 无需关注Node是如何实现, 只需要关心取得他所存放的Key-Value, 所以Entry只提供key的getter(key不可改)以及value的getter和setter

hash: key的hash值缓存, 避免重复计算. 但是可能会造成内存泄漏, 如果key的hash值由于某些成员的变化改变了, 那么这个key就再也无法被找到了.

key: key

value: value

next: 链表下一节点

核心方法

**Node<K, V>[] resize(): **数组扩容

该方法会在三种情况下被调用:

  1. 首次存放元素, 需要初始化时, 上面提到过, 有坑.
  2. size > threshold时(容量不够了). 比较常见
  3. Hash碰撞的元素超过8个, 但数组容量过小(<64)时, 扩容而不是树化(扩容可以降低碰撞概率). 这种情况下的扩容与实际存放的元素数量(size)无关.
  4. resize的源码分为两部分:
  5. 扩容, 容量和阈值都翻倍. 构建新的数组.
  6. 将原数组的元素迁移到新数组.

数组中的每个位置成为bin(箱子), 因为并不一定只存放一个元素. 当bin中只有一个元素, 重新使用位运算计算索引即可(数组大小依然是2的幂). 当bin中不止一个元素时, bin中的所有元素都需要一一处理. 这些碰撞的元素, 只有两个位置, 一个是原bin, 另一个是扩容那一侧的相同位置的bin(偏移原位置+原数组大小), 因为它们的hash值拥有相同的低位, 这一次 HashMap中将这种操作成为 split, 原位置叫 low, 扩容那一侧叫 high.

split后, 依然会保持原链表的顺序, 源码注释提到过. 至于bin中的元素到底在low侧还是high侧, Java8有一种非常巧妙的方式:

// 判断该表达式是否为0 为0则在低侧
(currentNode.hash & oldCapacity) == 0
// 数组容量的特点
10000000
// 获得索引时
10000000 - 1 = 01111111
// 索引等于Hash值的后面几位
// 如果一个Hash值 & 原数组容量 = 0 说明该Hash值在原数组容量的最高位的那个数一定是0
// 新数组容量为两倍 比原数组容量高了一位
100000000
// 那么 计算新索引时
10000000 - 1 = 011111111
// 由于Hash值在原数组容量的最高位的那个数是0 所以此时计算得到的索引与原索引相同
// 反之 新索引最高位将会多出一个1 也就是偏移到扩容那一侧的相同位置

如果是红黑树节点(根节点), 就调用红黑树的split方法(此时, 才会根据<6进行反树化)

**V put(K key, V value): **存放一个元素.

大家都会的: put方法, 先计算key的Hash值, 得到数组索引, 将key+value封装为一个Node放入该位置, 如果该位置, 已有元素, 则将该Node以链表形式放入, 如果链表长度超过8, 转换为红黑树.

更深入点研究存放元素的过程.

第一步: 计算hash值, 此hash并非JavaObject的hash, 它是逻辑上的Hash索引值, 区别于实际存储到数组的数组索引.

Hash表的内存空间一定要比Hash索引的取值范围更大, 但是Java的Hash值是32位, 每个Hash表分配这么大的内存空间显然是不现实的. 因此通过分配一个特定大小的数组, 通过取模的方式得到Hash值在该数组中的映射位置, 从而减小了内存空间的占用.

为了更好的计算这个数组索引, HashMap使用了非常取巧的方式, 上面也提到了, 当数组容量为2的幂时, 任何二进制数和它取模都是取最后几位, 通过简单的位运算即可得到索引. 但是这也带来另一个麻烦, 不管Hash值有多少位, 真正有意义的只有最后几位, 碰撞概率大大提高, 因此HashMap引入了扰动函数, 让高16位和低16位异或运算, 降低低16位的碰撞概率.

static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

这便是第一步要重新计算Hash值得原因.

第二步: 判断是否需要初始化, 如未初始化, 通过resize初始化, 上面提到过capacity的问题.

第三步: 计算数组索引(实际存放的位置)

tab[i = (n - 1) & hash]
  1. 如果该位置没有元素, 则构建链表节点直接存放
tab[i] = newNode(hash, key, value, null)
  1. 如果该位置已有元素, 且该元素的key与本次插入的key相同, 则替换该元素的value.
  2. 如果该key与本次插入的key不相同, 且该元素是树节点(红黑树根节点), 则使用putTreeVal方法存放元素(红黑树存放元素).
  3. 如果该元素不是树节点, 那就是个普通链表节点了, 开始拉链. 遍历该链表, 判断每个元素的key是否和本次插入的key相同, 发现相同的key, 则本次替换该元素的value, 结束; 如果到最后都没有相同的key, 就构建节点插入链表尾部. 当链表节点达到8个时, 树化.

最后, 判断size是否大于阈值, 如大于阈值, 扩容

**V get(Object key): **查找一个元素, 返回Value.

首先计算hash值. 计算索引, 定位到目标bin.

如果该bin没有元素直接返回null.

如果该bin有元素, 且该元素的key与本次插入的key相同, 则直接返回

如果该bin有元素, 该节点时红黑树节点, 委托给红黑树getTreeNode

如果只是普通节点, 直接向后遍历.

**V remove(Object key): **删除一个元素, 返回元素的Value; 返回null代表没有改Key的元素.

与查找过程非常类似, 但又有区别, 删除操作是统一执行的.

如果该bin没有元素直接返回null.

如果该bin有元素, 且为目标元素, 暂存.

如果该bin有元素, 该节点时红黑树节点, 委托给红黑树getTreeNode, 暂存.

如果该bin有元素, 直接向后遍历, 找到目标元素, 暂存.

如果暂存元素不为空, 则为待删除的元素. 红黑树节点委托给红黑树removeTreeNode; 链表第一个节点删除, 要注意将后一个节点放到数组的bin上.

红黑树算法的实现细节比较复杂, 简单挑几个可能有用的点.

红黑树的所有元素均是有序的, 优先Hash值排序(碰撞了不代表Hash值相同, 只是取模后的索引相同), 如果Hash值相同且Key是可比较的(实现了Comparable接口, 且Comparable的泛型参数是该Key的类型), 那么按Key的大小排序, 如果是不可比较的, 则按IdentityHashCode排序.

查找元素时, 优先按Hash值区分左右子树, 然后按Comparable接口比较大小进行区分, 如果还不行则递归.(最后用的是递归, 而不是IdentityHashCode)

反树化的条件:

if (root == null// 根节点没了
                || (movable
                    && (root.right == null // 右子树没了
                        || (rl = root.left) == null // 左子树没了
                        || rl.left == null))) {// 左子树的左子树没了
                tab[index] = first.untreeify(map);  // too small
                return;
            }

split过程, 先跟链表一样拆分, 再针对拆分后的两个链表重新建树.

拆分后的树节点数目小于6个,也会反树化.

反树化过程十分简单, 因为所有的树节点本身也符合链表节点特性, 只需要将树节点类型转换成普通节点即可.

详细代码注释放在: https://github.com/thascc/java8


标题:Java8 HashMap
作者:thas
地址:https://thas.cc/articles/2020/12/05/1607172626059.html