Map集合

2018-12-13  本文已影响0人  哓晓的故事

table的大小必须时2的幂次方，源于方便扩容
定位方式，通过key的hashcode值通过再散列h=hashcode^h>>>16的值找到对应的链表，然后equal链表中的val是否相等
hashMap中的红黑树只是TreeNode
conccurentHashMap中的红黑树是TreeBin包装的，提供了读写锁
HashMap源码分析
HashMap图文解释
JDK1.7 -> 头插法 -> 查找时间复杂度O(n)链表
JDK1.8 -> 尾插法不会出现死循环和逆序问题 -> 查找时间复杂度O(logn)红黑树

HashMap

JDK1.8-JDK1.7 HashMap差异.png

get

1. 链表存在
2. n=tab.length, 使用 first = tab[(n - 1) & hash] 获取hash值在链表中的首个位置
3. 如果第一个值就匹配hash和key，立即返回
4. 如果下一个节点存在
  1. 如果节点为红黑树
  2. 否则，循环链表获取与key相等的值

put

1. 如果表不存在, 初始化表
2. 如果表存在, 且值hash与表length &后Node not exists，新增Node
3. 否则, 对比 key是等于第一个node
  1. 如果是, 使用这个node
  2. 否则, 如果是红黑树
  3. 否则
    1. 如果没有下个节点，新增一个节点，若链表长度大于8，做红黑树排序处理
    2. 否则，判断下个节点的key是否等于当前传入的key
- 将变更的节点移动到Map的last
- 增加余数
- 如果表大小大于阀值，扩容表

hash

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

key哈希值与key哈希值右移16位，做异或，可以减少冲突量
JDK1.7 -> 9次扰动处理=4次位运算+5次异或
JDK1.8 -> 2次扰动处理=1次位运算+1次异或

resize

1. 获取oldTab的length(不存在为0)
2. 如果存在oldCap>0
    1. 超过最大容量, 设置全局阀值(threshold)为int的最大值
    2. 将oldCap左移一位(扩大一倍), 且旧容量超过初始默认容量, 将threshold左移一位(扩大一倍)
3. 否则, 如果存在oldThr
    1. 设置newCap为oldThr
4.  否则, 使用初始化值 cap=1<<4, threshold=loadfactory(=0.75)*cap
5. 如果不存在 oldTab, 返回newTab
6. 否则, 遍历旧的 oldTab, 如果存储的node存在
    1. 如果 next 没有指向下一个 node, 则赋予新表->newTab[e.hash & (newCap - 1)] = e;
    2. 否则, 如果 node 为TreeNode(红黑树) -> TODO
    3. 否则, 采用原始位置加原数组长度的方法计算得到位置`hash & oldCap` -> 用到了oldCap来计算key的hash值是否超过

// (e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下（jdk1.8则是用旧容量&来判断，如果为0说明无需移位，否则需要移位）
// (e.hash & (oldCap-1)) 得到的是下标位置（jdk1.7每次resize的位置都是与newCap-1重新计算得出）
// 以上两种方式可以获取新的数值下标，并且重新随机分布，而不会出现死循环问题
// 这是 JDK1.7 和 JDK1.8的区别

ConcurrentHashMap

JDK1.7
JDK1.8.png

get

  1. 根据key算出spread()[等于hash()]
  2. n=tab.length, 使用 first = tab[(n - 1) & hash] 获取hash值在链表中的Node链表
  3. 如果第一个值就匹配hash和key，立即返回
  4. 否则，循环Node链表获取与key相等的值
    1. 如果是红黑树
    2. 如果当前线程存在(写锁 或者 有waiter)，使用链表查询
    3. 否则，读锁+1，最后读锁-1，且是最后一个读锁，释放写线程阻塞

put

  1. 根据key算出spread()[等于hash()]
  2. 如果table不存在，初始化
    1. 使用sizeCtl来做自旋锁控制，做CAS
    2. sc = n - (n >>> 2); // sizeCtl 设置为0.75*n
  3. 否则，如果table存在，但是hash没有命中，casTabAt新增节点
    1. table是volatile修饰的，但不能保证线程每次都拿到table中的最新元素
    2. Unsafe.getObjectVolatile可以直接获取指定内存的数据
  4. 否则，如果为MOVED，说明hash 正在扩容搬移数据中
    if ((fh = f.hash) == MOVED)，执行helpeTransfer 协助扩容
  5. 否则，锁住整个Node链表头(这已经解决了写写锁问题)
    1. 如果f.hash >= 0，说明f是链表结构的头结点，遍历链表设置key
    2. 如果是红黑树，使用红黑树key进行putTreeVal
      1. 查找是否存在key, 存在则覆盖val，否则新建treeBin
      2. 在做红黑树balanceInsertion() -> 参考 Map里面的旋转前后要做加锁和解锁 
          1. 无写锁 -> +写锁 -> 加锁失败往下走
  /// 下方是一个死循环，直到1才能结束
  1. 如果有写锁，无读锁 -> +读锁 -> 加锁成功设置waiter为null
  2. 否则，如果有写锁，有读锁，无waiter -> +waiter
  3. 否则，如果有写锁，有读锁，有waiter -> 阻塞自身，等待写锁释放
    3. 如果节点数超过8，将其转为红黑树
      addCount() 增加计数器，如果sizeCtl达到扩容要求，扩容

remove

在删除过程中，需要加sync锁
如果链表删除要注意，如果删除首节点和非首节点要特殊处理
如果是红黑树，删除后，要重新对红黑树队列做调整（删除过程中要加锁和解锁，参考put的）

1. 先判断是否时首节点，做prev和next处理后
2. 如果树节点较少，返回true用链表处理
3. 否则，返回false，说明已经红黑树处理完成了
4. 找到红黑数最左边的节点，然后交换节点的颜色
5.

resizeStamp

Integer.numberOfLeadingZeros -> 计算一个int型值二进制中第一个1前面0的个数
将RESIZE_STAMP_BITS位数值置为1
保证返回的数值变为负数

tryPresize 扩容

  1. 构建一个nextTable，大小为table的两倍[这个过程只能一个线程]
  2. 把table的数据复制到nextTable中[采用辅助多线程来进行复制]

addCount 增加修改次数，选择扩容

// 此方法设置 sizectl 为负数, 标识正在扩容
U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
// 此方法标识协助扩容，线程个数数量+1
U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)

多个线程辅助转移数据，会导致冲突频繁，因此设置了一个步长，相当于不同的线程转移table 中不同 位置段 上的数据，这样可以减小冲突

transfer

为了方便并发扩容，减少线程之间的冲突，设置了步长stride，每个线程转移table中位置不同的数据
扩容拷贝, 和HashMap的resize扩容时的原理类似，加上并发控制

transfer.png

size

[JDK1.7]

  1. 最多计算3次，前2次计算结果做比对(使用modCount作为是否变更数据的计数器)
  2. 如果前2次结果相同，则总数准确，退出
  3. 否则，结果不准确，对segment加锁后再计算一次
  4. 使用segment，锁粒度粗

[JDK1.8]
提前到变更时做CAS

  1. 获取基本计数器 baseCount 使用 volatile(不考虑并发的计数器)
  2. 对实时计数器值做过counterCells中的变更value累加
  3. 去除segment，但是每次更新操作，进行计数

baseCount和counterCells时在变更动作后调用addCount()来记录
如果不存在counterCells，使用fullAddCount()初始化
循环 cellValue，baseCount，cellBusy来加锁，初始化cellValue值

foreach

遍历迭代期器具有 弱一致性，允许修改
在删除节点时，使用e = e.next的方式，这时候删除的节点还是右指向下一个节点

上一篇下一篇

猜你喜欢

热点阅读