容器思维导图
map的KV应避免为null
主要map类集合.png
HashMap的底层结构/HashMap如何解决哈希冲突
HashMap采用链地址法处理哈希冲突，它由数组+链表组成，底层结构是一个数组，而数组的元素是一个单向链表，当哈希冲突时，会将新值接入链表尾部
HashMap重写equals时，为什么要重写hashCode
HashMap用hashcode方法定位桶的位置，equals方法判断是否重复。如果重写了equals而没有重写hashcode方法，就会出现equals返回ture，但是hashcode不相同的对象，分处两个不同的桶，即在HashMap看来是两个不同的对象，显然不符合equals方法的定位。
HashMap如何定位桶的位置
- 处理hash，将HashCode()的高16位和低16位异或
- 对桶个数取模，
index = h&(length-1),因为length总是2的n次方，所以等价于对length取模。
为何HashMap的数组长度一定是2的次幂
保证（length-1）二进制低位都为1，这样做有三点好处
- 减少哈希冲突，例如01010101和01010111 与01111101作&运算得到的都是01010101。
- 减少扩容时的开销，扩容前和扩容后的（length-1）二进制只在最高位（最左边的1）有差异，当最高位hash为0时，下标不变；为1时，新下标=旧下标+旧容量。
- 性能考虑，当length总是2的n次方时，对length取模可用&运算优化，具有更高的效率
HashMap在jdk8优化了哪些
- 优化了hash，将HashCode()的高16位和低16位异或，这么做可以在数组比较小的时候，也能保证考虑到高低位都参与到数组槽的计算中去。有效解决低位与操作碰撞的问题。
- 链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能
- 优化了扩容后的下标重排的算法，当最高位hash为0时，下标不变；为1时，新下标=旧下标+旧容量。
- 延迟初始化，第一次put数据时才进行HashMap的初始化。
HashMap多线程使用会导致死循环的原因
企业微信截图_b5ee2bcb-775a-4b65-ae96-e98c095e274a.png
- 无论哪个版本的hashMap都是采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点
HashMap添加数据的过程
- 第一次使用时初始化容器
- 计算元素所要储存的位置index
- 判断该链是否为红黑树并添加元素
- 超过容量阀值，扩容
HashMap什么时候扩容
当数据量达到容量*负载因子时发生扩容。
HashMap和LinkedHashMap的区别
- HashMap无序，LinkedhashMap有序
- LinkedhashMap是由HashMap+双向链结构组成的，内部类Entry多了before和after两个属性分别用来存储前置和后置节点。
ConcurrentHashMap核心
- sizeCtl 标示位，同时也是扩容阀值
- ForwardingNode 扩容时表示已经处理过的占位符
- CAS+Synchronize确保并发安全
- 如何统计元素的个数？counterCells
- 扩容过程
- put流程
- 触发扩容的时机
ConcurrentHashMap触发扩容的时机
- 槽数小于64且存在某一个槽位链表个数大于等于8时触发
- 第一次put时扩容
- 超出扩容阀值（sizeCtl）时
ConcurrentHashMap put流程
- 第一次put初始化table
- 通过处理过的hash确定槽位
- 槽位没数据时，将数据CAS方式放在槽位上
- 槽位正在扩容处理时，协助扩容
- 槽位上有数据时，获取链表头锁（Synchronize），并将数据插入链表尾部（重复数据情况略）
- 该槽位数据量大于等于8时，扩容或者转红黑树
- 记录槽位数据量
- 判断是否需要扩容
ConcurrentHashMap扩容流程（不考虑红黑树）
- 创建新容器nextTable
- 遍历旧容器所有槽位
- 如果槽位上没有数据，槽位标记为已经处理
- 如果槽位已经处理，跳过
- 获取槽位链表头锁，同HashMap拆成两个链表分别放入nextTable对应槽位中
- 原槽位标记为已经处理
- 遍历完后，将新容器替换旧容器，设置新阀值
ConcurrentHashMap是如何统计元素的个数
- 每当线程 put 一个元素到容器中，先尝试CAS算法累加到 BASECOUNT 上，如果失败，线程会被映射到一个 CounterCell 对象上采用 CAS 算法自旋地对其属性value进行加 1 操作，
- 统计时，BASECOUNT +所有CounterCell的value
- 元素个数是热点数据，这么做是为了减少cas自旋的次数
使用@sun.misc.Contended修饰CounterCell，消除伪共享带来的性能开销
- @sun.misc.Contended的作用：使得被修饰对象独立占用一个缓冲行。
- 使用场景：主要适用于频繁写的共享数据上
- 什么是伪共享： 每个CPU 读取数据后都会存到自己的缓存里，为了节省空间，一个缓存行可能存储着多个变量，即伪共享
- 伪共享带来的性能开销：CPU修改缓存A类数据时，会导致同一缓存行的B类数据也失效，倘若A类数据写操作频繁，B类数据读操作频繁，CPU需要经常从内存中重新读取B类数据。
ConcurrentSkipListMap
- 跳表是可以实现二分查找的有序链表；
- 每个元素插入时随机生成它的level（怎么生成的？）
- 最低层包含所有的元素；
- 如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
- 每个索引节点包含两个指针，一个向下，一个向右；
- 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；
ConcurrentSkipListMap put流程
- 查找key的前置节点A
- 如果A下一个节点B的key与要加入的key相等，则cas修改B的值
- 创建新的节点，cas方式在A与B之间加入一个新节点
- 随机生成索引level
- 在小于level的索引中查找合适位置加入索引节点
- 如果level大于当前最高索引level，则创建新的索引
Map比较
| 容器 | 数据结构 | key能否为空 | value能否为空 | 并发安全 | 如何实现并发安全 | 有序 |
|---|---|---|---|---|---|---|
| HashMap | 数组+链表/红黑树 | 允许 | 允许 | 否 | - | 否 |
| LinkedHashMap | HashMap+双向链表 | 允许 | 允许 | 否 | - | 只支持插入顺序和访问顺序 |
| TreeMap | 红黑树 | 不允许 | 允许 | 否 | - | 是 |
| ConcurrentHashMap | 数组+链表/红黑树 | 不允许 | 不允许 | 是 | CAS + Synchronize | 否 |
| ConcurrentSkipListMap | 跳表 | 不允许 | 不允许 | 是 | CAS | 是 |
为什么ConcurrentHashMap不允许key为null，而HashMap允许
- HashMap对key为空的情况做了特殊处理，当key为空时返回的hash为0
- 其他容器并没有这么做
为什么ConcurrentHashMap不允许value为null，而HashMap允许
- value允许为空存在二义性，1 指定key并未在容器中映射过；2 put操作时value就为空。
- 单线程情况下，可以通过containKey方法区分，因此HashMap等非并非安全的容器允许，多线程情况则不行，因此Concurrent系容器都不允许
- value为null在Concurrent系代码实现中存在特殊含义，例如ConcurrentSkipListMap中表示数据正在被删除。
