HashMap
| HashMap | 说明 |
|---|---|
| 底层结构 | 1. JDK1.8之前：数组+链表 2. JDK1.8：数组+链表/红黑树 链表与红黑树之间的转换： 链表->红黑树：链表长度大于等于8且数组长度（hash桶）大于等于64的时候 红黑树->链表：红黑树的节点数量小于等于6的时候退化为链表 |
| 元素特性 | key、value可以为null，只能有一个key为null的键值对，允许有多个value为null的键值对 |
| hash桶的数量 | 默认16，加载因子默认0.75（HashMap也许是按照lazy-load原则，在首次put元素时在resize()方法中初始化） |
| 扰动函数 | 1. JDK1.8之前扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算 2. JDK1.8扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算 |
| 插入过程 | 1. 通过key的hashCode经过扰动函数处理过后得到hash值，然后对数组长度取模((n-1)&hash)得到数组下标 2. 如果没有产生hash冲突(下标位置没有元素)，则直接创建Node存入数组 3. 如果产生hash冲突，先利用equals进行比较，相同则取代该元素，不同，则判断链表高度插入链表（拉链法），链表高度达到8且数组长度到64则转表为红黑树，以减少搜索时间，长度低于6将红黑树转回链表 4. key为null，存在下标为0的位置 |
| 扩容 | 首先检测数组里元素个数(hash桶的大小)，当大于16*0.75=12的时候就会触发扩容，扩容成之前hash桶数量的2倍(2的幂) 会把之前那些元素再次进行一次哈希运算然后添加到新的hash桶里面，按照链表或红黑树的方式再排列起来 |
| 线程安全性 | 非线程安全 在插入操作的时候多线程情况下会有数据覆盖的可能 1.7：在put的时候还有个resize的过程，头插可能会形成一个环形链表导致死循环 1.8：改成尾插，解决了死循环问题，但仍然不建议在多线程环境下使用HashMap |
| hash桶的数量为什么是2的幂次方？ | 1. 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的 2. 但是我们不可能开辟一个长度为40亿的数组，用之前还要先对数组的长度取模运算，得到的余数才能用作数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。只有满足2的幂次方，(n - 1) & hash才能映射到0 |
为什么是(n-1)&hash？ |
取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；），并且 采用位操作 &，相对于%能够提高运算效率 |
| 为什么要树化？ | 链表查询是线性的，会严重影响存取性能，树实现可以提供可靠的O(logn)访问性能 |
ConcurrentHashMap
| HashMap | 说明 |
|---|---|
| 底层结构 | 1. JDK1.7：分段数组+链表 2. JDK1.8：改成了与HashMap一样的数据结构(数组+链表/红黑树)，使用synchronized+CAS来保证线程安全 |
| 扰动函数 | 同hashmap相似，1.8多了一个&操作保证hash为正数 |
| 实现线程安全的方式 | 1. JDK1.7：对整个桶数组进行了分段分割，加Segment分段锁(继承了ReentrantLock)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，并发度为分段个数（可以通过构造函数指定），数组扩容不会影响到其他的Segment 2. JDK1.8：直接用Node数组+链表/红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作，Node的val和next都用volatile修饰，保证可见性 CAS：查找、替换、赋值操作都使用CAS synchronized：锁链表的头结点，不影响其他元素的读写，锁粒度更细，效率更高，扩容时，阻塞所有读写操作，并发扩容 |
| 元素查询 | 1. JDK1.7：二次hash，第一次hash定位到Segment，第二次hash定位到元素所在链表的头部 2. JDK1.8：读操作无锁，Node的val和next都用volatile修饰，读写线程对该变量互相可见，数组用volatile修饰，保证扩容时被读线程感知 |
JDK1.8：hash的时候会 & HASH_BITS，用以保证其为正数。因为ConcurrentHashMap中会利用负值hash做特殊标识。
- Java8 ConcurrentHashMap 存储结构：
参考
留言
