thanq的日志

java8里HashMap/ConcurrentHashMap的实现

java8之前版本的HashMap/ConcurrentHashMap是怎样实现的

HashMap:

  • 设计初衷: 在数据hashCode离散场景下, 以接近O(1)的时间复杂度实现快速定位, 快速查找
  • 数据结构: Entry数组+Entry链表. Entry实现了Map.Entry接口, 是对key-value结构的封装, Entry内还会保存一个方便组成链表的指针, 以及一个根据key的hashCode用扰动函数算出的hash(下文的hash均指代根据对应key的hashCode, 用扰动函数算出的值)
  • hash扰动函数: 多次混合原hashCode的高位和低位,来加大低位的随机性

    1
    2
    3
    4
    static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    }
  • get操作过程: 先用hash定位到Entry数组的(hash % 数组长度)位置, 如果该位置处有数据, 会遍历该位置上的Entry链表, 直到找出key值和要找的key相等的数据
  • put操作过程: 先查看数组的(hash % 数组长度)位置有没有数据, 如果没有就直接将数据放到这个位点; 如果有数据就遍历这个位置上的Entry链表, 若是链表中已存在key值相同的数据, 则更新该数据并返回, 若是没有就将新数据作为表头加入链表
  • 数组长度会被强制为2的整数次幂, 虽说长度为素数会有更好的离散性, 但数组长度为2的整数次幂时, 可以更好的用位操作优化计算(如用hash & (数组长度-1)替代取模操作hash % 数组长度), 开销更小, 且扩容起来也更方便
  • 构造接受两个参数, 分别是数组初始长度(默认16)和加载因子(默认0.75), 初始长度 * 加载因子就是HashMap的初始最大容量, map里的数据量超过(数组长度 * 加载因子)是触发扩容操作的条件之一
  • 扩容操作过程: 当map里的数据量超过(数组长度 * 加载因子)且有put操作发生了哈希碰撞时, 会触发扩容操作, 扩容时会先构建长度加倍的新数组, 然后遍历一遍旧数组内的数据, 将它们重新落到新数组的(hash % 新数组长度)位置, 如数据量非常大, 扩容的开销不可忽略
  • HashMap中key和value都可以是空值
  • 存在的问题: 如果HashMap中的key值数hashCode都一样, 那所有数据就会一直都落在同一条链上, 此时设计初衷为实现快速查找的HashMap就退化为链表, 操作的时间复杂度成为O(n). 这点可能被攻击者利用. 比如你的json解析库有用到HashMap, 而攻击者提交了每个属性hashCode都一样的大json数据, 在解析这个json时, cup就会瞬间飙高, 影响服务可用性; 或者恶意攻击者持续不断的向系统提交hashCode相同的数据, 而处理这些数据时使用了HashMap, 这样系统性能就会不断降低, 且这种攻击不易察觉

ConcurrentHashMap:

  • HashMap是为单线程处理场景设计的, 并发场景下一般可以使用ConcurrentHashMap, 如果要求绝对的强一致性, 可用HashTable
  • 设计思想: 通过分段锁(多个独立的锁)来支持多个线程并发操作, 以此提高并发场景下的性能和伸缩性
  • 数据结构: Segment数组. Segment继承了ReentrantLock, 同时Segment内部包含了一个类HashMap的实现, 这个实现里可能并发访问的变量都是final或volatile修饰的, 且可能导致并发问题的操作会锁上当前Segment, 以保证线程安全
  • 构造接受3个参数: 分别是初始化容量(默认16), 加载因子(默认0.75), 并发等级(默认16); 初始化容量影响Segment内部HashEntry的初始数组长度, 加载因子影响每个Segment的扩容时机, 并发等级决定该ConcurrentHashMap内部Segment数组的长度, Segment数组长度会在初始化时确定下来, 之后不再变化; Segment数组和Segment内部HashEntry数组的长度都会被强制为2的整数次幂
  • get操作过程: 先用hash的高位定位到Segment数组中对应的Segment, 再根据hash定位到该Segment内HashEntry数组的对应位置, 如果该位置上有数据, 则遍历该位置上的链表, 直到找出要找的数据. get操作是无锁的
  • put操作过程: 先用hash的高位定位到对应的Segment, 再锁住该Segment, 之后的过程类似于HashMap的put操作, 当Segment内数据量超过Segment内HashEntry数组长度*加载因子且put操作发生了哈希碰撞时, 还会触发Segment内部的扩容操作, 所有这些操作完成后解锁该Segment
  • Segment内部扩容操作过程: 类似于HashMap的扩容过程
  • ConcurrentHashMap中key和value都不能是空值. 如果允许为空值, 就不能判断这个空值是由于存在并发操作导致的, 还是原本就是空值了, 这会导致一些并发判断失效
  • 和HashMap不同, ConcurrentHashMap构造的第一个参数是初始容量, 而不是用来存放数据数组长度
  • 还是有上面HashMap的hash碰撞拒绝服务攻击问题
  • 由于容量会分到各个Segment, 且事先无法知道那个Segment可能分到的数据量, 所以各Segment的扩容时机是不可控的, 若想避免扩容操作, 需保证各Segment的容量都大于整个ConcurrentHashMap的预估最大容量

java8的实现

HashMap:

  • 数据结构: Node数组+Node链表+TreeNode红黑树. Node类似于之前版本的Entry, 也是实现了Map.Entry接口, 封装了key-value数据; TreeNode继承了Node的子类LinkedHashMap.Entry, 是红黑树的实现
  • hash扰动函数: h ^ (h >>> 16). 这一版的扰动函数较之前版本精简了许多, 可能是java8的工程师觉得太复杂的扰动函数带来的效果提升并不大
  • 构造接受两个参数, 分别是Node数组初始长度(默认16)和加载因子(默认0.75), 数组长度会被限制为2的整数次幂, put操作时, 只要map里的数据量超过(数组长度 * 加载因子)就会触发扩容操作
  • get操作过程: 类似于之前版本的实现, 不过会判断要操作位点上的数据是不是TreeNode形式, 如果是就会以查找红黑树的方式取到数据
  • put操作过程: 类似于之前版本的实现, 不过操作时会判断Node数组对应位置上的数据类型, 如果为TreeNode, 就将新数据插到红黑树中, 否则就将新数据加入该位置上链表, 如操作后的链表长度大于8, 会将该链表改造成红黑树, 改造后发生在该位点上的增删改查操作时间复杂度由O(n)降为O(lgn)
  • 转成红黑树是为了应对哈希碰撞严重的极端情况(如恶意攻击等), 较好的解决了旧版纯链表实现可能导致的哈希碰撞拒绝服务攻击问题
  • 扩容时数组长度由2的n次幂变为2的n+1次幂, 而hash根据2的n+1次幂取模的值即是hash转为二进制后的后n位, 根据2的n次方取模就是后n-1位, 所以如果hash的第n位(可用hash&旧数组长度计算)为0的话数据在扩容后新数组中的位置就和在旧数组中的位置相同, 为1的话数据在扩容后新数组中的位置就是原位置+n. java8根据这个做了优化, 扩容时旧数组在w位置上的数据会根据hash的第n位是0还是1拆分为2组, 然后把为0的放到新数组的w位置, 为1的放到w+旧数组长度位置
  • 扩容操作过程: 如旧数组长度为2的n次幂, 会先构建长度加倍的新数组, 再遍历一遍旧数组内的数据, 已经是链表的节点, 会根据hash二进制形式的第n位是0还是1拆成两个链表, 已经是红黑树的节点, 会被拆为两棵红黑树, 然后按上一条的规则放到新数组上, 如果拆分后的红黑树长度小于等于6, 会再降级为链表
  • remove数据时, 如果remove操作发生在红黑树上, 会判断操作后的树的层数是不是小于3, 如果小于三层, 会将该红黑树降级为链表

ConcurrentHashMap:

  • 数据结构: Node数组+Node链表+TreeBin红黑树. 这里的Node和HashMap里的Node相似, 不过可能有并发访问的变量都是final或volatile修饰的, 以保证线程安全, TreeBin继承了Node, 内部包含了一个红黑树的实现(TreeNode), TreeBin节点的hash被固定为-2. 和旧版的结构相比, 新的结构变得更扁平, 数据操作不再需要先定位到Segment再二次定位了
  • 设计思路仍然是分段锁, 但锁的粒度是Node数组的每个Node, 锁的个数是Node数组的长度, 所以伸缩性会比锁粒度为固定数量Segment的旧实现强许多, 出现锁竞争的概率也会更小, 而且使用了内部锁而不是Lock, 遵循了如非必要使用内部锁而不是Lock的最佳实践
  • hash扰动函数: (h ^ (h >>> 16)) & 0x7fffffff, 比HashMap多了保证hash为正数的操作
  • 构造接受3个参数: 分别是初始化容量, 加载因子, 并发等级. 初始化容量会影响Node数组初始长度, 数组长度会被限制为2的整数次幂; 加载因子也会影响初始数组的大小, 但只在第一次初始化时有用, 经过扩容后加载因子会被固定为0.75; 并发等级已经没什么用了, 主要是保持向下兼容
  • ConcurrentHashMap内有个较重要的控制参数sizeCtl. sizeCtl为-1时, 说明正在初始化; sizeCtl为正数n时, 这个n就是当前ConcurrentHashMap的最大容量; sizeCtl为-n, 表明当前有n-1个线程正在进行扩容操作
  • get操作过程: 先根据key的hash定位到Node数组对应的位置, 如果该位置有数据会先判断该数据的hash, 若hash不为负, 说明该处数据为链表形式, 此时会遍历链表直到找到数据, 若hash为负, 说明该数据为TreeBin或ForwardingNode, 此时会调用其各自的find方法找数据, TreeBin的find方法即是从红黑树里找数据, 若是ForwardingNode说明此时当前ConcurrentHashMap正在扩容, 且当前位置上的数据已经转到了新Node数组上, ForwardingNode的find方法会在新数组里找数据. get操作还是无锁的
  • put操作过程: 先根据key的hash定位到Node数组对应的位置, 然后根据该位置上有没有数据, 是怎样类型的数据进行下一步操作:
    • 如果该位置上无数据(为null), 就直接通过cas操作直接放入新数据, 都不需要锁操作
    • 如果为ForwardingNode类型数据, 说明当前ConcurrentHashMap正在扩容, 这时当前线程会参与进扩容操作中, 并发的完成ConcurrentHashMap的扩容操作, 扩容完成后, 再向新Node数组put数据;
    • 如果不是以上两种情况, 说明在该位置存在形式为TreeBin或Node链表的数据, 并发生了hash碰撞, 此时会先对该位置的Node上锁, 然后判断具体的数据类型是什么, 如为TreeBin就将新数据放到TreeBin内的树结构中, 如果为链表就把新数据放入链表中, 如果新数据加入后链表长度大于8, 就会将链表转为TreeBin形式
    • 当put操作完成后, 如ConcurrentHashMap内数据量超过map的当前最大容量(sizeCtl), 就会触发扩容操作; 这个扩容阈值只在第一次初始化时为容量/加载因子, 扩容后会是新数组长度*0.75
  • 扩容操作过程: 扩容时会先创建长度加倍的新Node数组, 然后遍历旧数组, 将旧数组上的数据迁移到新数组, 过程类似于HashMap, 不过迁移过程中会对迁移中的旧Node数组对应节点上锁, 对应位置上的数据迁移完后, 会在旧数组对应位置上放入hash为MOVED(-1)的ForwardingNode对象, 以表明该节点上的数据迁移到新数组了, 之后发生在该旧节点的get操作会被ForwardingNode导流到新数组, 而发生在该节点的数据改动操作会让对应的操作线程加入到扩容操作中, 直到扩容完成, 再到新数组中继续操作
  • remove数据时, 如果remove操作发生在红黑树上, 也会判断操作后的树的层数是不是小于3, 如果小于三层, 会将该红黑树降级为链表

总结

  • java8的HashMap系容器通过引入红黑树, 将哈希碰撞严重时的复杂度由O(n)降为O(lgn), 较大的提升了哈希碰撞严重时的性能, 解决了旧版实现的hash碰撞拒绝服务攻击问题
  • 比起java7的实现, java8的ConcurrentHashMap实现更多的使用了cas操作, 更少的使用了锁操作, 且锁分段的个数就是Node数组长度, 锁竞争会更少, 伸缩性会更好, 同时数据结构更为扁平, 不用像旧实现一样两次定位了
  • java8的ConcurrentHashMap的扩容实现比java7的更可控, 同时还允许多线程扩容, 使得扩容操作能更快的完成, 但单次扩容的开销会比分段扩容的java7实现要大
  • java8下若想让ConcurrentHashMap达到极致性能, 可以在构造时预估一个容量的极大值max, 以保证不会发生扩容, 如有需要还可将该max设为max /* 2的整数次幂, 来让数据分布的更离散以减少哈希碰撞, 而碰撞少的话其性能会接近于无锁组件, 操作的时间复杂度也会趋近于O(1). 构造中的另两个参数已被弱化, 可以不再使用
  • 使用低版本java的同学可以升级了, Map性能提升只是java8新特性的冰山一角, 技术人只能拥抱变化
thanq wechat
扫一扫订阅我的微信公众号