HashMap源码刨析（面试必看）
2020-01-19 16:04:11来源：博客园 阅读 ()
HashMap源码刨析（面试必看）
目录
- 1、Hash的计算规则？
- 2、HashMap是怎么形成环形链表的(即为什么不是线程安全)？（1.7中的问题）
- 3、JDK1.7和1.8的HashMap不同点？
- 4、HashMap和HashTable的区别？
- 5、ConCurrentHashMap？
- 为什么加载因子是0.75
- HashMap构造函数：
- HashMap数组默认的值
- tableSizeFor(int cap）
- 为什么HashMap的容量一定是2的幂
- put方法
- resize()方法
- hash()方法
- 为什么使用(n - 1) & hash而不用 value % n
- put方法中，如果产生冲突除了覆盖或者不覆盖还使用了afterNodeAccess
- LinkedHashMap和HashMap的区别
- put方法中的桶的树型化扩充treeifyBin()
- treeify()方法是TreeNode结点内部的一个方法，实际作用才是将一条链表树化
- remove方法
- get方法
@(HashMap源码刨析)
JDK1.7：数组+链表
JDK1.8：数组+链表+红黑树
前五个问题环境用的是是JDK1.7，后面全部是1.8
1、Hash的计算规则？
简单的说是个“扰动函数”，目的是为了使散列分布的更加均匀。
具体算法是用key的Hashcode值右移16位，将hashcode高位和低位的值进行混合做异或运算，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。掺杂的元素多了，那么生成的hash值的随机性会增大，得到Hash。最后与table长度进行与运算(indexFor()方法)，和取余是一个结果，不过与运算更加节省计算机资源。
这里用&运算的原理：n一定是2的次方数(由扩容机制决定)，n-1的二进制表示则全为1，而&运算的方式是双方为1结果才为1，那么不管hash有多大，结果都取决于n-1的这几位，大于n-1的那部分全补为0，则不可能越界。
2、HashMap是怎么形成环形链表的(即为什么不是线程安全)？（1.7中的问题）
在多线程情况下进行扩容容易形成环形链表，关键点在于resieze()方法中的transfer()方法。
在单线程下代码执行过程：
在多线程下代码执行过程：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FNLaBmyb-1579436677465)(file:///C:\Users\李正阳\AppData\Local\Temp\ksohtml17192\wps3.png)]
当一个线程执行完Rehash完之后另一个再在旧map中Rehash,由于链表已经逆序，所以next会指回去，再进行Rehash就会形成环形链表
3、JDK1.7和1.8的HashMap不同点？
(1) JDK1.7使用的是头插法，1.8之后是尾插法。其原因在于1.7是用单链表进行的纵向延伸，当采用头插法能提高插入的效率(因为加到尾部还需要遍历链表)，但是容易出现逆序和环形链表死循环的问题。在1.8之后是因为加入了红黑树使用尾插法(尾插法要遍历链表，顺便判断链表长度是否大于8)，能够避免逆序和链表死循环问题。红黑树能提高查找效率，比链表的查找效率高。
(2) 扩容后数据储存的计算方式不一样
JDK1.7：直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）。
JDK1.8：直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。(table变为2倍，则左边增加一位1，和Hash值进行与操作即可)
(3) JDK1.7使用的是数组+单链表的数据结构。JDK1.8及以后使用的是数组+链表+红黑树的数据结构(当链表长度到达8的时候，也就是默认阈值，会自动扩容把链表转化成红黑树的数据结构)
4、HashMap和HashTable的区别？
(1) HashMap是非线程安全的，并且可以储存NULL。HashTbale是线程安全(即synchronized)，但不能存储NULL。
(2) HashMap利用HashCode重新计算Hash值，HashTbale直接使用key的HashCode()，再取模算下标。
(3) 内部实现使用的数组初始化和扩容方式不同。HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
5、ConCurrentHashMap？
核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
为什么加载因子是0.75
在HashMap中，默认创建的数组长度是16，也就是哈希桶个数为16，当添加key-value的时候，会先计算出他们的哈希值(h = hash),然后用return h & (length-1)就可以算出一个数组下标，这个数组下标就是键值对应该存放的位置。
但是，当数据较多的时候，不同键值对算出来的hash值相同，而导致最终存放的位置相同，这就是hash冲突，当出现hash冲突的时候，该位置的数据会转变成链表的形式存储，但是我们知道，数组的存储空间是连续的，所以可以直接使用下标索引来查取，修改，删除数据等操作，而且效率很高。而链表的存储空间不是连续的，所以不能使用下标 索引，对每一个数据的操作都要进行从头到尾的遍历，这样会使效率变得很低，特别是当链表长度较大的时候。为了防止链表长度较大，需要对数组进行动态扩容。
数组扩容需要申请新的内存空间，然后把之前的数据进行迁移，扩容频繁，需要耗费较多时间，效率降低，如果在使用完一半的时候扩容，空间利用率就很低，如果等快满了再进行扩容，hash冲突的概率增大！！那么什么时候开始扩容呢？？？
为了平衡空间利用率和hash冲突（效率），设置了一个加载因子(loadFactor)，并且设置一个扩容临界值（threshold = DEFAULT_INITIAL_CAPACITY * loadFactor）,就是说当使用了16*0.75=12个数组以后，就会进行扩容，且变为原来的两倍
在理想情况下，使用随机哈希吗，节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素的个数和概率的对照表。
从上表可以看出当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。
hash容器指定初始容量尽量为2的幂次方。
HashMap负载因子为0.75是空间和时间成本的一种折中。
HashMap构造函数：
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*
* 构造函数，设置基本的加载因子为0.75，意思是当一个 * 表的长度超过
* 临界值就会再散列然后放回容器，这是十分耗时间的。
* 这个临界值由负载因子和容量大小来决定，并且我们可以 * 手动初始化这个值
*
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
用户输入的容量初始值和负载因子后赋值检查
public HashMap(int initialCapacity, float loadFactor) {
//初始化数组默认值小于0直接抛出
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//大于最大值就直接默认为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子小于0, Float.isNaN或者输入的不是一个数字抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//赋值操作
this.loadFactor = loadFactor;
//确保你赋值虽然不是2的k次方，也会输出2的k次方
this.threshold = tableSizeFor(initialCapacity);
}HashMap数组默认的值
数组的初始默认值：
/** * * 数组的默认初始值为16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;为什么最大容量是这么大？
int 是32为整数，四个字节，负数为1
1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648首位为符号位，正数是0，负数为1
31位存储的是int型的补码，所以最大只能30位
如果我要存的值大于2^30如何处理
有一个resize()方法，这个方法的作用就是当使用的容量到达threshold容量的时候扩容
//但是如果最大容量大于默认的最大容量，会使threshold扩充为 Integer.MAX_VALUE if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; }threshold
int threshold;threshold = 初始容量 * 加载因子相当于扩容的限制值，相当于实际使用量
可以扩充到Integer.MAX_VALUE,还是为了能继续存储，因为到2 << 30 就会溢出。
表明不进行扩容了
所以说HashMap的总容量自然是MAXIMUM_CAPACITY
同时这个值没有在创建的时候初始化，而是在put方法中初始化了。
table
transient Node<K,V>[] table;是一个数组单链表结构
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;
tableSizeFor(int cap）
初始化容量，找到离输入最近2的幂，因为HashMap要求容量必须是2的幂。
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;
}int n = cap - 1是为了防止cap已经是2的幂了，一下举一个例子：
cap = 11
n |= >>> 1:
0000 1011 | 0000 0101 = 0000 1111
n |= >>> 2;
0000 1111 | 0000 0011 = 0000 1111
继续向下推，也是一样结果
如果最后值为32个1自然取到最大值MAXIMUM_CAPACITY，如果不是就给n+1，那么此时n = 16
为什么HashMap的容量一定是2的幂
- 1.奇数不行的解释很能被接受，在计算hash的时候，确定落在数组的位置的时候，计算方法是(n - 1) & hash ，奇数n-1为偶数，偶数2进制的结尾都是0，经过&运算末尾都是0，会 增加hash冲突。
- 2.为啥要是2的幂，不能是2的倍数么，比如6，10？ -
- 2.1 hashmap 结构是数组，每个数组里面的结构是node（链表或红黑树），正常情况下，如果你想放数据到不同的位置，肯定会想到取余数确定放在那个数据里， 计算公式： hash % n，这个是十进制计算。在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。
- 2.2 只有是2的幂数的数字经过n-1之后，二进制肯定是 ...11111111 这样的格式，这种格式计算的位置的时候，完全是由产生的hash值类决定，而不受n-1 影响。你可能会想，受影响不是更好么，又计算了一下 ，hash冲突可能更低了，这里要考虑到扩容了，2的幂次方*2，在二进制中比如4和8，代表2的2次方和3次方，他们的2进制结构相似,比如4和8 00000100 0000 1000 只是高位向前移了一位，这样扩容的时候，只需要判断高位hash,移动到之前位置的倍数就可以了，免去了重新计算位置的运算。
- 取决于操作系统，一般操作系统申请内存之列都是2的幂，因为这样可以有效避免内部碎片
- 会增加hash冲突的概率，详情看后面为什么不使用(n - 1) & hash
put方法
put函数不是具体实现，主要是为了方便用户，就像工厂方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}调用的putVal函数
putVal(hash(key), key, value, false, true);
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 一共有五个参数，第一个是插入元素的key的hash值，第二个是key本身，第三个是value，onlyIfAbsent true 代表映射存在不替换原值，evict 如果位false就代表HahMap代表正处于创建阶段
putVal方法中，冲突之后判断是不是处于数组的第一位
//确定是p这个位置hash值相同，并且key的值也相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//临时结点e = p
e = p;定理：
equal objects must have equal hash codes.
首先：java.lang.Object.hashCode() 是三条约定是
1、多次运行 hashCode()，其值必须总是一致的（前提：1、 equals() 中用到的信息没发生变化 2、在同一次 execution 中）
2、obj1.equals(obj2) == true，则必须 obj1.hashCode() == obj1.hashCode() 总是 true
3、obj1.equals(obj2) == false，则 obj1.hashCode() == obj2.hashCode() 最好 false 这是因为 HashMap.containsKey()，HashMap.put() 时
a：由于 hash 不同，则直接就不尝试了（好。这样效率高啊）
b：“两把刷子程序员” 把 hash 弄成相同的（equals()不同，hashCode()相同），还得向下尝试 equals() （不好）
情况一：
出现hash冲突，同时和数组指定位置第一个元素是一样的
代码节选：
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //临时结点e = p e = p; .............................................. //如果是第一种情况就，e的值位数组中第一个 if (e != null) { // existing mapping for key //保存结点e中的值 V oldValue = e.value; //如果oldValue（现在在数组中的结点值）或者onlyIfAbsent的值为false if (!onlyIfAbsent || oldValue == null) //覆盖现有结点的值 e.value = value; //给LinkedHashMap预留的方法位 afterNodeAccess(e); //返回旧的值 return oldValue; }情况二：发现插入位置已经是红黑树了，返回红黑树的结点
//第二种情况如果是红黑树就按照红黑树的插入结点的方式 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ............................................... //如果是第一种情况就，e的值位数组中第一个，第三种情况也要执行接下来的代码,第二种情况也会执行 if (e != null) { // existing mapping for key //保存结点e中的值 V oldValue = e.value; //如果oldValue（现在在数组中的结点值）或者onlyIfAbsent的值为false if (!onlyIfAbsent || oldValue == null) //覆盖现有结点的值 e.value = value; //给LinkedHashMap预留的方法位 afterNodeAccess(e); //返回旧的值 return oldValue; }情况3：虽然有冲突但是 不是第一个，遍历数组之后，找到就替换，没找到就插入，插入之后大于8执行桶的树型化
else {
//冲突的第三种情况，不是第一个久开始遍历
for (int binCount = 0; ; ++binCount) {
//如果已经到达了链表的尾端
if ((e = p.next) == null) {
//链表的末端插入当前需要插入的值
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于7，因为是从0开始的，所以是八个长度
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;
}
}
....................................................
//如果是第一种情况就，e的值位数组中第一个，第三种情况也要执行接下来的代码，第二种情况也会执行
if (e != null) { // existing mapping for key
//保存结点e中的值
V oldValue = e.value;
//如果oldValue（现在在数组中的结点值）或者onlyIfAbsent的值为false
if (!onlyIfAbsent || oldValue == null)
//覆盖现有结点的值
e.value = value;
//给LinkedHashMap预留的方法位
afterNodeAccess(e);
//返回旧的值
return oldValue;
}
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方法的完整代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果数组为空，由于创建的时候没有初始化，看resize()做了什么操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//检查数组的这个位置是不是已经有了元素，p为这个位置的元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//已经有了元素执行这部分内容
Node<K,V> e; K k;
//冲突的第一种情况确定是p这个位置第一个hash值相同，并且key的equals值也相同，如果hash值不相等就不用继续运行了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//临时结点e = p
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);
//如果链表长度大于等于7，因为是从0开始的，所以是八个长度
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;
}
}
//如果是第一种情况就，e的值位数组中第一个，第三种情况也要执行接下来的代码
if (e != null) { // existing mapping for key
//保存结点e中的值
V oldValue = e.value;
//如果oldValue（现在在数组中的结点值）或者onlyIfAbsent的值为false
if (!onlyIfAbsent || oldValue == null)
//覆盖现有结点的值
e.value = value;
//给LinkedHashMap预留的方法位
afterNodeAccess(e);
//返回旧的值
return oldValue;
}
}
//修改计数增加
++modCount;
//添加结点之后检查时候已经到达了扩容界限
if (++size > threshold)
//扩容
resize();
//为linkedHashMap服务
afterNodeInsertion(evict);
return null;
}resize()方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//如果数组为空，就将0赋值给oldCap，不为空则返回，表的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//之前的扩容界限,初始化的时候oldThr不会是0，因为有tableSizeFor()方法，确保oldThr至少是1
int oldThr = threshold;
//新的容量和新的扩容界限
int newCap, newThr = 0;
//如果是已经初始化的数组，并且数组里面还有元素,就会直接进入这个分支
if (oldCap > 0) {
//但是如果最大容量大于默认的最大容量，会使threshold扩充为nteger.MAX_VALUE，表明不在进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
//直接返回旧的表
return oldTab;
}
//新的容量为旧容量的2倍，这是向左移一位，由于本来就是2的幂次，向左移动自然是2倍，并且新容量要小于最大值，旧容量要大于初始值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的限制也要变成原来的两倍
newThr = oldThr << 1; // double threshold
}
//这个分支代表的是创建map使用的是带参构造函数，初始容量无论是输入多少，都会返回2 ^n，同时这个值存在threshold 中
else if (oldThr > 0) // initial capacity was placed in threshold
//给新的容量赋值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//这是第一次初始化新的容量，并且调用的是无参构造函数，新的newCap为16，新的扩容界限为12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//这是第一次初始化扩容限制，新的扩容限制为16 * 0.75 = 12
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
//如果容量已经大于MAXIMUM_CAPACITY，就给赋值为Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新的扩容界限给threshold
threshold = newThr;
//初始化数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将newtable赋值给table
table = newTab;
//如果这个表不为空的时候
if (oldTab != null) {
//遍历一遍表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果j这个位置的元素不为null
if ((e = oldTab[j]) != null) {
//先赋值为null
oldTab[j] = null;
//如果e.next为null就代表的是数组之中有值，且只有一个，直接赋值就行
if (e.next == null)
//重新计算hash之后，向新表中直接插入e
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;
//为0走这个分支
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//第一次进入这个循环一般会走这个分支如果不为0走这个分支
else {
if (hiTail == null)
//然后hiHead得到值，相当于初始化链表，头节点和尾结点一样
hiHead = e;
else
hiTail.next = e;
//hiTail也会得到值
hiTail = e;
}
} while ((e = next) != null);
//计算出hash和原容量为0才走这个分支
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//当不为0时候走这一点，将新链表链接到新的坐标底下
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//放回新的数组
return newTab;
}当链表的结点数大于8，就将这个结点转化为红黑树
扩容进行到最后，发现数组不为空，并且循环遍历的时候发现这个位置不是单单数组中一个值，还有一个单链表这个时候为什么要e.hash & oldCap？不应该是e.hash & newCap
do {
next = e.next;
if ((e.hash & oldCap) == 0) {这个是e.hash & oldCap != 0的情况举个例子：
扩容之前的容量 ：0001 0000
n - 1 0000 11111
新容量： 0010 0000
n - 1： 00001 1111
k1-hash： 0001 0100
与原容量& 0001 0000
newTab[j + oldCap] = hiHead;原下标： 0000 0100
原下标加原容量 0001 0100
K1-hash与新的n - 1& 0001 0100
这个结果和原下表加原容量的结果是一样的
e.hash & oldCap 等于0的情况
K2-hash： 0000 0100
与原容量n-1& 0000 0100
计算出来：新下标和原下标是一样的，下面是计算与新容量n-1计算
K2-HASH : 0000 0100
n-1 0001 1111
& 0000 0100
与原容量n-1和新容量n-1&其实结果是一样的
这些只是为了证明，扩容中，链表中的很多元素的新数组下标有两种可能，一种是还在元素数组下标，还有一种就是元素组加旧的容量的位置
为什么可以这样，因为在两种情况中，计算他们所处位置其实直接和新容量n-1&是一样的，上面的两个例子分别为两种情况，也证明了这一点。
hash()方法
static final int hash(Object key) {
int h;
//如果输入的键是null，hash就为0，否则计算hashcode
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}计算出hashcode的值然后和 h >>> 16位的值异或这个是为什么？
(h = key.hashCode()) ^ (h >>> 16)，为什么需要异或？
例子：
原值1： 10010001 10010101 10110000 11110001
右移动16位： 00000000 00000000 10010001 10010101
异或： 10010001 10010101 00100001 01100100
进入put函数中比较代码段
数组大小： 00000000 00000001 00000000 00000000
n - 1： 00000000 00000000 11111111 11111111
原值1与后： 00000000 00000000 10110000 11110001
异或后再与： 00000000 00000000 00100001 01100100
目前看不出什么，再来看一个原值2与原值1只差第一位
原值2： 00010001 10010101 10110000 11110001
右移动16位： 00000000 00000000 00010001 10010101
异或： 00010001 10010101 10100001 01100100
原值2与后： 00000000 00000000 10110000 11110001
异或后再与： 00000000 00000000 10100001 01100100
可见如果不先异或直接与两个数相差不大等情况下的，与之后的情况是一样的，如果先进行异或就可以提高hash值得散列度，可以避免冲突。
为什么使用(n - 1) & hash而不用 value % n
其实(n - 1) & hash 和 value % n 是相等的，但是需要n为2的幂，同时计算机更加习惯用 & 运算这种而不是这种取余运算，可以加快计算机计算的速度。
举个例子：（只有当n = 2的幂次的时候，才和value % n 相同
n = 16
0000 1111 n - 1
0000 0001 hash
-> 0000 0001
1 % 16 = 1
0000 1111
0000 0101
-> 0000 0101 = 8
n = 15
0000 1110 n -1
0000 0001 hash
-> 0000 0000
同时也会导致hash冲突增加
put方法中，如果产生冲突除了覆盖或者不覆盖还使用了afterNodeAccess
afterNodeAccess实现方法是LinkedHashMap类中的方法
LinkedHashMap和HashMap的区别看下一个问题
HashMap.afterNodeAccess()中说道，“是为LinkedHashMap留的后路”。如今行至于此，当观赏一方。首先需要了解的是LinkedHashMap相比HashMap多了有序性，由双向链表(before,after)实现。源码出现了一些全局变量：
accessOrder：true:按访问顺序排序（LRU），false:按插入顺序排序；
head、tail：存放链表首尾；
可见仅有accessOrder为true时，且访问节点不等于尾节点时，该方法才有意义。通过before、after重定向，将新访问节点链接为链表尾节点。
这些方法都是为了实现LinkedHashMap类的记录的插入顺序
LinkedHashMap和HashMap的区别
一般情况下，我们用的最多的是HashMap,在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.
HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为NULL，允许多条记录的值为NULL。
HashMap不支持线程同步，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致性。如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力。
Hashtable与HashMap类似，不同的是：它不允许记录的键或者值为空；它支持线程的同步，即任一时刻只有一个线程能写Hashtable，因此也导致了Hashtable在写入时会比较慢。
LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。
在遍历的时候会比HashMap慢TreeMap能够把它保存的记录根据键排序，默认是按升序排序，也可以指定排序的比较器。当用Iterator遍历TreeMap时，得到的记录是排过序的。
put方法中的桶的树型化扩充treeifyBin()
***TREEIFY_THRESHOLD***** = 8;
当链表长度大于此值时，将链表转化为红黑树。
***UNTREEIFY_THRESHOLD***** = 6;
当红黑树小于此值时又会转回链表
扩充的实际操作不是放在这里
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//进行树型化的阈值为64，如果小于64就没必要树化，会选择先扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//进行扩容
resize();
//找到需要扩容的位置
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//将链表结点转为树状结点
TreeNode<K,V> p = replacementTreeNode(e, null);
//初始化hd，hd为链表的第一个
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
//tl在刚进入 = hd = p ，然后之后的作用为遍历链表然后将他们链接起来
tl = p;
} while ((e = e.next) != null);
//hd为链表的头节点，先将他赋值给表的固定位置，然后对hd这个链表进行树化
if ((tab[index] = hd) != null)
//将这条链表树化
hd.treeify(tab);
}
}treeify()方法是TreeNode结点内部的一个方法，实际作用才是将一条链表树化
还未研究红黑树，暂且不做解析
remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}调用了removeNode这个方法，然后介绍一下这个方法的五个参数。
- @param hash hash for key
- @param key the key
- @param value the value to match if matchValue, else ignored
- @param matchValue if true only remove if value is equal
- @param movable if false do not move other nodes while removing
第一个是hash，自然是计算key的hash
第二个就是key值
第三个是value值
第四个是 是否匹配value，如果值为true，只删除值相同的，默认为false
第五个为如果为false，在删除的时候不移动其他结点，默认为true
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//如果这个数组已经初始化了，并且这个位置不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//检查数组这个位置第一个是否为所要删除的结点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//这个数组不止有一个元素
else if ((e = p.next) != null) {
//链表已经红黑树化，调用红黑树获取结点的方法
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//数组情况
else {
//循环遍历
do {
//找到需要删除的值就赋值，然后结束循环
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
//p为需要删除元素的前一个元素
p = e;
} while ((e = e.next) != null);
}
}
//在hash表中找到了node，并且node不为空，并且值相同
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//结点是树形结点调用红黑树删除方法
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//node和p结点一样的情况，只有在删除链表第一个结点的情况下
else if (node == p)
tab[index] = node.next;
//直接将p.next指向需要删除的结点的下一个
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}get方法
public V get(Object key) {
Node<K,V> e;
//找到了就直接返回value，没找到就直接返回null
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;
//前一个条件是表已经初始化了
if ((tab = table) != null && (n = tab.length) > 0 &&
//并且这个位置的数组链表不为null
(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);
//检查链表中有没有相等的key，找到就直接返回e
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//找不到就返回null
return null;
}这部分没有什么好说的，红黑树部分后续再讲解。
后记：
前五个问题，感谢我的同学ZR，剩下中有些解释是我网上找的资料，因为写的好就直接摘录了。其余均为自己的分析和理解，有错希望指出。
原文链接:https://www.cnblogs.com/lzy321/p/12215520.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- 你说研究过Spring里面的源码，循环依赖你会么？ 2020-06-09
- 通俗理解spring源码（六）—— 默认标签（import、alias、be 2020-06-07
- HashMap：源代码（构造方法、put、resize、get、remove、rep 2020-06-04
- HashMap1.7和1.8，红黑树原理！ 2020-06-03
- 学习源码的第八个月，我成了Spring的开源贡献者 2020-06-02
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
