HashMap

JDK1.7以及之前由数组加链表实现

JDK1.8以及之后由数组加链表加红黑树实现

底层结构

为什么是2的幂次方？因为计算数组下标的时候要用到数组长度

默认容量为16且必须是2的幂次方

最大容量是2^30

默认负载因子是0.75

阈值=容量*负载因子。添加键值对后，如果键值对的个数 > 阈值，则进行扩容

红黑树是一棵自平衡的二叉查找树，解决了链表线性查找的性能问题

树化阈值=8。当桶的链表上元素个数 >= 8则链表转成红黑树

非树化阈值=6。当桶的链表上元素个数 <= 6则红黑树转成链表

树化阈值的最小容量=64。数组的长度 >= 64 && 桶上的链表元素个数 >= 8才会进行树化，否则进行数组扩容，扩容后的容量是旧的2倍，即旧值左移1位

首先计算hash() = (key.hashcode) ^ (key.hashcode >>> 16)。再用(数组长度 - 1) & hash()。1. hashcode的高16位与低16作异或运算，使得hash出来的值更加普遍2. hash出来的值通常很大，如果采用%运算，则基本都会落到数组最后面部分的桶上。数组长度限制为2幂次方后，数组长度-1得到的二进制就是全部二进制位为1，因此采用&运算只有个操作数为1才是1。3. &运算比%运算、/运算要快

put元素进去时计算数组下标

源码

1. key的hashcode高16位与低16位作^异或运算，降低hash冲突的概率，使数据均匀分布

2. 采用链地址法链接具有相同hash值的元素

3. 链表查询性能是O(n)，红黑树是O(logN)。链表变长查询性能下降，而红黑树是一个二叉查找树。而且红黑树不是绝对平衡，省去非必要的左旋右旋。

HashMap如何解决冲突的？为什么链表转红黑树

添加键值对后，如果键值对个数  > 阈值(数组容量*负载因子)，‌则扩容。新容量是旧容量的2倍(旧容量左移1位)

数组长度小于等于64时，直接扩容可以重新分配数据的位置，‌比树化要好，树结点的大小比普通节点大两倍。‌其实是在时间和空间权衡

数组某个桶上链表长度 >= 8，且数组长度 < 64时，也会扩容而不是链表转红黑树。

什么时候扩容？

计算下标一般采用取余操作。‌如果取余操作中除数是2的幂次方，则等价于与除数减1作&运算。‌而且&运算速度比%运算速度快

因此采用了 数组长度n-1 & hash()计算下标。‌当n为2的幂次方，n-1的二进制为全是1，不管hash()的值是多少，‌算出来的下标都不会数组越界。

如果不是2次幂，n-1二进制位不全是1，‌那么不同的hash值分别做&运算计算下标，会得到相同的下标，增加了数据冲突

数组长度为什么要2的幂次方

如果桶上没有链表只有1个元素，jdk1.7以前和jdk1.8以后都要重新计算

使用split()方法进行拆分

该元素是树节点

用hash()值与旧容量的二进制那一位做&运算，如果结果等于0，则下标不变，如果结果 等于1，则下标等于原位置+旧容量

该元素是链表节点

如果桶上有元素

扩容时，每个Entry都要计算1次吗

链表越长，查询性能越低

树节点占用空间是普通节点的2倍。要考虑时空权衡

为什么桶中个数超过8才转红黑树，又为什么有时候要从树转链表

jdk1.7以前，多线程情况下，会形成环链或者数据丢失

jdk1.8以后，多线程情况下，会覆盖数据

HashMap是否线程安全

使用Node+CAS+synchronized。synchronized只锁桶的链表或者树的首节点

ConcurrentHashMap原理

面试问题

HashMap