HashMap在JDK1.7和1.8的实现是有些不同的。
在JDK1.7中，HashMap 的实现是 数组 + 链表
在JDK1.8中，HashMap的底层实现是数字 + 链表/ 红黑树
key的要求
HashMap的key可以为null，而且只能有一个key为null
- 重写hashCode()和equals()方法
- key的内容是不可变的，否则可能查找不到
先来复习一下HashMap的实现原理，在HashMap中有一个Node数组，其中Node中存储key-value和key的hash值，同时这个Node也是一个链表中的一个节点。
我们称这个数组是桶
put
当我们调用HashMap的put方法进行存储时，首先会计算key的hash值，将key-value、hash值封装成一个Node.
利用key的hash值与此时HashMap的桶体积做模运算，计算出要存储的位置
index = hash % capacity
// 由于capacity 是 2的次幂
// 所以以上等价于
// 使用位运算，能够更快
index = hash & (capacity - 1)
**如果此时桶中此时的位置是空，则将此Node放在这个位置。
如果此时桶中这个位置已经有元素了
- 如果两者的key的hash是相同的，或者key的equals()是相等的，则就是更新，将旧的value替换成新的value
- 如果两者的hash不同，并且key的equals()不相等，则代表key不相等，此时发生了Hash碰撞，此时就会拉链表或红黑树
来看一下源码中对这一部分的理解
// 此方法的参数 hash
// key
// value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab代表整个HashMap中的桶
Node<K,V>[] tab;
// 用来封装新的节点
Node<K,V> p;
// n 当前的桶容量 capacity
// i 计算出来的新的元素的桶中的index索引
int n, i;
// tab = table 引用桶，
// 如果tab ==null 或 tab.length == 0 代表还没有初始化，此时初始化桶
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 计算出新元素在桶中的索引 i
// 如果此时元素p为null, 则代表此位置为空，直接插入这个新的节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果p != null， 则代表此位置已经有元素了
else {
// 用e 临时的结点
Node<K,V> e;
// k代表此位置的旧的key
K k;
// 如果此时的hash相同,并且key相同
// 或 key的equals()相等
// 则代表此时的key是同一个，就更新value
// 统一修改的代码在下面
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 到此，已经不是同一个key了，
// 即发生了hash碰撞
// 选择是链表 还是红黑树来解决此问题
// 判断此节点是否是 红黑树的结点，
// 如果是，直接插入新的节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 判断到这一步，就是一个普通的结点了
// 说明key不相同，就需要拉链表了
else {
for (int binCount = 0; ; ++binCount) {
// 插入新的节点
// 插入完成后, e = null
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 发现key的hash相同 或 key 的equals()相等
// 即是发现了链表中有的节点的key是相同的则修改
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 这个代码统一修改了 桶中的 或 链表中相同key 的value
// 此时的e不为null，即要修改,将新的value赋给原来的value
// 返回旧的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
// 操作数 + 1
} ++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通过看源码，发现在put时，如果key相同则是修改value，那么将旧的value返回；如果key不相同，即是插入节点，调用put方法就会返回一个null
get
根据key来返回value
首先根据key计算出在桶中的索引，通过key的equals()判断是不是同一个key，如果是直接返回。
如果不是，则根据 链表 或 红黑树 继续找，直到找到这个key，然后返回
来看具体的一个源码
final Node<K,V> getNode(int hash, Object key) {
// 代表整个桶
Node<K,V>[] tab;
// 临时结点
Node<K,V> first, e;
// 桶容量capacity
int n;
K k;
// 首先桶不能为空
if ((tab = table) != null && (n = tab.length) > 0 &&
// first也就是在数组中的那个结点
// (n - 1) & hash 计算出索引
(first = tab[(n - 1) & hash]) != null) {
// 如果此时数组中的结点就是，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果数组中的结点不是,那么此处就是链表 或 红黑树
if ((e = first.next) != null) {
// 如果是红黑树，通过红黑树来查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 不是红黑树，直接迭代寻找，然后返回就好了
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
} return null;
}
扩容原理
HashMap什么时候发生扩容？
首先要知道几个概念，HashMap中的几个属性
首先一个概念就是capacity，就是桶的体积，即整个数组的大小，通过HashMap的无参创建时，默认是16。
- size：数量，此时桶中已经存储了多少元素（包括链表中的数量），即所有的已存储的结点的数量
- loadFactory：转载因子，默认是0.75
- threshold：临界值，threshold = capacity * loadFactory
当size超过threshold时，就会触发HashMap的扩容机制。
扩容时，会开辟一个新的数组，新的数组的容量是原始的2倍，根据原始桶中的每个元素的hash值重新计算索引index，然后拷贝放入新的数组中
扩容的这个过程是非常耗时间的。
来看源码
final Node<K,V>[] resize() {
// oldTab 旧的桶
Node<K,V>[] oldTab = table;
// oldCap 旧的桶的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr 旧的临界值
int oldThr = threshold;
// newCap新的容量, newThr新的临界值
int newCap, newThr = 0;
if (oldCap > 0) {
// 旧的容量不为0，
// 旧的容量是不是大于最大值
// MAXIMUN_CAPACITY = 1 >> 31;
// 已经最大了，无法扩容，临界值就是int的最大值
// 返回旧的桶
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 旧的容量是常规的
// newCap 翻倍
// newThr 翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 创建新的桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 开始拷贝原始的结点 进入新的桶中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的桶
return newTab;
}
初始化容量
为了在使用HashMap过程中频繁的发生扩容，建议在new HashMap对象时，通过构造方法传入一个指定的容量大小。
因为扩容是非常损耗性能的。
如果直接使用HashMap的无参构造来创建，则默认的初始化容量就是16
当我们传入初始化容量值时，并不是真正的初始化容量值。HashMap会经过优化，选择第一个大于等于此数值的2的次幂作为初始化的容量大小。
为啥要选择2的次幂作为容量初始化容量呢？
这样就能保证无论何时，HashMap的容量都是2的次幂
在计算节点的索引时，我们是通过求模来计算的
index = hash % capacity
直接的求模运算时非常耗时的，在计算机中最快的运算是位运算。
如果capacity是2的次幂，则以上公式就会利用位运算来优化
index = (capacity - 1) & hash
两者是等价的，但是位运算会快很多，性能更高。
如果capacity不是2的次幂，那么每次在put、get时直接进行求模运算，会浪费掉一些不必要的时间。
对初始化容量进行优化后，capacity保证是2的次幂，然后就能快速的计算出节点的索引。
除了能够快速的计算出索引的位置这一好处之外，还有一个好处就是
当进行扩容时，会用该节点的hash值与旧的容量做与运算
如果hash & oldCap == 0则元素保留在原来的位置，否则newIndex = oldIndex + oldCap
总结：容量为什么是2的次幂？
- 首先，为了快速计算索引
- 其次，为了扩容时快速计算出新的索引位置
初始化容量选择多少是合适的
我们知道有一个临界值
threshold = capacity * loadFactory
当size超过threshold时，就会触发扩容。
我们在初始化HashMap时，应当避免频繁地扩容，此时一个合适的初始化容量就能减少扩容次数。
用空间换性能。
对于HashMap中的loadFactory默认值是0.75，我们不建议修改，此时的HashMap的总和性能是比较好的。
- 如果loadFactory偏小，就会频繁触发扩容
- 如果loadFactory偏大，扩容时的压力就会大，占用过多的时间
所以这个默认的0.75是一个比较好的值，不建议修改。
那么初始化时，建议的初始化容量也是有一个公式
initCapacity = expectedCapacity / loadFactory
例如我们要存储7个元素
如果不套用以上公式，在创建时直接传入7，经过优化初始化容量是8，临界值是 8 * 0.75 = 6, 也就是当我们put 第7个元素时就会触发扩容。
套用以上公式
7 / 0.75 = 10
创建HashMap时，传入的值是10
HashMap map = new HashMap<String,String>(10);
10不是2的次幂，经过优化，初始化容量是16。
这样临界值就是 threshold = 16 * 0.75 = 12，我们put 7个元素是不会触发扩容的。
二次hash
在计算key的hash值时，并没有使用key的原始的hash值，而是再次进行了扰动，为什么？
看jdk1.8中HashMap中这个扰动的源码，hash()方法也称为扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先通过key的hashCode()方法来获取key的原始hash值，用这个值与右移16位后的值做异或运算，这样得到的值才是我们key-value中要用到的hash值。
这是扰动，为了保证key的hash值散列的足够均匀，避免在同一个地方的链表过长
链表与红黑树的转换
JDK1.7的实现是 数组 + 链表
JDK1.8的实现是 数组 + 链表 / 红黑树
在jdk1.7中，发生Hash冲突后，就会拉链表。当冲突频繁发生，就会导致此节点处的链表很长，在查找、插入时的效率就会降低。
那么如何避免链表过长呢？
可以选择扩容，扩容后的结点就会分散在新的位置，但是难免会存在极端的情况，会存在无论怎么扩容，链表长度都不会改变的情况。
然后jdk1.8中引入了红黑树，当链表长度超过8时，并且桶的容量大于等于64时，链表就会转换为红黑树 ，红黑树在插入、查找的效率是非常高的
链表查找一个元素的时间复杂度是O(n)，但是红黑树查找的时间复杂度是O(logn)。
-
为什么要用红黑树？
答：红黑树用来避免Dos攻击，防止链表过长，导致HashMap的性能下降，链表树化是概率比较低的情况。（在负载因子0.75的前提下，链表长度超过8的概率是非常非常低的，选择8是为了让树化的几率足够小） -
链表树化的情况？
链表长度超过阈值8，数组容量大于等于64 -
树退化为链表的情况？
- 在扩容时，如果拆分树，树元素个数小于等于 6 ，则会退化为链表。
- remove节点时，若root、root.left、root.right、root.left.left有一个为null则会退化为链表
并发下HashMap容易出现的问题
- 并发丢数据，多个线程修改了同一个key的value
- jdk1.7下，由于头插法，在扩容时，可能发生死链