HashMap简介
HashMap 底层是基于 数组+链表(JDK8之前) 数组+链表/红黑树(JDK8)
HashMap 是一个用于存储 key-value 键值对的集合，每一个键值对也叫 Node。这些键值对分布在一个数组当中。
HashMap 最多允许一条记录的键值为null .允许多条记录的值为null
存储结构
JDk1.8 的HashMap 的数据结构如下图，当链表的节点大于8时，会转为红黑树，当节点小于6时，红黑树又会转为链表。这里的树使用的数据结构是红黑树，红黑树是一个自平衡的二叉查找树，查找效率会从链表的o(n)降低为o(logn)，效率是非常大的提高。
基本属性
// 默认容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表节点转换红黑树节点的阈值, 9个节点转
static final int TREEIFY_THRESHOLD = 8;
// 红黑树节点转换链表节点的阈值, 6个节点转
static final int UNTREEIFY_THRESHOLD = 6;
// 转红黑树时, table的最小长度
static final int MIN_TREEIFY_CAPACITY = 64;
// 链表节点, 继承自Entry
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ... ...
}
// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
// ...
}
Hash算法
散列定位:
（n-1）& hash
- n: 数组的长度
- hash：key 的hashcode
其实上面的公式等于:
** 为什么 hash&(n-1) == hash%n ？ **
我们以长度为16位例:
n-1 的二进制为1111
那么无论hash的值有多大，永远只有后四位，和 n-1 进行与操作
hash&(n-1) 的最小值0 ，最大值为 n-1
而 hash%n 的值也是最小值为0，最大值为 n-1
HashMap 中的hash key 为 :
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们对上面的代码改造一下，易于理解:
static final int hash(Object key){
if(key == null) return o;
int h = key.hashCode();// 32位
int temp = h>>>16;// 向右移16位
int newHash = h^temp;//异或运算
return newHash;
}
整体分三个步骤:
- 拿到key的hashCode
- 将hashCode 的高位参与运算，重新计算hash值
- 将计算出来的hash值与(table.length-1)进行& 运算
为什么不直接用
hash%n
- 位运算消耗资源更少，更有效率
- 避免了hashcode为负数的情况
下面列举一个简单例子来说明hash的整个过程
当table数组长度为16时，table.length-1=15,15 的二进制: 1111即低4位全部为1，高位全部为0，因此此时hashCode&(table.length-1) 的运算结果取决于 hashcode的低4位，高28位就没有作用了，并且由于hash结果只取决于hashCode的后4位，hash冲突的概率会大大增加，因此，在 jdk1.8中，hash的高位也参与了计算，目的是为了降低hash冲突的概率。
我们以 “king”字符串为例:
为什么要先高16位异或低16位再取模运算
从上面来看：异或的情况下 0 和 1 出现的概率各为 50%
我们可以举一个例子:
(1) 直接用key的hashCode 和 (n-1) 进行&操作
我们从上图可以看到，当table[]数组的长度为16的时候，(16-1）的最后四位为1111，对于多个Key,只要哈希码的最后四位为0，不论高位怎么变化，最终的结果都为0，这时候产生碰撞的几率非常大，为解决这个问题，于是就有了hash码的低16位和高16位进行异或。
右移16位，自己的高16位和自己的低16位进行异或，以此来加大低位的随机性。
从上面来看，高16位和低16位异或，确实降低了hash碰撞的概率。
为什么capacity是2的幂？
因为我们算index的时候用的是
(n-1)&hash
,这样能保证 n-1 是全位1的二进制数，如果不全位1的话，没存在某一位位0，那么0,1与0的结果都为0，这样有可能讲两个hash不同的值最终装入同一个桶值，增加碰撞的几率。
HashMap put 原理
put 方法源码如下:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table数组是否为空或数组长度为0，如果为空，则通过resize进行初始阿虎
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据key得到hash值，然后和 数组长度-1 进行与操作得到当前key所在的索引值，并且把当前索引值上的Node值赋给p
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 如果该位置存在数据
Node<K,V> e; K k;
// 如果该位置上的key 和 要存放的key一样, 则直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 判断当前桶是否为TreeNode
// 如果是，则进行红黑树插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 如果是链表
for (int binCount = 0; ; ++binCount) {
//查找当前位置链表的表尾，表尾的next节点尾null,找到链表的尾部赋给下一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果脸变得长度大于等于8，则需要转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果节点key存在，则覆盖原来位置的key，同时将原来位置的元素，沿着链表向后移一位
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不为空，则代表目标节点存在，使用传入的value覆盖该节点的value,
// 并返回oldValue
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果插入节点数超过阈值，则调用resize 方法进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put 操作的主要流程如下:
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
下面举例说明put的插入过程
我们首先put “king” 元素，步骤如下:
map.put("king",33);
- 首先判断table[] 数组有没有初始化，如果没有，则进行初始化，默认长度为16
-
判断tab[index]中有没有元素，如果没有，则直接把元素放进去，由于 “king”的
(n-1)&hash的结果值为 6，所以判断tab[5] 有没有元素，此时没有，则直接放进去。 - 判断是否要扩容，此时不需要扩容
最终如下图:
我们再添加一个元素”peter”
map.put("peter",33);
由于peter元素的index也为5，所以 也会定位到table数组的索引5的位置。
5的索引位置上已经有了一个元素，所以就把peter元素添加到链表的尾部。
添加 peter元素，会走到put方法下的这段代码：
HashMap的扩容机制
经过rehash之后，元素的位置要么在原位置，要么是 原位置加上原数组长度的位置。
要搞明白上面这个问题，首先需要明白
为什么HashMap的数组长度永远都是2的幂？？
下面是HashMap 的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
从上面可以看出，无论你传入的initialCapacity是多少？都需要经过计算tableSizeFor的计算
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我们着中分析
tableSizeFor()
方法
由于 HashMap 的capacity 都是2的幂，因此这方法用于找到大于等于 initialCapcity 的最小的2的幂(如果initialCapacity 如果是2的幂，则直接返回)
我们举两个例子，来说明代码的含义
(1) 当 initialCapcity 为2的幂的时候，最终返回的是 initialCapcity
1. int n = cap - 1 n=15
0000 1111
2. n |= n >>> 1 右移1位
0000 1111
0000 0111 或 右移1位
---------------------
0000 1111
2. n |= n >>> 2 右移2位
0000 1111
0000 0011 或
---------
0000 1111
3.n |= n >>> 4 右移4位
0000 1111
0000 0000 或
---------
0000 1111
4.n |= n >>> 8 右移8位
0000 1111
0000 0000 或
---------
0000 1111
5.n |= n >>> 16 右移16位
0000 1111
0000 0000 或
---------
0000 1111
6.n = n+1
结果为 2^4=16
(2) 如果 initialCapcity 不是2的幂，则返回大于 initialCapcity 的最小2次幂
我们以11为例，返回结果应该是返回16
1. int n = cap - 1 n=10
0000 1010
2. n |= n >>> 1 右移1位
0000 1010
0000 0101 或 右移1位
---------------------
0000 1111
2. n |= n >>> 2 右移2位
0000 1111
0000 0011 或
---------
0000 1111
3.n |= n >>> 4 右移4位
0000 1111
0000 0000 或
---------
0000 1111
4.n |= n >>> 8 右移8位
0000 1111
0000 0000 或
---------
0000 1111
5.n |= n >>> 16 右移16位
0000 1111
0000 0000 或
---------
0000 1111
6.n = n+1
结果为 2^4=16
了解了为什么HashMap的数组长度永远都是2的幂，我们再来分析resize方法
resize() 方法中的比较重要的是 链表和红黑树的 rehash 操作，先来说 rehash的实现原理
HashMap在扩容的时候，一般是把长度扩为原来的2倍，所以元素的位置要么在原位置，要么在原位置再移动2次幂的位置。
我们以”king” 和 “peter” 为例， index = (n-1)&hash
(1) 当长度为 16的时候 (n-1) = 0000 1111
king
0000 0000 0011 0010 0011 1011 1010 0101 hash
0000 0000 0000 0000 0000 0000 0000 1111 (n-1)
----------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 (n-1) & hash
得到的index为 5
perter
0000 0110 0101 1001 1111 0100 0101 0101 hash
0000 0000 0000 0000 0000 0000 0000 1111 (n-1)
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 (n-1)&hash
得到的index 为5
(1) 当长度为 32 的时候 n-1= 31 = 0001 1111
king
0000 0000 0011 0010 0011 1011 1010 0101 hash
0000 0000 0000 0000 0000 0000 0001 1111 (n-1)
----------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 (n-1)&hash
index = 5
peter
0000 0110 0101 1001 1111 0100 0101 0101 hash
0000 0000 0000 0000 0000 0000 0001 1111 (n-1)
---------------------------------------
0000 0000 0000 0000 0000 0000 0001 0101 (n-1)&hash
index = 21 = 16 + 5
当 hashMap的容量从16扩容到32的时候
king 的 index 没有变
而 peter 的index 变了 21
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
下面我们看resize整个源码：
方法中的局部变量解释如下:
- oldTab : 数组类型，代表扩容之前HashMap中的数组，也就是所有的桶
- oldCap: 为int类型，代表扩容之前总桶数量。
- oldThr : int 类型，代表扩容之前下次扩容的阈值
- newCap : int 类型，代表这次扩容之后总桶数量
- newThr: int 类型，扩容之后下次扩容的阈值
- newTab : 数组类型，代表扩容之后 HashMap中的数组。
final Node<K,V>[] resize() {
// 当前所有元素所在的数组，
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果 数组元素在正常范围内，那么新的数组容量为老的数组容量的2倍
// 如果扩容之后新的容量小于最大容量，并且老的数组容量大于等于默认的初始化容量(16)
// 那么新数组的扩容阈值设置为老阈值的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 老数组为空
// 如果老数组的扩容阈值大于0，那么设置新数组的容量为该阈值
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)// 如果元素没有下一个节点，说明该元素不存在hash冲突
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 当前 index 的对应的节点为红黑树，这里不做讲解
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果该节点有下一个节点，说明该节点是一个链表，
// 之所以定义两个头两个尾对象,是由于链表中的元素的下标在扩容后,要么是原下标+oldCap,要么不变
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
//遍历桶中的链表
do {
next = e.next;
// 下标没有改变 ① 参考下面解释
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 第一个节点
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果与运算结果不为0，说明hash值大于老数组长度
// 此时该元素应该放置到新数组的高位位置上
// 例如，长度为16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上
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;
}
我们来解释 ① 的代码 ，为什么e.hash & oldCap==0 就能说明扩容后的下标也是不变的？
数组的长度一定是2的n次方，如果hash值和该长度做与运算，那么该hash值可参与计算的有效二进制就是和长度对等的后n位
我们以长度为16为例说明
如果结果为0，说明hash值中参与计算的对等的二进制位的最高位一定为0。
比如：长度为16 ，二进制位 1 0000 ，那么hash中对等的位置 为
…0 * * * * 和 1 0000 进行与运算结果才是00000 。又因为定位下标时的取模运算是以hash值和长度减1进行与运算，所以下标 为 (
…0 * * * * & 1111) 结果也等于 00000。同样 长度n 为 32 64 等 ，下标也为0。
所以该hash值再和新数组的长度取摸的话mod值也不会放生变化，也就是说该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。
总结
- 具有很快的访问速度，但遍历顺序却是不确定的。（无序性）
- HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
- HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。
- 如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap
- HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构
- HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是0.75f；
- HashMap扩容时每次容量变为原来的两倍；
- 当桶的数量小于64时不会进行树化，只会扩容；
- 当桶的数量大于64且单个桶中元素的数量大于8时，进行树化；
- 当单个桶中元素数量小于6时，进行反树化；