hashMap简介
- HashMap是基于哈希表实现的，每一个元素是一个key-value对，无序，不可重复。
- HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。
- HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。
- hashmap集合的默认初始化容量为16(2<<3)，如果初始化增加的大小则是最接近该数的2的幂次方，默认加载因子为0.75，也就是说这个默认加载因子是当hashMap集合底层数组的容量达到75%时，数组就开始扩容。hashmap集合初始化容量是2的陪数，为了达到散列均匀，提高hashmap集合的存取效率。
- 无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方
- HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。
- JDK1.8之后当链表的长度达到 “8” 时，内部会调用 “treeifyBin” 方法，判断数组长度是否达到 “64” 达到就会自动变成红黑树的结构，达不到会调用扩容机制，当红黑树节点的个数达到 “6” 之后，又会变成链表结构。
源码解析
初始化Map
HashMap hashMap=new HashMap();
public HashMap() {
//DEFAULT_LOAD_FACTOR = 0.75f;
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap hashMap=new HashMap(5);
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//初始化大小不能为负数
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//不能超过最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//指定的扩容因子不能小于等于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}//不管传多大的容量，容量都是最靠近设置值的2的幂次方tableSizeFor()
static final int tableSizeFor(int cap) {//返回给定目标容量的两倍幂
int n = cap - 1;//减1.防止传入的刚好是2的幂次方的时候，得到的是下一个幂次方，比如传入4，不减1，会得到8
n |= n >>> 1;//右移一位，然后|运算，能保证高2位是1，是4
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;//类推到最大的2的32-1，也就是32个1！！因为 java中int4字节，也就是32位，达到int的最大值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//再加1，
}
举例展示
n=cap-1 ; // 4 二进制位100
n |= n >>> 1; // n>>>1 为 0000 0010 与n|运算 得到0000 0110
n |= n >>> 2; // n>>>2 为 0000 0001 与n|运算 得到0000 0111 转换为十进制为7
n |= n >>> 8; // 还是7
n |= n >>> 16; // 还是7
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : n + 1; //再加1，返回8，得到的是传入的最近的2 的幂put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}hash()扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//让高低位都参与下标hashcode的计算
}putVal（）方法
//hash 通过扰动函数得到的hash值 onlyIfAbsent false evict true
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为空，并且tab.length为0
if ((tab = table) == null || (n = tab.length) == 0)
//进入resize方法,得到一个初始化大小为8的数组
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//根据 hashcode取模7 得到下标，并且查询下标值是否为空，第一次为null
tab[i] = newNode(hash, key, value, null);//在下标 位置new node 将key value赋值
else {//将数组上的链表移到新数组
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}初始化resize方法
final Node<K,V>[] resize() {//返回一个node数组
Node<K,V>[] oldTab = table;//第一次进来为null
int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap=0
int oldThr = threshold;//传进来最靠近2的幂等的数据 现在传的是5 那么就是8
int newCap, newThr = 0;
if (oldCap > 0) {//第一次进来不满足
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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// 满足 oldThr=8 initial capacity was placed in threshold 初始容量为阈值
newCap = oldThr;//newCap=8
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;//ft=8*0.75 得到6
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);//newThr 为6
}
threshold = newThr;//赋值扩容阈值为6
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//初始化8大小的数组
table = newTab;//将初始化的table赋值给table
if (oldTab != null) {//第一次不满足条件，不需要进行rehash
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;//返回初始化为8的tab
}第二个元素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为8容量的table 不为空，不进入该逻辑
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)根据hash得 到下标，如果为空，直接new node
tab[i] = newNode(hash, key, value, null);//在下标 位置new node 将key value赋值
else {//下标如果有位置，说明key是一样的，或者发生了hash冲突
Node<K,V> e; K k;
if (p.hash == hash &&//p为下标位置已有的值 如果该值的key跟传入的一致 把e替换成p
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//如果是黑红树 往红黑树添加节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//不是node节点也不是红黑树
for (int binCount = 0; ; ++binCount) {
//e为p节点的下一个节点，如果为空，说明到了p节点位 置的最后一个位置（循环里把p设置为e）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);//加到p节点的next
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果binCount大于等于7 代表链表的长度达到 8的时候，转为红黑树
treeifyBin(tab, hash);//里面会先判断容量是否小于64，不然先进行resize扩容
break;//跳出循环
}
//hash冲突 并且key相同的时候，直接跳出 覆盖原来 的key就行
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key//如果e不为null
V oldValue = e.value;//得到原来位置的值
if (!onlyIfAbsent || oldValue == null)//如果onlyIfAbsent为false 或者没有value 替换原来 的value
e.value = value;
afterNodeAccess(e);//模板方法
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果大于我的阈值，进行resize
resize();
afterNodeInsertion(evict);模板
return null;
}扩容resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//已有的的数组table
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 之前table长度为8
int oldThr = threshold;//之前的阈值为6
int newCap, newThr = 0;
if (oldCap > 0) {//8>0满足
if (oldCap >= MAXIMUM_CAPACITY) {//不为最大值，没有 扩容到最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}//newCap为之前容量的2倍 如果小于最大值并且之前的容量大于默 认的大小，newThr为老阈值的2倍（我们的例子不满足）
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) {//满足该场景，当前新的阈值还是0
float ft = (float)newCap * loadFactor;//根据新的table容量计算下次扩容的阈值 为16 *0.75=12
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);//12赋值 给newThr
}
threshold = newThr;//阈值设置为12
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//讲table数组扩容到16
if (oldTab != null) {//满足
for (int j = 0; j < oldCap; ++j) {//循环老的数组数据
Node<K,V> e;
if ((e = oldTab[j]) != null) {//将下标的数据赋 值给e
oldTab[j] = null;
if (e.next == null)//e的next为null。代表当前位置不是链表，没有发生hash冲突
newTab[e.hash & (newCap - 1)] = e;// 把e放到新的位置
else if (e instanceof TreeNode)//如果是红黑 树，将树移到新的位置 如果小于6 会退化成单向链表
((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;
}
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}getNode方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//table不为空，并且通过hash拿到的value不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//第一个节点的数据就是我要的key，直接返回第一个节点
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;
}put原理
第一步首先将k,v封装到Node对象当中（节点）。
第二步它的底层会调用K的hashCode()方法得出hash值。
第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
因此，放在hashMap集合key部分的元素如果是自定义对象的话都需要重写hashCode和equal方法。
get原理
第一步：先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
在hashMap添加元素的时候会计算添加元素的hash值，通过hash值确定放在哪个hash桶中，当不同的元素计算出相同的hash桶的时候，这样就发生了哈希碰撞
哈希碰撞
开放地址发：
当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
链地址法（拉链法）hashMap使用的就这这种方法：
将相同hash值的对象组织成一个链表放在hash值对应的槽位；
再哈希法：
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
建立一个公共溢出区:
假设哈希函数的值域为[0,m-1],则设向量HashTable[0…m-1]为基本表，另外设立存储空间向量OverTable[0…v]用以存储发生冲突的记录。
HashMap中的“死锁”
HashMap是非线程安全，死锁一般都是产生于并发情况下。我们假设有二个进程T1、T2，HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同，于是形成一个链接，假设为A->C->B，而D、E Hash值不同，于是容量不足，需要新建一个更大尺寸的hash表，然后把数据从老的Hash表中 迁移到新的Hash表中(refresh)。这时T2进程闯进来了，T1暂时挂起，T2进程也准备放入新的key，这时也 发现容量不足，也refresh一把。refresh之后原来的链表结构假设为C->A，之后T1进程继续执行，链接结构 为A->C,这时就形成A.next=B,B.next=A的环形链表。一旦取值进入这个环形链表就会陷入死循环。
解决办法：
使用线程安全的ConcurrentHashMap
hashMap的容量怎么扩充
table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造
时传入，最大限制是1<<30；并且必须是2的幂次方
loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态
扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75
时，threshold 就是12，当 table 的实际大小超过 12时，table就需要
动态扩容；
扩容时，调用 resize() 方法，将 table 长度变为原来的两倍，并且根据
新的容量，计算新的数据索引值
hashMap 在JDK1.8跟1.7的区别，chm在JDK1.8跟1.7的区别
- 1.7采用数组+单链表，1.8在单链表超过8并且数组长度超过64时，单
- 1.7扩容时需要重新计算哈希值和索引位置，1.8不重新计算哈希值，而 是采用和扩容后容量进行&操作来计算新的索引位置。
- 1.7插入元素到单链表中采用头插入法，1.8采用的是尾插入法。（1.7重 新计算hash值并发有闭环链表风险）
chm 上述hashMap的变更也是chm的变更，还有锁
1.7采用分段锁的机制，锁住的是一个segment数组，采用重入锁
ReentrantLock（重入锁）
1.8.采用Node + CAS + Synchronized来保证并发安全,取消类 Segment， 直接锁entry
为什么取消重入锁，采用synchronized?
粒度降低了；
JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized
优化空间更大，更加自然。
在大量的数据操作下，对于 JVM 的内存压力，基于 API 的
ReentrantLock 会开销更多的内存。
标签：Node,Map,java,value,next,源码,key,hash,null From： https://blog.csdn.net/loushaoqi/article/details/144591322