- JDK1.7的HashMap
- 1111、resize扩容方法
- 2222、createEntry方法
- GET方法源码
- JDK1.8的HashMap
- 红黑树前置知识
- 红黑树
- Jdk1.8的HashMap概述
- 面试常问
- Put方法大致过程
- GET方法查找元素的大致过程？
- 快速失败机制是什么？
- 如何保证key的唯一性呢？
- 能否使用任何类作为 Map 的 key？
- 为什么HashMap中String、Integer这样的包装类适合作为K？
- 如果使用Object作为HashMap的Key，应该怎么办呢？
- HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table数组的下标？
- hashCode()和equals()方法的重要性体现在什么地方？
- 为什么引入红黑树？
- 什么时候会进行树化？什么树化进行树退化为链表？
- 为什么链表转红黑树的树化阈值是8？为什么转回链表节点是用的6而不是复用8？
- HashMap 有哪些重要属性？分别用于做什么的？
- thres hold 除了用于存放扩容阈值还有其他作用吗？
- HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
- 为什么HashMap 的容量必须是2的N次方？怎么来的？
- 为什么负载因子是0.75而不是其他的？
- 为什么要将 hashCode 的高16位参与运算？
- HashMap扩容的大致原理
- 红黑树和链表都是通过 e.hash & oldCap == 0 来定位在新表的索引位置，这是为什么？
- 介绍一下死循环问题？
- 那总结下 JDK 1.8 主要进行了哪些优化？
- 源码
任何没有指明Jdk版本的HashMap源码资料都是在耍流氓，毕竟每一套版本的源码相较之前版本都有所改进；我在下面记录了有关Jdk1.7跟Jdk1.8这两个版本HashMap的相关知识点，因为这两个版本的HashMap源码最为经典，面试中也经常会问；
JDK1.7的HashMap
概述
在介绍HashMap的数据结构之前，我们先来看看我们之前都学习过的结构，回忆回忆它的各自的特点是什么。
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)；
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)；
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（），仅需一次定位即可完成，时间复杂度为O(1)，值得插一嘴的是，我们要介绍的主角HashMap采用的就是一个由数组+链表组成的哈希表，接下来我们就来看看哈希表是如何实现达到常数阶O(1)如此高性能的。
有计算机基础的伙伴应该都知道，抽象逻辑数据结构的物理存储只有两种结构：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，但本质上在计算机中实际存储的也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以找到元素，哈希表采用了数组的这种特性，而且哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们可以把跟当前元素相关的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成查找操作。这个函数就叫做哈希函数。 这个函数的设计好坏会直接影响到哈希表的优劣。
哈希冲突
虽然哈希表能够一次定位找到查找的元素是否存在，但是也有其他的问题，比如说如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算时的简单性以及散列的地址分布均匀，但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。
那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
HashMap的基本结构
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
JDK1.7中的HashMap调用put方法进行添加元素时候使用的是头插法，table数组存放的是节点的引用，真正的节点对象存放在堆中；首次添加元素的时候，会将元素的引用存放在table数组中，该引用指向堆中的对象；如下图所示：
再次往里面添加元素的时候，只需要将节点指向堆中的对象，然后将table中数组的引用换成新添加对象的引用，即可完成头插法添加元素。
PUT方法大致流程
PUT方法流程
1、通过 HashMap 自己提供的hash 算法算出当前 key 的hash 值
2、通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组下标的几号位置
找到table下标的过程如下，
3、判断size 是否已经达到了当前扩容阈值，如果没有，则继续添加；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。
请注意：size 是当前容器中已有 Entry 的数量，不是数组长度。
4、然后将将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有元素，
4.1、该位置如果没有Entry对象，则将封装好的Entry放在这个位置上；
4.2、如果此位置上已经存在链表，那么遍历链表，
4.2.1、如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value。
4.2.2、如果遍历完链表，没有找到key 与当前 key equals为 true的，就把刚才封装的新的 Entry中next 指向当前链表的始节点，也就是说当前节点现在在链表的第一个位置，简单来说是头插法，即先来的往后退。
GET方法大致流程
1、找到数组下标；当调用get方法时首先判断输入的key是否为空,如果为空,从hashmap数组下标为0的位置获取值返回；key不为空的话就会调用hash函数，这个hash函数会将key对应的hashCode值返回，将返回的hashcode与entry数组长度-1进行逻辑与运算得到一个index值，用这个index值来确定数据存储在entry数组当中的位置。
2、遍历链表；通过循环来遍历索引位置对应的链表，初始值为数据存储在entry数组当中的位置，循环条件为entry对象不为null，改变循环条件为entry对象的下一个节点。
3、判断hash函数得到的hash值；如果hash函数得到的hash值与entry对象中key的hash值相等并且entry对象当中的key值与get方法传进来的key值equals相同则返回entry对象的value值，否则返回null。
remove方法大致流程
扩容的大致原理
源码分析
重要属性及常量
属性
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。//至于为什么这么做，后面会有详细分析。transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;/**实际存储的key-value键值对的个数*/transient int size;/**扩容阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到*/int threshold;/**负载因子，代表了table的填充度有多少，默认是0.75加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。*/final float loadFactor;/**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException，达到快速失败的效果*/transient int modCount;
常量
/**数组的默认初始容量16-必须是2次幂。*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/**最大容量：如果任何一个具有参数的构造函数隐式指定了（is implicitly specified by）一个更大的值，则使用的该最大容量。必须是2次幂<= 1<<30。*/static final int MAXIMUM_CAPACITY = 1 << 30;/**默认装载因子，在构造函数中未指定加载因子时使用。*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/**一个空表实例，以便在表没有膨胀时共享。*/static final Entry<?,?>[] EMPTY_TABLE = {};
内部结构
Entry是HashMap中的一个静态内部类。
static class Entry<K,V> implements Map.Entry<K,V> {final K key;// map中key值，可以为null。V value;// map中的value值，可以为null。//存储指向下一个Entry的引用，单链表结构，防止key值不同，hash值相同,解决哈希冲突Entry<K,V> next;。int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}
常见的构造方法
HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值
initialCapacity默认为16，loadFactory默认为0.75
无参构造方法
//调用的是二参构造方法public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}
一参构造方法
//调用的是二参构造方法public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}
二参构造方法
从这段代码我们可以看出，在常规构造器中，并没有一开始就为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组
public HashMap(int initialCapacity, float loadFactor) {//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)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;threshold = initialCapacity;init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现}
PUT方法源码分析
public V put(K key, V value) {//判断哈希表内容是否为空，如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为thresholdif (table == EMPTY_TABLE) {//首次添加元素肯定为空，进行初始化===================================11111==================================================inflateTable(threshold);}//若果添加的元素对应的key是null，存储位置为table[0]或table[0]的冲突链上if (key == null)//会进行特殊处理，说明我们的HashMap是支持key为null的，将其放在table数组的第0个位置，哈希值是0；也有覆盖的情况return putForNullKey(value);//根据元素的key计算对应的hash值===================================2222===============================================int hash = hash(key);===================================3333===============================================//根据计算出来的hash值以及table数组的长度去计算元素存放的桶下标int i = indexFor(hash, table.length);/*为什么这里会有个循环呢？ JDK1.7的put方法在存入两个key相同的元素时，会进行覆盖操作，然后返回覆盖之前的key对应的value值，这里的循环就是用来判断该桶下标对应的链表中是否有跟新添加元素相同的key。因为并不是每次遍历都会到链表尾部，所以不会在这个循环中将新添加的元素进行插入*///得到table数组下标后进行相应循环，刚开始循环时table[i]表示链表的头节点//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧valuefor (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//集合结构修改次数自增，保证并发访问时，若HashMap内部结构发生变化，快速响应失败modCount++;===================================4444===============================================//将这几个参数进行封装成Entry对象进行元素添加addEntry(hash, key, value, i);return null;}
111、inflateTable方法
inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17，capacity=32；
private void inflateTable(int toSize) {=====================================================================================// 将容量变化为2的次方数，比如传入的容量值是17，则返回一个32（2的五次方）int capacity = roundUpToPowerOf2(toSize);//保证capacity一定是2的次幂//计算扩容阈值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//创建一个新的table数组table = new Entry[capacity];initHashSeedAsNeeded(capacity);}
roundUpToPowerOf2
roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.
/*将容量变化为2的次方数，比如传入的容量值是17，则返回一个32（2的五次方）*/private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY==================这个number-1是保证若果number是16的话，最终返回的值也是16===================================================================: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}
若果是我们去实现这个方法的话，实现思路的关键是如何去判断一个数是否是2的次方数：
1----- 0000 00012----- 0000 00104----- 0000 01008----- 0000 100016---- 0001 0000这里有一个规律，某个数字转化成二进制的话，该二进制串中只有一个位置是1。
所以我们实现的关键就是将该数字转化成二进制数，然后判断该二进制数是否只有一个位置是1，其他位置全是0。这个先到这。
highestOneBit方法的作用是找到小于等于输入参数i的2的次方数，那这里是怎么利用它来获得我们想要的大于等于我们输入的容量的最小2的次方数的？我们可以将我们输入的容量进行左移一位，左移相当于乘2，即将容量变大一倍再传入该highestOneBit方法，最终就能得到我们想要的大于等于我们传入的容量的最小2的次方数。
比如传入的容量是17 ，先左移变成34 ，再调用highestOneBit方法变成32。
highestOneBit方法
/*该highestOneBit方法的作用是找到小于等于输入参数i的2的次方数*/public static int highestOneBit(int i) {// 进行多次的操作是因为int是32位整数的i |= (i >> 1);i |= (i >> 2);i |= (i >> 4);i |= (i >> 8);i |= (i >> 16);return i - (i >>> 1);}
该方法的推演过程：假如传入highestOneBit方法的参数 i = 17； 这个 >> 符号表示右移 （ / ） ， 这个| 表示或运算（有1为1）；
先看第一行代码： i |= (i >> 1); //假设 i =17 ，17 0001 0001 (17对应的二进制)i >> 1 0000 1000 (将17右移一位)i |= (i >> 1) 0001 1001 (将右移后跟原来的i 进行或运算)第二行代码： i |= (i >> 2); （将上面计算的结果进行操作，同理）此时的i 0001 1001i >> 2 0000 0110 （右移两位）i |= (i >> 2); 0001 1110剩下的分析同理，>> 8 0000 00000001 1111 (后面该结果不会变化)>> 16 0001 1111 （也就是说此时i对应的二进制数是这个）然后执行： return i - (i >>> 1);该句代码分析：i >>> 1 先将i再进行右移一位 ，然后用i 减去右移的结果，最后返回
为什么代码这样设计？可以看出，右移一位再进行或运算之后的效果是最高位的1的后一位也变为1；
001* **** （*表示0或1）>>1 0001 ****| 0011 **** (得到第二个1)
接下来再右移两位后再进行或运算之后的效果是最高位的1数起的第二个1的后两个位也变为1；
001* **** （*表示0或1）>>1 0001 ****| 0011 **** (得到第二个1)>>2 0000 11**| 0011 11**
也就是说每次进行这样的操作时都会将最高位的*变成1（右移几位就变几个）；一步一步将后面的位置变为1；
https://www.bilibili.com/video/BV1x741117jq?t=5077.21小时24分
所以最后用后来的 i 减去 i 右移一位，这个结果就是我们要的给定的任意数字，返回比其小的第一个2的次方数。
这里要把容量变成2的次方数这么复杂，那为什么硬是要将其变成2的次方数呢？这样做的意义是什么？这里先留个悬念。
222、hash方法
//这个k是添加的元素对应的keyfinal int hash(Object k) {//默认的hashSeed值为0int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//符号^表示异或操作，相同为0，不同为1//调用hashCode方法获取其哈希码，但因为h的值在上面赋值为0，0跟哈希码进行异或会改变h的值h ^= k.hashCode();//不断进行右移，异或操作h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);//Entry里面存的不是原来k.hashCode()方法返回的值，而是进行一系列操作后的值}
这里在算哈希码的时候为什么要进行这么多次的右移、异或操作呢？
这是因为在调用indexFor方法计算下标时，该哈希码要跟数组长度 -1 进行与操作，如下面的indexFor方法介绍的所示，因为int是32位的整数，而在进行与操作的时候哈希码只有低16位参与了与运算，而高16位不参与运算，完全不起作用；这就导致两个高位不同而低位相同的key算出来的数组下标产生哈希冲突的概率加大；
所以我们要尽量让高16位也参与运算，减少哈希碰撞的概率；那如何才能让哈希码的高16位也能参与到运算中来呢？这就是进行扰动，即多次的右移、异或操作的原因，目的就是为了让散列表更加散列、随机；
这里注意一点，因为传入的key可以是任意对象的，我们可以去重写它的hashCode方法，倘若你自己重写的方法没有对哈希码进行多次的扰动的话，得出来的散列表的散列性就会很差，链表的长度会很长，查询的性能就会很差；
333、indexFor方法
/*该方法返回值就是元素存放在桶数组的下标*/static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);}
HashMap对该方法返回的桶下标有两个要求：
1、该数组的下标不能越界
2、计算出来的下标要均衡
要满足这两个操作的话进行取余是非常合适的，但是该方法并不是用这个方法实现的，这里使用的是&与操作，并不能满足我们的要求.
但是：这里我们假设返回的哈希值对应的二进制是0101 0101，数组长度16；则 h & (length-1); 有如下运算
length-1=16-1=15
h: 0101 0101
15: 0000 1111
&: 0000 0101 (与运算，都为1才为1)
那么最终得出来的结果是否符合上面的两个要求？可以看出哈希码跟长度-1进行相与操作，得出来的结果是哈希码的低4位0101，而低四位的范围是0000~1111，正好是0~15，符合不越界的要求。而且由于哈希码的任意性，这0~15个数也是随机分布的；
这里符合第一个要求的关键是这个数组的长度是16，它是一个二的次方数，二的次方数的一个特点就是它对应的二进制串只有一个1，16减去1之后就得到一个高位全是0低位全是1的数15；
这也是为什么我们要求table数组的容量一定是2的次方数的原因；
至于为什么不用取模操作而用与操作，这是因为与操作是是位操作，是计算机中计算比较快的运算，比取模更快；
444、addEntry方法
通过以下代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
/*扩容阈值threshold=table数组长度 * 负载因子*/void addEntry(int hash, K key, V value, int bucketIndex) {//判断当前集合中的元素个数size是否大于等于扩容阈值，以确定是否需要进行扩容if ((size >= threshold)&&(null != table[bucketIndex])){===================================1111===============================================resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}===================================2222===============================================createEntry(hash, key, value, bucketIndex);}
1111、resize扩容方法
void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;//table数组已经最大了，不再进行扩容if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//创建一个新数组,容量是扩容后的容量值Entry[] newTable = new Entry[newCapacity];=========================11112222===============================================transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}
11111、initHashSeedAsNeeded方法
https://www.bilibili.com/video/BV1x741117jq?p=3&t=3542.7
第59分钟
/**初始化哈希种子，哈希种子的作用是让生成的哈希码更复杂，使散列表更为散列这个方法是判断是否进行重哈希的关键，这里我们重点关注其什么时候返回true什么时候返回false*/final boolean initHashSeedAsNeeded(int capacity) {//hashSeed哈希种子默认为0boolean currentAltHashing = hashSeed != 0;boolean useAltHashing = sun.misc.VM.isBooted() &&(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//进行异或操作，当两个不相等的情况下才会返回trueboolean switching = currentAltHashing ^ useAltHashing;if (switching) {hashSeed = useAltHashing? sun.misc.Hashing.randomHashSeed(this): 0;}return switching;}
那什么时候进行重哈希呢？
1：11：42之前
22222、transfer方法
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
使用双重循环将旧table数组的节点元素进行迁移到新数组中，注意在转移完成之后，原来链表中的节点顺序是1-2—3-4，会变成4-3-2-1
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {//执行while的一次过程就一个元素转移到新数组中，等while循环结束，该位置的链表就全转移到新数组中了；while(null != e) {Entry<K,V> next = e.next;//是否进行重哈希，默认falseif (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//重新计算元素在数组中的下标int i = indexFor(e.hash, newCapacity);// 下面两行代码包含头插法过程e.next = newTable[i];newTable[i] = e;//e = next;}}}
这个方法是如何将元素进行转移的呢？
rehash默认是false，也就是不进行重新计算哈希值，假设现在某个元素的哈希值对应的二进制是 0101 0101 ， 默认数组长度是16；那么使用indexFor方法进行计算数组下标的时候：容量为16hash 0101 010115 0000 1111& 0000 0101同样，我们在扩容的时候仍然是使用indexFor方法进行计算元素在数组对应下标的，这里rehash默认是false，哈希码就不产生变化，变化的只有数组的长度，由16->32换句话说，同样的哈希值用同样的indexFor方法进行计算，这里是有一个规律的容量为32hash 0101 010131 0001 1111 (只有第五位产生变化)& 0001 0101 （相与的结果只有第五位变化）从这里就可以看出，旧数组中的一个元素转移到新数组中时有两种情况，以上面的例子来说，第五位是0还是1决定了元素在新数组的位置是原来的位置还是新位置；若果第五位是0的话，那么元素在新数组中的下标位置不变；若果是1的话，那么元素在新数组中下标的位置是旧数组长度加上原来下标位置；当然这个规律的前提条件是元素的哈希码没有进行重哈希；
jdk1.7中循环链表的出现
其中一种情况；
上面分析transfer方法时都是考虑在单线程情况下的，在JDK1.7中，倘若该扩容过程是在多线程情况下，可能会发生链表循环的情况；
假设有两个线程同时对同一个hashmap对象调用put方法
然后两个线程同时判断出来需要进行扩容，所以两个线程都进入到了resize方法中，所以两个线程都会去生成一个数组，然后进入transfer方法
也就是说两个线程都会去进行transfer方法的双重循环，将旧数组的元素往新数组中迁移；假设现在两个线程都执行到了这一行代码
对应的指针指向情况如下所示
这个时候，线程1继续往下执行，而线程2停留在**Entry<K,V> next = e.next;**这行代码里，即线程2指向的元素在线程1进行转移的过程中一直都没有发生变化；在线程1执行完转移后，**由于头插法的缘故**，原本链表的顺序从1-2-3变成了3-2-1；因为线程2在线程1转移的过程中卡住了，在线程1执行完转移后线程2的情况如下所示
这个时候线程2又开始执行了，但是这个时候线程2再将元素迁往线程2创建的新数组的时候（两个线程创建的数组不一样）就会产生循环链表了；
恰好线程二又将线程1扩容后的数组进行覆盖成循环链表的数组，这个时候倘若有人采用get方法去获取存在于循环链表中的元素的话，就会不停的进行循环。
而出现循环的关键就是jdk1.7在put方法的时候采用的是头插法；
那为什么要遍历链表将其中的节点一个一个地进行迁移而不是直接将链表的头节点直接迁移到新数组中？
这是因为，扩容的目的是让原来数组中的元素在新数组中的分布更为散列；这样在转移的时候遍历链表，就能够使每个节点分布在数组中的桶位置不同，进而使元素的分布更为均匀，这样在查询的时候效率会更高，而不是只放在一个链表中，使链表的长度不断变长，进而将链表进行拆剪；
而上面的循环链表出现的情况，是假设某个链表在数组进行迁移的时候其元素仍然是迁移到新数组的相同下标又重新形成链表的极为特殊的情况；
2222、createEntry方法
/*bucketIndex：元素存放的桶下标*/void createEntry(int hash, K key, V value, int bucketIndex) {//下面的两句代码做包含了元素添加的头插法过程Entry<K,V> e = table[bucketIndex];//根据计算出来的hash, key, value, e创建出新的Entry对象（就是我们新添加的元素）table[bucketIndex] = new Entry<>(hash, key, value, e);//将元素个数自增size++;}
GET方法源码
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
public V get(Object key) {//如果key为null,则直接去table[0]处去检索即可。if (key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}
getEntry 方法
可以看出，get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}//通过key的hashcode值计算hash值int hash = (key == null) ? 0 : hash(key);//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}
要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。
重写equals方法需同时重写hashCode方法
public class MyTest {private static class Person{int idCard;String name;public Person(int idCard, String name) {this.idCard = idCard;this.name = name;}@Overridepublic boolean equals(Object o) {if (this == o) {return true;}if (o == null || getClass() != o.getClass()){return false;}Person person = (Person) o;//两个对象是否等值，通过idCard来确定return this.idCard == person.idCard;}}public static void main(String []args){HashMap<Person,String> map = new HashMap<Person, String>();Person person = new Person(1234,"乔峰");//put到hashmap中去map.put(person,"天龙八部");//get取出，从逻辑上讲应该能输出“天龙八部”System.out.println("结果:"+map.get(new Person(1234,"萧峰")));}}实际输出结果：null
如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到同一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
JDK1.8的HashMap
红黑树前置知识
二叉搜索树
二叉搜索树 - 定义
二叉树的定义很容易理解，在二叉树的基础上加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。
这个要求就是：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
二叉搜索树 - 查找节点
查找某个节点，必须从根节点开始查找。
①、查找值比当前节点值大，则搜索右子树;
②、查找值等于当前节点值，停止搜索（终止条件);
③、查找值小于当前节点值，则搜索左子树;
二叉搜索树-插入节点
要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性,待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置。
二叉搜索树-遍历节点
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的二叉树遍历有前序遍历，中序遍历和后序遍历。
而二叉搜索树最常用的是中序遍历，因为这样子遍历出来的顺序是从小到大升序的。
①、中序遍历:左子树——》根节点——》右子树
②、前序遍历:根节点——》左子树——》右子树
③、后序遍历:左子树——》右子树——》根节点
二叉搜索树-查找最大值和最小值
要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。
同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。
二叉搜索树-删除节点
删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂.
1、该节点是叶节点(没有子节点)
2、该节点有一个子节点
3、该节点有两个子节点
①、删除没有子节点的叶子节点
要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为null即可。
②、删除有一个子节点的节点
删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。
③、删除有两个子节点的节点
当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。
既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢?
我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字 的次高节点是它的中序遍历后继节点。用后继节点来代替制除的节点，显然该二叉搜索树还是有序的。
例如，
那么如何找到删除节点的中序后继节点呢?
其实我们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。后继节点也就是:比删除节点大的最小节点。
④、删除有必要吗?
通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete。
当该字段为true时，表示该节点已经删除，反之则没有删除。这样删除节点就不会改变树的结构了。
影响就是查询时需要判断一下节点是否已被删除。
二叉搜索树 - 时间复杂度分析
对于一个有序的数组（排列），使用二分查找算法的时间复杂度能达到O（logn），每次查询都能排除一半的元素。但是二分查找算法有一个缺陷，那就是必须依赖一个有序的数组。而数组的缺陷就是容量是固定的，这样在插入、删除元素的时候就毕竟麻烦，比如删除某个元素时需要将该位置后面的所有元素往前移动一步；而数组的容量是固定的，一旦数组装满了，再去添加元素的时候就需要创建一个比之前元素更大的数组，同时将原来数组的元素迁移到新数组中。这样不太灵活，既不能快速插入也不能灵活扩容。
所以我们就想让二分查找算法能够像链表一样能够灵活插入并扩容，同时还能保持二分查找的高性能。二叉搜索树就是干这个的，它即能够灵活插入元素，又能保持二分的高性能查找。
二叉搜索树的缺陷
但是普通的二叉搜索树又有一个致命的缺陷，那就是在极端的情况下二叉树会退化成链表
这样它的查找性能就大为下降，达不到每次判断淘汰一半的效果，退化为O（N）。自然而然，我们就会想到将其优化为一颗在插入元素时，可以自动调整树的两边平衡的AVL平衡树。
AVL树
AVL树，它在插入和删除节点时，总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制，插入一个节点和删除一个节点都有可能调整多个节点的不平衡状态。
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在O(logn)，不过却不是最佳的,
因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整。
频繁的左旋转和右旋转操作一定会影响整个AVL树的性能，这会使平衡树的性能大打折扣，除非是平衡与不平衡变化很少的情况下，否则AVL树所带来的搜索性能提升不足以弥补平衡树所带来的性能损耗。
那有没有绝对平衡的一种树呢？没有高度差也不会有平衡因子，没有平衡因子就不会有调整旋转操作。2-3树正是一种绝对平衡的树，任意节点到它所有的叶子节点的深度都是相等的。
2-3树的数字代表一个节点有2到3个子树。它也满足二分搜索树的基本性质，但它不属于二分搜索树。
2-3树
2-3树：由2节点、3节点组成 。 在这两种节点的配合下，2-3树可以保证在插入值过程中，任意叶子节点到根节点的距离都是相同的。完全实现了矮胖矮胖的目标。
2-节点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父节点，右子树所有元素的值均大于它父节点；
3-节点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父节点，中子树所有元素的值都位于父节点左右两个元素之间，右子树所有元素的值均大于它父节点；
其子树也是空树、2-节点或者3-节点；
没有元素相等的节点。
https://www.bilibili.com/video/BV1DE411i77d?spm_id_from=333.337.search-card.all.click3分
上图就是一个2 - 3 树，根节点10有两个指针，所以它是一个2节点；同理根节点左边的5也是一个2节点；而根节点右边的12、15有三个指针，所以是一个3节点（包含了12、15两个元素）；
图中也可以很容易看出来这颗树的所有叶子节点都在同一层次中
2-3树查找元素
2-3树的查找类似二分搜索树的查找，根据元素的大小来决定查找的方向。要判断一个元素是否存在，我们先将待查找元素和根节点比较，如果它和其中任意一个相等，那查找命中；否则根据比较的结果来选择查找的方向。
2-3树插入元素
插入元素首先进行查找命中，若查找命中则不予插入此元素，如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中，则在叶子节点中插入这个元素。
空树的插入很简单，创建一个节点即可。如果不是空树，插入的情况分为4种：
1、向2-节点中插入元素；
如果未命中查找结束于2-节点，直接将2-节点替换为3-节点，并将待插入元素添加到其中。 
2、向一颗只含有一个3-节点的树中插入元素；
如果未命中查找结束于3-节点，先临时将其成为4-节点，把待插入元素添加到其中，然后将4-节点转化为3个2-节点，中间的节点成为左右节点的父节点。
如果临时4-节点有父节点，就会变成向一个父节点为2-节点的**3-节点**中插入元素，中间节点与父节点为2-节点的合并。 ？？？？？？？？？？
3、向一个父节点为2-节点的3-节点中插入元素；
4、向一个父节点为3-节点的3-节点中插入元素。
插入元素后一直向上分解临时的4-节点，直到遇到2-节点的父节点变成3-节点不再分解。如果达到树根节点还是4-节点，则进行分解根节点，此时树高+1（只有分解根节点才会增加树高）。
2-3树元素删除
红黑树
红黑树的定义
文档https://www.cnblogs.com/lukazan/p/14702151.html视频https://www.bilibili.com/video/BV1UJ411J7CU?p=2
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [**注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！**]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。**不可以同时存在两个红色节点相连
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
如果一个节点存在黑色子节点，那么该节点肯定至少有两个子节点？？**
红黑树并不是一个完美平衡二叉查找树，根结点的左子树可以比右子树高（反之也行）,但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。
红黑树的性质讲完了，只要这棵树满足以上性质，这棵树就是趋近与平衡状态的,
红黑树的插入操作
执行插入操作的时候，首先要找到新节点应该插入的位置，再考虑是否符合红黑树的定义，然后决定做出何种调整；
- 查找插入的位置：插入节点的颜色必须是红色，插入黑色节点会破坏平衡
- 插入后自平衡
红黑树能自平衡，它靠的是三种操作:左旋、右旋和变色。
1.变色:结点的颜色由红变黑或由黑变红。
⒉.左旋:以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结沦的左子结点变为旋转结点的右子结点，左子结点保持不变。
3.右旋:以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
插入元素的时候，如果父节点是黑色的，则整棵树不必调整就已经满足了红黑树的所有性质。如果父节点是红色的（可知，该父节点的父结点一定是黑色的)，则插入新节点后，违背了红色结点只能有黑色孩子的性质，需要进行调整。
(1) 情景1：红黑树为空树
- 将插入节点作为根节点，然后将根节点设置为黑色
(2) 情景2：插入点的key已存在
- 替换原节点的value值
(3) 情景3：插入节点的父节点是黑节点
- 直接插入，不会影响自平衡
(4) 情景4：插入节点的父节点是红节点
根据性质2：父节点为红色一定不是根节点；根据性质4：爷节点肯定是黑色。
找到新节点插入的位置后，有以下几种情况
情景4.1：新节点的叔叔节点存在，且为红色
- 将父节点P和叔节点U改为黑色
- 爷节点PP改为红色。
- 进行后续处理:（进行递归或迭代处理）
- 如果PP的父节点是黑色，则无需处理
- 如果PP的父节点是红色，将PP设为当前插入节点，继续做自平衡处理
情景4.2：叔节点不存在或为黑节点，且插入节点的父节点是爷节点的左孩子
注意：叔叔节点应该非红即空，否则破坏性质5
情景4.2.1：插入节点是父节点的左孩子（LL双红情况）
- 将父节点P设为黑色，将爷节点PP设为红色
- 对爷节点PP进行右旋
情景4.2.1：插入节点是父节点的右孩子（LR双红情况）
- 对父节点P进行左旋
- 将P设为当前节点，得到LL双红情况
- 将I设为黑色，将爷节点PP设为红色
- 对爷节点PP进行右旋
情景4.3：叔叔节点不存在或为黑节点，且插入节点的父节点是爷节点的右孩子
对应情景4.2，只是方向相反
情景4.3.1：插入节点是父节点的右孩子（RR双红情况）
- 父节点P设为黑色，爷节点PP设为红色
- 对爷节点PP进行左旋
情景4.3.2：插入节点是父节点的左孩子（LR双红）
- 对父节点p进行右旋
- 将P节点作为当前节点，得到RR双红情况
- 把I设为黑色，爷节点PP设为红色
- 对爷节点PP进行左旋
插入演示
（注意红黑树中的叶子节点是指NULL节点）
红黑树插入元素的时候需要查找插入的位置，而且插入节点的颜色必须是红色，插入黑色节点会破坏平衡。
1、红黑树为空树，此时插入一个节点10作为根节点，并使之变为黑色；
2、插入一个节点20，由于节点20比10大，所以该节点放在根节点的右边；此时的树符合红黑树的定义；
3、插入一个节点30，此时30比根节点10大，所以来到其右边，又发现30比20大，故又将其放在20的右边。此时再来判断一下该树是否符合红黑树的5大定义；
很明显不符合第四条如果一个节点是红色的，则它的子节点必须是黑色的。所以此时需要进行调整，也就是进行左旋，结果就是将根节点10旋转成节点20的左节点，节点20就变为新的根节点；此时节点10变成红色节点20变成黑色；
4、然后再插入一个节点40，寻找插入位置的时候应该放在节点30的右边，这个时候很明显不符合红黑树定义需要进行调整；
此时就不需要进行左旋+变色来调整了，只需要变色即可。首先将节点10、30变成黑色，节点20变成红色，此时根节点不符合定义，再把根节点变回黑色。
5、再添加一个节点25，应该放在节点30的左边；此时符合红黑树的定义，不需要调整；
添加一个节点5放在10的左边，也不需要调整；
6、再次添加节点50，应该放在40右边；此时新添加的节点的父节点40是红色的，且父节点40的兄弟节点，也就是新添加节点的叔叔节点是红色的，对应情况4.1
7、插入节点35，插入的位置在节点40的左边，无需调整；再插入一个节点60，位置在50右边，还是对应情况4.1，即在调整过程中出现了连续的红节点；
最后调整之后的情况如下所示
Jdk1.8的HashMap概述
基础
我们知道，数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入和删除也容易的数据结构呢？答案是肯定的，这就是我们要提起的哈希表，也叫散列表。事实上，哈希表有多种不同的实现方法，我们接下来解释的是最经典的一种方法 —— 拉链法，我们可以将其理解为链表的数组 。
我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是 哈希算法。
总的来说，哈希表适合用作快速查找、删除的基本数据结构，通常需要总数据量可以放入内存。在使用哈希表时，有以下几个关键点：
- hash 函数（哈希算法）的选择：针对不同的对象(字符串、整数等)具体的哈希方法；
- 碰撞处理：常用的有两种方式，一种是open hashing，即 >拉链法；
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，它的基本原理就是把任意长度的输入通过散列算法这种映射规则，变换成固定长度的输出，被映射输出的二进制串就是散列值（哈希值）；这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入的空间。
Hash具有如下特点:
**不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。**也就是说从hash值不可以反向推导出原始的数据。<br /> 所有散列函数都有如下一个基本特性**：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，****输入值不一定相同**。
什么是哈希冲突？
由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间，所以根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。
抽屉原理:桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的”“抽屉原理”。
而当两个**不同的输入值，根据同一散列函数计算出相同的散列值**的现象，我们就把它叫做碰撞（哈希碰撞）。 也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
所以我们选择的hash算法要尽可能的减少哈希冲突的概率；
但是产生了哈希冲突又怎么解决？
哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
HashMap继承体系
HashMap底层存储结构
我们知道，在Java中最常用的两种结构是 数组 和 链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。实际上，HashMap 就是一个 链表数组，如下是它数据结构：
从上图中，我们可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity 就代表了该数组的长度，也就是桶的个数。
面试常问
Put方法大致过程
问题：key相同，hash值一定相等吗？
PUT方法添加元素的大致过程
在HashMap中，我们最常用的两个操作就是：put(Key,Value) 和 get(Key)。其中put方法的大致过程是这样的，
1、程序员调用hashMap对象的put方法将元素添加进集合；
2、通过扰动函数计算新添加元素的key对应的hash值，同时也使元素的hash更加散列，然后用计算出来的hash值跟table数组长度-1后的值相与得到新添加元素应该添加在table数组的下标
3、判断Node类型的table数组该位置的元素情况
3.1、若该位置的元素为空，也就是还没有Node对象；则将要添加的元素封装成Node对象并直接放在该位置
3.2、若该位置已经有元素了，此时又分为以下几种情况
3.2.1、该桶位置的第一个元素的key跟要添加的元素key值以及哈希码相等，将元素的value值进行替换
3.2.2、该桶位置的元素已经链表化，且链表的头元素与要插入的key不一致；这个时候遍历链表元素，又有以下几种情况：
3.2.2.1、遍历完链表后也没有找到链表中跟新添加元素key相同的节点，则将元素封装成链表节点添加到链表的尾部（注意jdk1.8之前是头插入，1.8之后是尾插，为了防止出现死链）
注意，把元素插入链表尾部之后判断是否达到树化标准，在链表的元素个数达到8个且数组table的长度达到64的时候就会触发树化函数 将链表树化为红黑树。
3.2.2.2、如果当前key已经存在该链表中了，跳出for循环，进行替换。
3.2.3、该桶位置的链表已经树化，此时将元素封装成红黑树节点，然后先找到新插入节点应该添加到红黑树中的位置，然后进行红黑树的调整。
4、元素添加进hashMap后代表修改次数的属性modCount以及代表元素数量的属性size都自增1，同时在自增后判断元素的数量是否达到扩容的阈值，若果达到就进行扩容。
GET方法查找元素的大致过程？
1、通过key的Hash找到唯一的桶下标位置。寻找方法和put过程中是相同的，都是通过与运算(capacity-1)&hash
2、找到具体桶位，现在有两种情况
2.1、如果该桶位置的首元素key和目标key相同，则返回首元素。
2.2、如果该桶位置的首元素的key不相同。则判断有没有第二个元素
2.2.1、如果没有，在该桶位处就没必要再找，直接返回null。
2.2.2、如果有第二元素。则判断首元素类型
2.2.2.1、如果为链表，采用do-while循环遍历桶中链表，查看链表中是否有要查找的元素
2.2.2.2、如果为红黑树，用红黑树的遍历方式，即调用getTreeNode()方法进行查找匹配；
2.2.2.2.1、首先找到根节点Root，从根节点向下找。
2.2.2.2.2、然后，根据查找key的hash值和当前node的hash值比较
2.2.2.2.2.1、如果大于，就向右边找。
2.2.2.2.2.2、如果小于，就向左找。
2.2.2.2.2.3、如果相同并比较equals相同，就返回当前节点
2.2.2.2.2.4、如果左孩子没有了，就向右孩子找。
2.2.2.2.2.5、如果右孩子没有了，就向左孩子找。
2.2.2.2.2.6、如果没有找到就进入下一轮递归寻找。
快速失败机制是什么？
https://www.bilibili.com/video/BV1x741117jq?p=3&t=4712.01：18：15
public static void main(String[] args) {HashMap<String,String> hashMap=new HashMap<>();hashMap.put("1","1");hashMap.put("2","2");for(String key : hashMap.keySet()){if ( key.equals("1"))hashMap.remove(key);}}
如何保证key的唯一性呢？
我们都知道，HashMap中的Key是唯一的，那它是如何保证key的唯一性呢？
我们首先想到的是用equals比较，没错，这样可以实现，但随着元素的增多，put 和 get 的效率将越来越低，这里的时间复杂度是O(n)。也就是说，假如 HashMap 有1000个元素，那么 put时就需要比较 1000 次，这是相当耗时的，远达不到HashMap快速存取的目的。
实际上，HashMap 很少会用到equals方法，因为其内通过一个哈希表管理所有元素，利用哈希算法可以快速的存取元素。当我们调用put方法存值时，HashMap首先会调用Key的hashCode方法，然后基于此获取Key哈希码，然后通过哈希码快速找到某个桶下标，这个位置可以被称之为 bucketIndex。
还有，如果两个对象的hashCode不同，那么equals一定为 false；否则，如果其hashCode相同，equals也不一定为 true。所以，理论上，hashCode 可能存在碰撞的情况，当碰撞发生时，这时会取出bucketIndex桶内已存储的元素，并通过hashCode() 和 equals() 来逐个比较以判断Key是否已存在。如果已存在，则使用新Value值替换旧Value值，并返回旧Value值；如果不存在，则存放新的键值对
此外，如果HashMap中存在键为NULL的键值对，那么一定在第一个桶中。
能否使用任何类作为 Map 的 key？
可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：
- 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。
- 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
- 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
- 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。
为什么HashMap中String、Integer这样的包装类适合作为K？
答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率 。
- 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
- 内部已重写了
equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况；
如果使用Object作为HashMap的Key，应该怎么办呢？
答：重写hashCode()和equals()方法
- 重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
- 重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；
HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table数组的下标？
答：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，没有那么多空间就会导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
那怎么解决呢？
1、HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
2、在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储。这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；
hashCode()和equals()方法的重要性体现在什么地方？
Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。
为什么引入红黑树？
jdk1.7中的hashmap是数组+链表，虽然说在元素数量达到一定阈值的时候也会进行扩容，但是当链表中的元素越来越多的时候，链表中的查询效率就会下降， 最坏的时候时间复杂度O(n) ；
为了提升在 [hash]冲突严重时（链表过长）的查找性能，1.8引入 了红黑树之后，在链表的元素达到一定的数量之后就会树化成红黑树，而红黑树的特点是一颗黑节点完美平衡的树，能够保证节点的高性能查找以及插入，弥补了1.7中的缺陷； 使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。
什么时候会进行树化？什么树化进行树退化为链表？
对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点的方法（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。
对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。
为什么链表转红黑树的树化阈值是8？为什么转回链表节点是用的6而不是复用8？
我们平时在写代码的时候，必须考虑的两个很重要的因素是：时间和空间。对于 HashMap 也是同样的道理，简单来说，树化阈值为8是在时间和空间上权衡的结果 。
首先和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。在负载因子为0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一。将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6又退化成链表。链表中元素个数为8时的概率已经非常小，再多的概率就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。
而且红黑树中的TreeNode是链表中的Node所占空间的2倍，虽然红黑树的查找效率为o(logN)，要优于链表的o(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。所以，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。
Java的源码贡献者在进行大量实验发现，hash碰撞发生8次的概率已经降低到了0.00000006，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因，此次操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。所以，这个时候，就应该将链表转换为红黑树了，也就是为什么链表转红黑树的阈值是8。
最后，红黑树转链表的阈值为6，主要是因为，如果也将该阈值设置于8，那么当hash碰撞在8时，会反生链表和红黑树的不停相互激荡转换，白白浪费资源，造成性能的损耗。
HashMap 有哪些重要属性？分别用于做什么的？
除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：
1）size：表示HashMap 已经存储的节点个数；
2）threshold（thres hold）：扩容阈值，当 HashMap 的个数达到该值，触发扩容。
3）loadFactor（load Factor）：负载因子，扩容阈值 = 容量 * 负载因子。
4）modCount：表示集合结构的修改次数。
thres hold 除了用于存放扩容阈值还有其他作用吗？
HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
默认初始容量是16。HashMap 的容量的限制是容量必须是2的N次方。
HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。
为什么HashMap 的容量必须是2的N次方？怎么来的？
因为HashMap 中的数据结构是数组加链表还有红黑树嘛，数组中放的就链表，在我们把元素添加进HashMap 的时候，需要先计算出元素应该放在数组中的哪一个位置。计算的方法就是先根据元素的key算出相应的哈希值，然后拿该哈希值跟数组的长度-1进行相与，然后得到我们添加的元素将要添加到数组中的哪一个桶下标。但是这个下标是有要求的， 首先该数组的下标不能越界其次计算出来的下标要均衡。
若果仅是满足这两个条件的话取模操作是非常合适的，但是这里之所以用的是相与操作是因为与操作是位操作，是计算机中计算比较快的运算，比取模更快；
而用与操作去计算下标的话，你用来跟哈希码进行相与的数组容量就必须是一个二的次方数，二的次方数的一个特点就是它对应的二进制串只有一个1，16减去1之后就得到一个高位全是0低位全是1的数15（假如数组容量是16）；这样哈希码不管它的二进制是怎样的，它跟一个高位全是0低位全是1的数15进行相与操作，结果的范围只可能是0-15保证了数组不越界，而且由于哈希码的不确定性，同时保证了计算出来的下标是均匀分布的。
简单来说，之所以是2的次方数，就是为了让相与操作跟取模操作的结果一样。
为什么负载因子是0.75而不是其他的？
这个应该 是在时间和空间上权衡的结果。如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。
为什么要将 hashCode 的高16位参与运算？
HashMap在计算hashCode 的时候调用了hash方法对hashCode进行多次的扰动，1.7的hash源码如下：
//这个k是添加的元素对应的keyfinal int hash(Object k) {//默认的hashSeed值为0int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//符号^表示异或操作，相同为0，不同为1//调用hashCode方法获取其哈希码，但因为h的值在上面赋值为0，0跟哈希码进行异或会改变h的值h ^= k.hashCode();//不断进行右移，异或操作h ^= (h >>> 20) ^ (h >>> 12);//第一次扰动return h ^ (h >>> 7) ^ (h >>> 4);//第二次扰动//Entry里面存的不是原来k.hashCode()方法返回的值，而是进行一系列操作后的值}
这里在算哈希码的时候为什么要进行这么多次的右移、异或操作（两次扰动）呢？
这是因为在调用indexFor方法计算下标时，该哈希码要跟数组长度 -1 进行与操作，如下面的indexFor方法介绍的所示，因为int是32位的整数，而在进行与操作的时候哈希码只有低16位参与了与运算，而高16完全不起作用；这就导致两个高位不同而低位相同的key算出来的数组下标产生哈希冲突的概率加大；
所以我们要尽量让高16位也参与运算，减少哈希碰撞的概率；那如何才能让哈希码的高16位也能参与到运算中来呢？这就是进行扰动，即多次的右移、异或操作的原因，目的就是为了让散列表更加散列、随机；
1.8的hash方法做了改进，不知道区别是什么？是引进了红黑树？？
这里注意一点，因为传入的key可以是任意对象的，我们可以去重写它的hashCode方法，倘若你自己重写的方法没有对哈希码进行多次的扰动的话，得出来的散列表的散列性就会很差，链表的长度会很长，查询的性能就会很差；
HashMap扩容的大致原理
因为当哈希表中的元素越来越多时，必然会影响查找性能，查找效率本来是O（1），元素多了就成了O（N）了，所以需要进行扩容让哈希表容量变大，将其中的元素分散，提高性能，缓解查找压力；
扩容的大致流程如下，
红黑树和链表都是通过 e.hash & oldCap == 0 来定位在新表的索引位置，这是为什么？
值得一看
介绍一下死循环问题？
导致死循环的根本原因是 JDK 1.7 扩容采用的是“头插法”，会导致同一索引位置的节点在扩容后顺序反掉。而 JDK 1.8 之后采用的是“尾插法”，扩容后节点顺序不会反掉，不存在死循环问题。
其中一种情况；
上面分析transfer方法时都是考虑在单线程情况下的，在JDK1.7中，倘若该扩容过程是在多线程情况下，可能会发生链表循环的情况；
假设有两个线程同时对同一个hashmap对象调用put方法
然后两个线程同时判断出来需要进行扩容，所以两个线程都进入到了resize方法中，所以两个线程都会去生成一个数组，然后进入transfer方法
也就是说两个线程都会去进行transfer方法的双重循环，将旧数组的元素往新数组中迁移；假设现在两个线程都执行到了这一行代码
对应的指针指向情况如下所示
这个时候，线程1继续往下执行，而线程2停留在**Entry<K,V> next = e.next;**这行代码里，即线程2指向的元素在线程1进行转移的过程中一直都没有发生变化；在线程1执行完转移后，**由于头插法的缘故**，原本链表的顺序从1-2-3变成了3-2-1；因为线程2在线程1转移的过程中卡住了，在线程1执行完转移后线程2的情况如下所示
这个时候线程2又开始执行了，但是这个时候线程2再将元素迁往线程2创建的新数组的时候（两个线程创建的数组不一样）就会产生循环链表了；
恰好线程二又将线程1扩容后的数组进行覆盖成循环链表的数组，这个时候倘若有人采用get方法去获取存在于循环链表中的元素的话，就会不停的进行循环。
而出现循环的关键就是jdk1.7在put方法的时候采用的是头插法；
那为什么要遍历链表将其中的节点一个一个地进行迁移而不是直接将链表的头节点直接迁移到新数组中？
这是因为，扩容的目的是让原来数组中的元素在新数组中的分布更为散列；这样在转移的时候遍历链表，就能够使每个节点分布在数组中的桶位置不同，进而使元素的分布更为均匀，这样在查询的时候效率会更高，而不是只放在一个链表中，使链表的长度不断变长，进而将链表进行拆剪；
而上面的循环链表出现的情况，是假设某个链表在数组进行迁移的时候其元素仍然是迁移到新数组的相同下标又重新形成链表的极为特殊的情况；
那总结下 JDK 1.8 主要进行了哪些优化？
1）底层数据结构从“数组+链表”改成“数组+链表+红黑树”，主要是优化了 hash 冲突较严重时，链表过长的查找性能：O(n) -> O(logn)。
2）计算 table 初始容量的方式发生了改变，老的方式是从1开始不断向左进行移位运算，直到找到大于等于入参容量的值；新的方式则是通过“5个移位+或等于运算”来计算。 有什么用呢？
3）优化了 hash 值的计算方式，老的通过一顿瞎操作，新的只是简单的让高16位参与了运算。
4）扩容时插入方式从“头插法”改成“尾插法”，避免了并发下的死循环。
5）扩容时计算节点在新表的索引位置方式从“h & (length-1)”改成“hash & oldCap”，性能可能提升不大，但设计更巧妙、更优雅。
源码
重要常量以及属性
重要常量
/**table数组的默认大小，*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/**table数组的最大容量*/static final int MAXIMUM_CAPACITY = 1 << 30;/**缺省的负载因子*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/**树化阈值，链表长度达到多少会变成红黑树*/static final int TREEIFY_THRESHOLD = 8;/**链表的长度下降到多少时会进行树降级为链表*/static final int UNTREEIFY_THRESHOLD = 6;/**当哈希表中所有的元素到达64个时才会升级会红黑树，并不是链表的长度达到8就会红黑树化，两个条件同时满足时才会树化存疑：（是桶的数量还是所有元素的数量？？？？？？）*/static final int MIN_TREEIFY_CAPACITY = 64;
重要属性
/**用Node维护的哈希散列表，啥时候初始化呢？*/transient Node<K,V>[] table;/***/transient Set<Map.Entry<K,V>> entrySet;/**当前哈希表中的元素个数*/transient int size;/**当前哈希表的结构修改次数，即增添删除元素时。替换元素不算变化*/transient int modCount;/**扩容阈值，即当哈希表的元素超过阈值时就会触发扩容*/int threshold;/**负载因子threshold = capacity * loadFactor ；*/final float loadFactor;
这里提到了两个非常重要的参数：初始容量 和 负载因子，这两个参数是影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量 (table 数组的大小)，初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。
对于使用 拉链法（下文会提到）的哈希表来说，查找一个元素的平均时间是 O(1+a)，a 指的是链的长度，是一个常数。特别地，若负载因子越大，那么对空间的利用更充分，但查找效率的也就越低；若负载因子越小，那么哈希表的数据将越稀疏，对空间造成的浪费也就越严重。系统默认负载因子为 0.75，这是时间和空间成本上一种折衷，一般情况下我们是无需修改的。
Node结构分析
大致源码
//我们存储的元素都会封装成一个node节点static class Node<K,V> implements Map.Entry<K,V> {//存储的是Node节点中key扰动后的哈希值，扰动的目的是hash分布更均匀。final int hash;//我们存的元素的key键final K key;//我们存的元素的value值V value;//产生哈希碰撞后指向节点的下一节点形成链表，当链表长度达到8且哈希表中所有元素达到64个时，该链表结构将升级为红黑树Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}
Node是HashMap的一个静态内部类，主要是实现了Map.Entry接口中的三个方法，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Entry 是构成哈希表的基石，是**哈希表所存储的元素的具体形式**。
K getKey();V getValue();V setValue(V value);
构造方法
构造方法有四个：
构造方法一
1、无参构造方法：什么参数也不传入，该构造方法内部只有一句代码，
public HashMap() {//指定负载因子为默认的0.75f。this.loadFactor = DEFAULT_LOAD_FACTOR;}
构造方法二
2、指定initialCapacity的构造方法：
public HashMap(int initialCapacity) {//方法内部套娃调用了第三个构造方法：this(initialCapacity, DEFAULT_LOAD_FACTOR);}
构造方法三
3、指定 initialCapacity 和 loadFactor的构造方法：
最关键的构造方法，看下面的源码分析
public HashMap(int initialCapacity, float loadFactor) {//初始容量不能小于0if (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;//为什么不直接赋值呢？防止传进来的数字乱七八糟的，它必须得是二的次幂，不是2的次方数的话就帮它变成2的次方数；也就是说tableSizeFor方法的作用就是返回一个大于等于当前参数initialCapacity的一个数字，该数字一定是2的次方数；this.threshold = tableSizeFor(initialCapacity);}
tableSizeFor方法1.8版本
构造方法四
4、参数为另外一个map实例的构造方法：会将map的值复制到当前map，具体参考后续源码分析
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
Put方法源码
public V put(K key, V value) {//put方法里面调用的也是putVal方法，说明该方法才是核心；之后再来看putVal方法，现在我们先来分析一下hash(key)方法return putVal(hash(key),key,value,false,true);}
hash(key)方法对应源码
之前我们说过，当我们往哈希表中插入元素时，首先会根据该元素的key对应经过扰动后的哈希值，然后该将哈希值与哈希表数组长度做某种运算，得到该元素在哈希表中的位置，再将元素放入该位置；<br /> 而这里所说的扰动函数就是这个hash方法
/**hash方法作用：让key的hash值高16位也参与路由运算*/static final int hash(Object key) {int h;//key为null时返回0；也就是说放入的元素key为0，它存储的位置就是哈希表中的第0个位置return (key == null) ?0:(h = key.hashCode()) ^ (h >>> 16);}
该函数的核心是 扰动计算的逻辑：(h = key.hashCode()) ^ (h >>> 16)
让key原本的hash码与自己右移十六位后，进行异或运算。这么做的原因是，在table数组长度不够长时，让高位也能参与运算。
因为路由寻址算法的计算方式是table.length - 1 & hash， 当table数组的长度比较小时，比如table=16时，table.length - 1 = 1111 （二进制），它的高位都为0，因此无论hash的高位值是多少，都是不会参与计算的，举个例子：
// Hash 产生碰撞示例：00000000 00000000 00000000 00000101 & 1111 = 0101//高位11111111没有产生作用，这里发生了碰撞00000000 11111111 00000000 00000101 & 1111 = 0101
而通过右移16位再进行异或计算后，低位上的值也会受到高位的影响，大大减少了Hash冲突的概率。还是上面的两个数，在经过扰动后，就不会再冲突了：
00000000 00000000 00000000 00000101 // H100000000 00000000 00000000 00000000 // H1 >>> 1600000000 00000000 00000000 00000101 // hash1 = H1 ^ (H1 >>> 16) = 500000000 11111111 00000000 00000101 // H200000000 00000000 00000000 11111111 // H2 >>> 1600000000 00000000 00000000 11111010 // hash2 = H2 ^ (H2 >>> 16) = 250// 没有 Hash 碰撞(n - 1) & hash1 = (16 - 1) & 5 = 5(n - 1) & hash2 = (16 - 1) & 250 = 10
这里也可以看出1.8的hash方法没有1.7的hash方法复杂，有一部分原因是加入了红黑树；1.7的hash方法之所以要进行多次的右移以及异或操作，就是为了使计算出来的hashCode哈希码的散列性更好，最终的目的是为了让元素在数组的位置更为均匀，链表的长度更短。
虽然1.8的hashCode的作用跟1.7的差不多，都是用来计算元素在数组的下标位置，只不过不需要那么散列了。因为有红黑树的加入，其查询、插入的效率都得到了一定的保证，所以这里的哈希hash方法就可以进行相应的简化，到时候执行到该方法就不需要消耗那么多的CPU资源了。
putVal方法对应源码
分析完扰动函数，接下来分析一下put方法的核心putVal方法
public V put(K key, V value) {//实际调用的是putVal方法//这里要注意的是扰动函数hash()return putVal(hash(key), key, value, false, true);}/*** Implements Map.put and related methods.* @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent 该参数表示如果散列表中已经存在某个key，就不进行插入元素了，这里默认是false。也就是说，若果已经存在该key对应的元素，那么就将该元素进行替换* @param evict 暂时不用管，用不到*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab：表示当前hash散列表；1.7是Entry类型，1.8变成了Node类型，但Node类型继承了Entry类型Node<K,V>[] tab;//p：当前散列表的桶元素；Node<K,V> p;// n：表示散列表数组的长度；i：表示路由寻址结果（元素存储的下下标）int n, i;/*懒加载。当tab为空时，也就是第一次插入数据时，才初始化最耗费内存的hash表；1、为什么是懒加载呢？因为刚开始创建出一个hashmap对象，可能还没有往里面存放数据，若果一创建出一个hashmap对象就给它创建哈希表，会占用极大的内存空间。所以第一次插入数据时，才初始化最耗费内存的hash表*/if ((tab = table) == null || (n = tab.length) == 0)//执行resize()，初始化，创建哈希表n = (tab = resize()).length;/*(n - 1) & hash 即是哈希表的路由算法，则tab[i = (n - 1) & hash]就是哈希表中的桶元素*/if ((p = tab[i = (n - 1) & hash]) == null)// 情况1：路由寻址算法找到的桶为null，那么直接将元素封装为node，再把node放进去tab[i] = new Node(hash, key, value, null);//情况2：找到的桶已经有数据了（可能是一个链节点，也可能是一个链表，还有可能已经树化）下面的三个分支走其中一个分支，决定是修改还是添加else {//e是一个临时的node元素（表示一个已存在的key相同的node）Node<K,V> e;//k表示一个临时的keyK k;//情况2.1：桶的头元素的key就是你要put插入的元素对应的key，hash相等还要判断值是否相等，如果完全一致，后续则进行值的替换操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//这种情况该位置只有一个节点元素e = p;//情况2.2：这种情况是树化之后，看树中是否与添加元素相同key的元素，没有则进行添加，有则返回else if (p instanceof TreeNode)======================================================================================e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//情况2.3：链化的情况，==且链表的头元素与要插入的key不一致==，这个时候遍历整个链表，没有则进行添加，有则返回for (int binCount = 0; ; ++binCount) {//情况2.3.1 ：e == null说明遍历结束，此时仍然没有相同的，那么直接加入链表（注意jdk1.8之前是头插入，1.8之后是尾插，为了防止出现死链）if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);/*判断插入元素后，是否达到树化标准，这里TREEIFY_THRESHOLD - 1是因为遍历链表的时候是从0开始的，当binCount=7时就已经表示前面有8个元素了，这个时候就会触发树化函数,换句话说触发的条件是8，但链表的长度已经是9了；*/if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st================================触发树化函数==========================================treeifyBin(tab, hash);break;}//情况2.3.2：如果当前key已经存在map中了，跳出for循环，后续会进行替换if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//遍历下一个元素p = e;}}//e!=null，说明当前key已经存在map中了，进行替换操作并且返回旧值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//当元素新增或者减少才会++modCount，修改旧值不会++modCount;// 散列表中的实际元素数量size如果大于阈值，扩容翻倍，扩容方法resize的内部逻辑跟1.7差不多if (++size > threshold)resize();//这个方法是ConcurrentHashMap才用到的，这里是的方法体是空的afterNodeInsertion(evict);return null;}
树化方法treeifyBin
这个方法里面是在链表中的元素达到树化标准的情况下将链表树化的逻辑
/**hash：要添加元素的key对应的hash值*/final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//如果数组长度小于64的话，不会进行树化if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//数组长度没达到64，而链表长度达到8，选择进行扩容resize();//判断数组该位置是否为空，不为空才进行树化else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;//树化第一步//遍历链表，将链表节点转化为树节点，并且通过prev、next属性生成TreeNode一个双向链表do {=============================将链表的每一个节点转化成树的节点=============================TreeNode<K,V> p = replacementTreeNode(e, null);//同时连接双向链表if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);//if ((tab[index] = hd) != null)================真正进行树化，调用的是双向链表的第一个节点的treeify方法==============hd.treeify(tab);}}
replacementTreeNode
这个方法是在遍历到某个链表节点时用来将链表节点替换成一个树的节点的
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
treeify方法
执行到这里的时候已经将单链表转化为一个TreeNode双向链表了。但是进行树化的时候跟prev属性关系不大，只起到一个辅助作用；
生成的主要流程如下：先将双向链表的第一个节点作为红黑树的根节点，然后用根节点的next属性找到下一个节点 ，然后将找到的这个属性插入到红黑树中去；然后再将下一个节点插入红黑树中，如此直到添加完成；
/*
*/
final void treeify(Node<K,V>[] tab) {
//
TreeNode<K,V> root = null;
//这个this就是双向链表中的第一个节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//记录下一个节点
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//root为空就先初始化root节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
/*在初始化root节点之后，后面的代码就是将元素添加到红黑树中；
想要将一个节点插入到红黑树中，第一步就是找到该节点应该添加到红黑树中的什么位置，也就是先找到该节点的父节点，下面的for循环做的就是这件事
*/
K k = x.key;
//新节点的哈希值
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//当前元素的哈希值大于新节点的哈希值
if ((ph = p.hash) > h)
dir = -1; //-1表示往红黑树的左边走
else if (ph < h)
dir = 1;//1表示往红黑树的右边走
//哈希值相等的情况
else if ((kc == null &&
//comparableClassFor方法是指，如果元素的key实现了Comparable接口的话，比较的时候用该key的比较方法去比较，如果实现了该接口返回值是null
(kc = comparableClassFor(k)) == null) ||
//用自己实现的Comparable接口中的比较规则进行比较，如果比较出来的结果还是相等的话，tieBreakOrder方法
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//将x节点插入后调整红黑树
root = balanceInsertion(root, x);
break;
}
}
}
}
=================================== ===================================================================
//执行该代码前，已经将table的该位置树化成了一颗红黑树了，root也指向了红黑树的根节点。这个方法的作用就是将红黑树的根节点赋值到table[i]
moveRootToFront(tab, root);
}
比较的先后顺序
moveRootToFront
由于在树化的时候将TreeNode节点生成了一个双向链表，在生成了红黑树之后，双向链表的prev跟next属性仍然指向的是树化的时候的情况，也就是说现在红黑树中同时存在双向链表跟红黑树。
这个方法会保证根节点出现在table数组的该位置的第一个节点。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
// 将红黑树的根节点赋值到table[index]
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//验证红黑树是否符合定义
assert checkInvariants(root);
}
}
putTreeVal方法
如果插入元素的时候发现table数组的该位置已经树化了，则调用该方法，里面的逻辑也是进行比较查看树中是否与添加元素相同key的元素，没有则进行添加，有则将该节点返回。其代码逻辑跟之前的大概差不多；
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
扩容resize方法源码
为什么需要扩容？
因为当哈希表中的元素越来越多时，必然会影响查找性能，查找效率本来是O（1），元素多了就成了O（N）了，所以需要进行扩容让哈希表容量变大，将其中的元素分散，提高性能，缓解查找压力；
如下图所示，putVal方法中，是先将size自增后再去比较是否大于扩容阈值threshold。这里是跟1.7是有区别的
下图是1.7中判断扩容的条件，它除了判断size是否大于等于扩容阈值，还多了一个条件，那就是table数组的该位置元素不能为空。而1.8就是直接判断是否大于扩容阈值。
https://www.bilibili.com/video/BV1LJ411W7dP?p=6&t=338.0
5分38秒
下面是1.8中的扩容方法的源码
final Node<K,V>[] resize() {
//扩容前的哈希表
Node<K,V>[] oldTab = table;
//oldCap：扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//扩容前的扩容阈值,即触发本次扩容时的阈值
int oldThr = threshold;
//newCap:扩容后的数组大小；newThr：下次再次触发扩容阈值
int newCap, newThr = 0;
//下面的一部分代码的目的就是计算出新的数组大小newCap和新的扩容阈值newThr
//情况1：当oldCap > 0表示 hashMap已经初始化过时，进行正常扩容
if (oldCap > 0) {
//情况1.1：如果扩容之前table数组的oldCap已经大于最大阈值容量MAXIMUM_CAPACITY，不再扩充，设置扩容阈值为int最大值（很难触发，极少数情况）
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//情况1.2：oldCap << 1左移一位进行翻倍，即将newCap值设置为oldCap长度*2。如果newCap不大于MAXIMUM_CAPACITY，并且oldCap的值是大于16的，那么下次的扩容阈值也左移一位进行翻倍
//对oldCap>=16的判断是因为精度问题
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//左移一位，进行翻倍
newThr = oldThr << 1; // double threshold
}
//情况2：oldCap==0，说明hashMap还没有初始化
/*
构造函数为这3种时，OldThr>0
1. new HashMap(initCap,LoadFactor)
2. new HashMap(initCap)
3.new HashMap(map)且map存在数据
*/
//此时newCap就是初始化的threshold
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//oldCap==0，oldThr也是0
// ：调用new HashMap()构造方法时，OldThr为空; 此时newCap和newThr都取默认值计算
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;
//上面的代码的目的就是计算出新的数组大小newCap和新的扩容阈值newThr
//接下来的代码是创建一个新的table数组，并将旧数组中的元素迁移到新数组中去；
//创建resize后的新数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//扩容核心,说明扩容之前已经存在table
if (oldTab != null) {
//遍历旧数组的每一个位置上的元素, 找到所有已经存在的数据进行处理，也就是放入新数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//e表示遍历过程中的当前node节点,table数组上的该位置有元素
if ((e = oldTab[j]) != null) {
//将旧数组该位置的元素置空
oldTab[j] = null;
//next为null，说明此处还未发生碰撞，当前bin只有单个数据，此时直接计算当前元素在新数组的桶位置并将其存储在该位置
if (e.next == null)//这个判断成功表示当前位置只有一个元素
//这样的话就直接计算元素在新数组的下标然后进行迁移
newTab[e.hash & (newCap - 1)] = e;
//table数组该位置元素不止一个，有两种情况，一种是树化，另一种是链表，这里是判断是否树化
else if (e instanceof TreeNode)
//进入到红黑树的扩容转移，split表示拆分，里面的逻辑跟转移链表差不多
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//链表的扩容转移
else { // preserve order
//低位链表（也就是参与路由计算位的首位为0）：存放在扩容之后数组的下标位置与扩容前一致
Node<K,V> loHead = null, loTail = null;
//高位链表（也就是参与路由计算位的首位为1）：存放在扩容之后的数组的下标位置为：当前下标位 + 扩容前的数组长度
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历结束后，将链表分为e.hash & oldCap结果是0的属于低位，用loHead连接，结果非0是高位用hiHead连接
do {
next = e.next;
// hash -> .... 1 1111
// hash -> .... 0 1111
// oldCap-> ... 1 0000(16)
// 计算结果要么是0要么是16，等于0，说明高位为0，放入低位链
//e.hash & oldCap的结果不是0就是非0，这里的逻辑是将结果是0的放在一起，不是0的有分在一起；
if ((e.hash & oldCap) == 0) {
//说明此时低位链为空，直接将e设为链表的head
if (loTail == null)
loHead = e;
//否则将链表的尾部指向e
else
loTail.next = e;
//再把e重新设为当前的tail
loTail = e;
}
//高位为1，放入高位链
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//低位链的元素在新tab中index不变
if (loTail != null) {
//切断与旧tab中高位链的处理
loTail.next = null;
newTab[j] = loHead;
}
//高位链的元素在新tab中被放入新的index
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
整个扩容的流程代码中注释写的非常明确，基本就是各种条件判断。在链化的情况进行扩容时，Java选择将原本的链表拆分成两条链表，根据判断节点的高位hash值来决定是高位链表还是低位链表。高位链表在新tab中的index为oldIndex + oldCap，低位链表在新tab中的index仍然为oldIndex。
高低位链表的计算方式，假设oldCap为16，源码中计算方式为(e.hash & oldCap) == 0：
hash1 = .... 1 1111
hash2 = .... 0 1111
oldCap = .... 1 0000
我们知道HashMap的路由寻址算法是hash & oldCap - 1 ，所以hash1 和 hash2 会被放入同一个桶位。而使用 hash & oldCap计算时，计算的结果只看他们的最高位，也就是oldCap为1的位。通过区分最高位，就划出了两条链表。
Get方法源码
public V get(Object key) {
Node<K,V> e;
//存的时候做了一次hash扰动，取的时候同理也要做一次hash扰动再匹配
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//引用当前hashTab的散列表
Node<K,V>[] tab;
//first：桶位中的头元素；e：临时node元素；
Node<K,V> first, e;
n：table数组长度
int n; K k;
//判断table非空 并且定位到的桶不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//情况1：定位到的桶，首个元素刚好就是要找的元素
// 判断桶上第一个node的hash和key的hash一致，并判断key的值和first node 的key是否相同，相同就返回第一个Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//情况2：定位到bin，bin内不止一个元素，可能链化或者树化
if ((e = first.next) != null) {
//情况2.1：树化
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//情况2.2：链化 ，链表方式查找Node： 采用do while形式遍历，保证循环至少走一次。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get方法逻辑比较简单，唯一要注意的点判断元素相等的逻辑：e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))。首先要判断hash值是否相等，然后还要判断key的值是否相等（用==和equals判断值，==对于基本类型的判断更快，小优化），因为存在hash冲突的情况。
getNode() 获取目标key的Node
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断node数组已经初始化，根据key的hash找到first node
if ((tab = table) != null
&& (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 判断桶上第一个node的hash和key的hash一致，并判断key的值和first node 的key是否相同，相同就返回第一个Node
if (first.hash == hash && ((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);
// 链表方式查找Node： 采用do while形式遍历，保证循环至少走一次。
do {
// 依次遍历，和遍历桶顶元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
remove方法源码
public V remove(Object key) {
Node<K,V> e;
//真正执行删除逻辑的代码是removeNode，如果删除成功会返回删除的值，否则返回null
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
matchValue ： 表示是否连value也一起进行匹配
*/
//真正执行删除的逻辑
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//p：当前Node ，tab：当前哈希表
Node<K,V>[] tab; Node<K,V> p;
// n：当前table长度 ， index：寻址结果，要删除的元素所在的桶位
int n, index;
//判断哈希表中是否有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
//定位到要移除元素所在的桶位置
(p = tab[index = (n - 1) & hash]) != null) {
//能进来这里表示桶里面是有元素的，需要进行元素匹配操作且删除
//node：查找到的结果；e：当前Node的next元素；
Node<K,V> node = null, e;
K k;
V v;
//情况1：当前桶的头元素就是要删除的元素（哈希值跟key值都一致）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//情况2：当前桶位中存在链表或者树
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是node的前一个元素，方便后面通过p.next=node.next来remove，
p = e;
} while ((e = e.next) != null);
}
}
//判断node不为空的话，说明找到了需要删除的数据，下面为删除逻辑
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//情况1：如果是树结构，走树的删除逻辑
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//情况2：桶的头元素就是要删除元素，
else if (node == p)
//那么将头元素的下一个元素放到第一位，就等于把旧的头元素删除了
tab[index] = node.next;
else
//情况3：链化且要删除元素非头元素的情况，删除node，p->node>nextNode => p->nextNode
//node是要删除的元素，p指向node的前一位
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
replace方法内部就是调用getNode方法进行替换的
若有收获，就点个赞吧
0 人点赞
