Kosmos

HashMap

不支持并发操作
HashMap里面是数组,数组中的每一个元素都是单向链表

特征值

capacity:当前数组容量,始终保持 2^n,可以扩容,扩容后数组大小为当前的2倍
loadFactor:负载因子，默认为 0.75,负载因子越接近1,数组就越密,查找效率低,越小就越疏,数组的利用率就低
threshold:扩容的阈值,等于capacity*loadFactor
在计算key的哈希值的之后让key的hash值与高16位进行异或运算,减少了hash冲突
扩容:当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素,将容量扩大为原来的两倍,并将原来的数组迁移到现有数组中,迁移过程中，会将原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16，那么扩容后，原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置
默认容量:16

Java7中的HashMap

Put方法

1. 放入第一个元素时初始化数组大小
2. 根据key存放value
   1. key为null,这个value放到 table[0] 中
   2. key非null,得到hash的key值,通过indexFor方法计算出数组的下标,遍历一下对应下标的链表,假如有重复(key的判重),直接覆盖并返回旧值,否则就将value添加到链表上

初始化数据

大小为大于输入数字的最小2的n次方,不输的话默认是16
阈值等于capacity*loadFactor

计算对应的数组下标

取key的hash值的低n位(n根据数组大小确定),假如数组大小为32.那么取hash的低5位

添加节点到链表

将新值放入到链表的表头(注意是表头)
假如当前的容量大于阈值并且要存放的数组位置有值了,那么就要扩容,扩容后重新计算存放的位置

Get方法

1. 计算hash值:得到key的hash值
2. 获取数组的下标:hash的低n位
3. 遍历下标对应的链表

Java8中的HashMap

采用数组+链表+红黑树
链表中元素有8个并且散列表容量大于64时会自动转化为红黑树
根据第一个元素是Node或者是TreeNode来确定是链表还是红黑树

Put方法

1. 放入第一个元素时初始化数组大小(初始化大小到默认的16或者自定义大小)
2. 通过Hash找到数组的位置
   1. 假如该位置没有值,就放入其中
   2. 已经有元素的话,判断第一个元素的key和插入值的key是否相等,假如相等就覆盖并返回旧值
   3. 判断是红黑树还是链表,红黑树的话就调用红黑树的插入方法,链表的话插入到链表的最后面(假如插入的值是第八个,链表会调用treeifyBin方法变化成红黑树)
   4. 假如插入后超过阈值就进行扩容(resize)

扩容的时候假如是链表,会被拆分两条链表

Get方法

1. 计算key的Hash值,根据hash值找到数组的下标
2. 假如是链表,遍历链表,假如是红黑树就遍历红黑树

ConcurrentHashMap

并发安全

特征值

concurrencyLevel:并发数,Segement默认是16,表示最多可以同时支持 16 个线程并发写
initialCapacity:整个ConcurrentHashMap的容量,Segment 数组不可以扩容
loadFactor:为每个Segement内部使用
segementshift:2的sshift次方等于ssize，segmentShift=32-sshift;segementMask=ssize-1(确保低位都是1来使得获得的hashcode均匀分布
不允许key和value是null

Java7中的ConcurrentHashMap

ConcurrentHashMap是一个Segement数组,可以对单个Segement加锁
Segment 数组不可以扩容,默认每个Segement容量大小为2
初始化完成后得到一个Segement数组,只初始化了一个Segement[0]
Segement内部是数组HashEntry+链表
每一个segement对象都有一个count数(volicate)来统计内部的entry数量,加入count大于阈值会扩容成原来的两倍;统计size的时候前两次不加锁(如果出来的数据变了的话),在将remove和put方法锁住进行统计

Put方法

1. 计算key的hash值
2. 根据Hash值找到Segement位置下标j(计算方法:(hash >>> segmentShift) & segmentMask)
3. 对Segement[j]初始化,根据当前的Segement[0]来初始化Segement[j],并发操作使用 CAS 进行控制
4. 将新值插入到对应的Segement槽中
   0. 获取Segement的独占锁,循环调用tryLock获取
   1. 通过key的Hash值得到数组下标(table.length - 1) & hash
   2. 得到该位置的链表表头,遍历链表查看是否有重复值,有的话覆盖旧值并返回旧值
   3. 将改新值节点设置为表头,假如超过了该Segement阈值则需要扩容(Rehash),然后在进行插入操作,由于entry的next是final,所以只能在表头插入元素
      扩容是对Segement内的HashEntry数组进行扩容,扩容成两倍,扩容后,将原数组位置 i 处的链表拆分到 新数组位置 i 和 i+oldCap 两个位置

Get方法

get方法不用加锁,所用的变量都是volilate修饰,volatile可以保证内存可见性，所以不会读取到过期数据。

1. 计算Hash值,找到Segement(槽)
2. 根据Hash值在Segement内部数组中找到下标
3. 遍历链表

remove()元素后该元素后面的元素顺序不变,前面的会变成倒序(是从表头插入的)

Java8中的ConcurrentHashMap

加入了红黑树
构造函数初始化(设置sizeCtl)
通过提供的初始化容量大小设置sizeCtl
sizeCtl:(1.5 * initialCapacity + 1),然后向上取最近的2的n次方
sizeCtl数值:-1(初始化) ,-n(有n-1个线程正在扩容),正数(下一次要扩容的大小)或0(没有初始化)

初始化数组

通过CAS将sizeCtl设置成-1,通过判断sizeCtl来判断是否被初始化,并设置默认值

链表转红黑树

对链表加锁,遍历链表,建立红黑树,并设置到对应的位置.不一定转化成红黑树,有可能就是数组扩容

数据迁移

将旧的数组大小分配给多个线程
数组第一个元素的hash值假如是MOVED(-1),表明正在迁移,迁移要判断是链表还是红黑树
迁移可以多线程并发,线程加入使sizectl自增,线程退出后sizectl自减
数据迁移的时候要得到当前数组位置元素的Sychronized锁

Put方法

1. 假如数组表为null,则初始化数组
2. 通过key的Hash值得到数组的下标位置
   1. 数组头元素位置是空的.那就使用CAS将新值写入
   2. 数组头元素位置非空,判断是否是链表,如果是链表,就遍历链表,查找重复值,有重复值就覆盖并返回旧值,没有重复值就将新的节点放到最后;如果是红黑树,就按红黑树的插入方法插入
3. 插入后判断链表是否大于8并且数组长度是否大于64,只有前面两项都满足时才会转化成红黑树,否则就是扩容数组

Get方法

1. 计算hash值
2. 通过Hash找到数组的下标位置
3. 在链表或者红黑树中查找数据

---

标题：学习笔记|HashMap和ConcurrentHashMap
作者：ellenbboe
地址：https://ellenbboe.github.io/articles/2019/07/23/1563870255078.html