# HashMap 底层如何实现
以上为整体类继承结构
主要特点
数据以键值 (kay-value) 对方式储存的一个集合容器
key 不重复
可以使用 null 的键和 null 的值
不保证 key-value 映射的顺序
非线程安全实现
数据结构
- JDK1.7: 数组 + 链表
- JDK1.8: 数组 + 链表 + 红黑树
HashMap 性能参数 q
- 初始容量 capacity: 创建数组的长度默认是 16, 如果太少，很容易触发扩容，如果太多，遍历数组会比较慢
- 负载因子 loadFactor: 一个衡量的尺度，数组长度达到多少的时候触发数组自动扩容，默认为 0.75
- 阈值 threshold:
阈值=容量*负载因子，默认16*0.75=12, 当元素数量超过阈值时触发扩容
# 多线程条件下 HashMap 有什么问题吗
- 多线程条件下会导致死循环的问题，导致 CPU100%
- 多线程 put 可能导致元素丢失
- put 和 get 并发时，可能导致 get 为 null
# HashMap 链表节点过深时为什么选择使用红黑树
该问题要根据二叉树的特性来回答
二叉查找树
强平衡二叉查找树
弱平衡二叉查找树
红黑树
# 什么是 hash 碰撞，发射 hash 碰撞怎么办
定义：对于不同的关键字，可能得到同一个 hash 地址，即 key1!=key2 而 f (key1) == f (key2), 对于这种现象称之为 hash 碰撞，也叫 hash 冲突
一般 hash 冲突只能尽量地减少，无法完全避免，因为关键字在理论上可以有无限多个，而用来储存这些关键字的数组容量有限的，所以就必然会导致 hash 冲突，只能通过选择合适的 hash 函数来降低发生 hash 冲突的概率
具体解决办法
- 开放地址法：当发生 hash 冲突的时候，按照某种方法继续探测 hash 表中其他储存位置，一直找到空位置为止
- 再 hash 法：发生冲突时再次 hash, 直到没有冲突
- 链地址法 (HashMap 采用的方法): 当发生 hash 冲突时，以链表的方式储存冲突元素，插入方式头插尾插均可.(虽然该方法是一种不错的解决方式，但也存在一些明显的弊端，在极端情况下，查询的时间还是会达到 O (n) 级别，此时哈希表退化成普通链表，此时查找元素，时间复杂度为 O (n). 因此，在链表达到一定长度后，把链表转化为一棵树可以提高查找效率，HashMap 源码中就是这么实现的。当数组长度大于 64, 且数组某个位置上的链表长度大于 8 时，就会把数组某个位置上的链表转换为一棵红黑树)
# ConcurrentHashMap 底层如何实现
在 JDK1.7 和 JDK1.8 实现方式不同
- 1.7: 数据结构为 Segment [] 数组 + HashEntry [] 数组 +; 链表，Segment 继承 ReentrantLock, 采用分段锁 (默认 16 把锁), 每一把锁只锁一个 Segment
- 1.8: 数据结构为 Node [] 数组 + 链表 + 红黑树，初始化 Node 数组采用 CAS+volatile; 放数据时采用 synchronize
