Day 41 复习HashMap和ConcurrentHashM

ConcurrentHashMap

size实现
先采用不加锁的方式，连续计算元素的个数，最多计算3次：1、如果前后两次计算结果相同，则说明计算出来的元素个数是准确的；2、如果前后两次计算结果都不同，则给每个 Segment 进行加锁，再计算一次元素的个数；
JDK1.8：第一次put的时候才会进行初始化Node数组，底层是以node节点的形式存储，每次锁都是对node节点锁，每次出现哈希碰撞都是在同一个node节点以单项链表的方式进行存储。当链表长度>=8，就会转换成红黑树,他这里放弃了分段锁，使用了CAS+Synchronized操作来确保Node的一些操作的原子性，取代了锁
put实现
1、如果没有初始化就先调用initTable（）方法来进行初始化过程；
2、如果没有hash冲突就直接CAS插入；
3、如果还在进行扩容操作就先进行扩容；
4、如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；
5、最后一个如果Hash冲突时会形成Node链表，在链表长度超过8，Node数组超过64时会将链表结构转换为红黑树的结构，break再一次进入循环；
6、如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容
size实现
1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount；1、初始化时counterCells为空，在并发量很高时，如果存在两个线程同时执行CAS修改baseCount值，则失败的线程会继续执行方法体中的逻辑，使用CounterCell记录元素个数的变化；2、如果CounterCell数组counterCells为空，调用fullAddCount()方法进行初始化，并插入对应的记录数，通过CAS设置cellsBusy字段，只有设置成功的线程才能初始化CounterCell数组；3、如果通过CAS设置cellsBusy字段失败的话，则继续尝试通过CAS修改baseCount字段，如果修改baseCount字段成功的话，就退出循环，否则继续循环插入CounterCell对象；
元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数；
扩容
当put或者执行时需要扩容，另一个线程也进来了。会通过helpTransfer()方法协助扩容(进行分段，不同线程负责不同模块数据的迁移)，同时对应扩容的线程数会+1
当多个线程进行扩容时：

通过这个方法计算每个线程负责扩容的长度；
1.8为什么弃用分段锁，使用节点锁(synchronized+cas)
1、加入多个分段锁浪费内存空间。
2、生产环境中， map 在放入时竞争同一个锁的概率非常小，分段锁反而会造成更新等操作的长时间等待。
3、为了提高 GC 的效率
为什么不用ReentrantLock而用synchronized ?
减少内存开销:如果使用ReentrantLock则需要节点继承AQS来获得同步支持，增加内存开销，而1.8中只有头节点需要进行同步。
内部优化:synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。

---

HashMap

HashMap

1.7

1.8
Get,put操作时间复杂度都是o(1)

如果说：写了初始容量：11 ？hashmap的容量就是11？

hashmap的get，put操作时间复杂度O(1)

key.hashCode = 不确定 - 有符号的整型值

key.hashCode % 16 = table.lenth = [0-15] = index = 3;

array[index] = value;

数组所有的元素位是否能够100%被利用起来？

不一定，hash碰

引入链表结构解决hash冲突，采用头部插入链表法，链表时间复杂度O(n)

N代表链表的长度

hash并不是用取模计算index，而是用位运算！

效率：位运算>%

并没有说hashmap的容量一定是16，

数据结构
数组+链表+(红黑树jdk>=8)

从上面的注释的初始容量必须是2的倍数为什么呢
是为了能够完整的打散hashcode均匀分布到table中
源码原理分析
重要成员变量

DEFAULT_INITIAL_CAPACITY = 1 << 4

Hash表默认初始容量16

如果写了初始容量，那么初始容量是多少呢

MAXIMUM_CAPACITY = 1 << 30

最大Hash表容量

DEFAULT_LOAD_FACTOR = 0.75f

默认加载因子

TREEIFY_THRESHOLD = 8

链表转红黑树阈值

UNTREEIFY_THRESHOLD = 6

红黑树转链表阈值

MIN_TREEIFY_CAPACITY = 64

链表转红黑树时hash表最小容量阈值，达不到优先扩容。
内部的执行机制源码
HashMap是线程不安全的，不安全的具体原因就是在高并发场景下，扩容可能产生死锁(Jdk1.7存在)以及get操作可能带来的数据丢失。