0. 简述
0.1 什么是hash
核心理论：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。
Hash的特点：
- 从hash值不可以反向推导出原始的数据
- 输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
- 哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
- hash算法的冲突概率要小
由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。
根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。
抽屉原理：桌子上有十个苹果，要把这十个苹果放到9个抽屉里，无论怎样放，我们会发现至少有一个抽屉里面放不少于两个苹果。
HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在，即主要用来存放键值对。其特点有：
- 1.8 前数据结构为数组+链表，1.8为数组+链表+红黑树
- 非线程安全的
- key和value都可以为null，但是键位置只能存在一个 null
- 存储是无序的
- 键是唯一的
面试题：引入红黑树的原因
jdk1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势。针对这种情况，jdk1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
0.1 扩容机制
- HashMap 默认初始桶位数16，如果某个桶中的链表长度大于8，则先进行判断：
- 如果桶位数小于64，则先进行扩容(2倍)，扩容之后重新计算哈希值，这样桶中的链表长度就变短了(之所以链表长度变短与桶的定位方式有关，请接着往下看)。
- 如果桶位数大于64，且某个桶中的链表长度大于8，则对链表进行树化(红黑树，即自平衡的二叉树)
- 如果红黑树的节点数小于6，树也会重新变会链表。
面试题：为什么优先扩容桶位数(数组长度)，而不是直接树化？
当长度小于64时，且链表长度大于8时，如果直接树化，可能会导致效率降低，主要在两方面，一是当长度小时，更容易hash冲突，当出现hash冲突时，相比于平衡红黑树，链表的效率会更高，二是此时threshold较小更容易扩容，扩容会导致红黑树重新计算相比链表会增加树化的步骤
思考: 效率问题
首先为什么要避免hash冲突，是因为数组的检索效率是相对来说是很高的，最好的情况就是没有冲突，直接索引获取节点。但这是无法避免的，解决办法是拉链法。当hashmap长度很短时，他取模的cap小，更容易冲突，需要先扩容。扩容后cap变大，允许存储更多的节点了，如果数据分配足够均匀，就不容易树化或再次扩容。当hashmap长度大于等于64时，链表长度大于8，如果不树化，那么链表会越来越长，效率会降低，所以要转成红黑树（参考上方 引入红黑树的原因）；而如果继续扩容，当有新的链表长度大于8时， 此时旧的threshold很可能还没用完就重新扩容，空间利用率会被降低。
1. 类注释（机翻）
由于类注释太长 放在了最后面：点击跳转至类注释
2. 类图
如图所示：
通过上述继承关系我们发现一个很奇怪的现象，就是 HashMap 已经继承了AbstractMap 而 AbstractMap 类实现了Map 接口，那为什么 HashMap 还要在实现 Map 接口呢？同样在 ArrayList 中 LinkedLis 中都是这种结构。据 Java 集合框架的创始人 Josh Bloch 描述，这样的写法是一个失误。在 Java 集合框架中，类似这样的写法很多，最幵始写 Java 集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，jdk 的维护者，后来不认为这个小小的失误值得去修改，所以就这样保留下来了。
2. 属性和常量
/*** The default initial capacity - MUST be a power of two.** HashMap的初始化容量（必须是 2 的 n 次幂）默认的初始容量为16*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.** 最大的容量为2的30次方*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** The load factor used when none specified in constructor.** 默认的装载因子*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** The bin count threshold for using a tree rather than list for a* bin. Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.** 树化阈值，当一个桶中的元素个数大于等于8时进行树化*/static final int TREEIFY_THRESHOLD = 8;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.** 树降级为链表的阈值，当一个桶中的元素个数小于等于6时把树转化为链表*/static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.** 当桶的个数达到64的时候才进行树化*/static final int MIN_TREEIFY_CAPACITY = 64;/*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)** Node数组，又叫作桶（bucket）*/transient Node<K,V>[] table;/*** Holds cached entrySet(). Note that AbstractMap fields are used* for keySet() and values().** 作为entrySet()的缓存*/transient Set<Map.Entry<K,V>> entrySet;/*** The number of key-value mappings contained in this map.** 元素的数量*/transient int size;/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash). This field is used to make iterators on Collection-views of* the HashMap fail-fast. (See ConcurrentModificationException).** 修改次数，用于在迭代的时候执行快速失败策略*/transient int modCount;/*** The next size value at which to resize (capacity * load factor).* The javadoc description is true upon serialization.* Additionally, if the table array has not been allocated, this* field holds the initial array capacity, or zero signifying* DEFAULT_INITIAL_CAPACITY.** 当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor* 如果尚未分配table array，则此字段保存初始数组容量，或零*/int threshold;/*** The load factor for the hash table.** 装载因子*/final float loadFactor;
3. 数据结构
3.1 Node
Node是一个典型的单链表节点，其中，hash用来存储key计算得来的hash值。
/*** Basic hash bin node, used for most entries. (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class Node<K,V> implements Map.Entry<K,V> {final int hash;// hash用来存储key计算得来的hash值final K key;// 键V value;// 值Node<K,V> next;// 下一个node节点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() {// 调用底层c++ 返回Key/Value的哈希码值，如果此对象为null,则返回0return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule}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;}}
3.2 TreeNode
TreeNode内部类，它继承自LinkedHashMap中的Entry类，TreeNode是一个典型的树型节点，其中，prev是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;}// 位于LinkedHashMap中，典型的双向链表节点，这个类之后会单独发文章论述static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}
4. 构造方法
4.1 HashMap()
构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）。
public HashMap() {// 将默认的负载因子0.75赋值给loadFactor，并没有创建数组this.loadFactor = DEFAULT_LOAD_FACTOR;}
面试题：为什么负载因子是0.75
作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
不是0.5或1 :
如果是0.5 ， 那么每次达到容量的一半就进行扩容，默认容量是16， 达到8就扩容成32，达到16就扩容成64， 最终使用空间和未使用空间的差值会逐渐增加，空间利用率低下。 如果是1，那意味着每次空间使用完毕才扩容，在一定程度上会增加put时候的时间。
完美负载因子？ :
参考：https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap
数学公式 完全没看懂，有一条评论说选择0.75可能是因为它和任意一个2的n次幂相乘都可以得到整数，我觉得有点道理
4.2 HashMap(int initialCapacity)
构造一个具有指定的初始容量和默认负载因子（0.75）HashMap 。
// 指定“容量大小”的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}
4.3 HashMap(int initialCapacity, float loadFactor)
构造一个具有指定的初始容量和负载因子的 HashMap。
/*** 指定“容量大小”和“负载因子”的构造函数* initialCapacity：指定的容量* loadFactor:指定的负载因子*/public HashMap(int initialCapacity, float loadFactor) {// 判断初始化容量initialCapacity是否小于0if (initialCapacity < 0)// 如果小于0，则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITYif (initialCapacity > MAXIMUM_CAPACITY)// 如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacityinitialCapacity = MAXIMUM_CAPACITY;// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值if (loadFactor <= 0 || Float.isNaN(loadFactor))// 如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal load factor: " + loadFactor);// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactorthis.loadFactor = loadFactor;// 一般不建议修改默认的负载因子this.threshold = tableSizeFor(initialCapacity);}
最后调用了tableSizeFor，来看一下方法实现：tableSizeFor
对于this.threshold = tableSizeFor(initialCapacity); 的疑问
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug，应该这样书写：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）
但是请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
4.4 HashMap(Map<? extends K, ? extends V> m)
包含另一个 “Map” 的构造函数
// 构造一个映射关系与指定 Map 相同的新 HashMap。public HashMap(Map<? extends K, ? extends V> m) {// 负载因子loadFactor变为默认的负载因子0.75this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
最后调用了 putMapEntries()，来看一下方法实现：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//获取参数集合的长度int s = m.size();if (s > 0) {//判断参数集合的长度是否大于0if (table == null) { // 判断table是否已经初始化// 未初始化，s为m的实际元素个数float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int// 计算得到的t大于阈值，则初始化阈值，将其变为符合要求的2的n次幂数if (t > threshold)threshold = tableSizeFor(t);}// 如果table已初始化过了，并且m元素个数大于阈值，进行扩容处理else if (s > threshold)resize();// 将m中的所有元素添加至HashMap中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();// 得到的key 和 value 放入 hashmapputVal(hash(key), key, value, false, evict);}}}
面试题：**float ft = ((float)s / loadFactor) + 1.0F;** 这一行代码中为什么要加 1.0F ？
(float)s/loadFactor 的结果是小数，加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量，更大的容量能够减少 resize 的调用次数(为了效率，应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。
例如：原来集合的元素个数是 6 个，那么 6/0.75 是8，由于8是 2 的n次幂，那么
if (t > threshold) threshold = tableSizeFor(t);执行过后，新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了，这样会导致在存储元素的时候，容量不够，还得继续扩容，那么性能降低了，而如果 +1 呢，数组长度直接变为16了，这样可以减少数组的扩容。
5. 方法
5.1 hash
/*** Computes key.hashCode() and spreads (XORs) higher bits of hash* to lower. Because the table uses power-of-two masking, sets of* hashes that vary only in bits above the current mask will* always collide. (Among known examples are sets of Float keys* holding consecutive whole numbers in small tables.) So we* apply a transform that spreads the impact of higher bits* downward. There is a tradeoff between speed, utility, and* quality of bit-spreading. Because many common sets of hashes* are already reasonably distributed (so don't benefit from* spreading), and because we use trees to handle large sets of* collisions in bins, we just XOR some shifted bits in the* cheapest possible way to reduce systematic lossage, as well as* to incorporate impact of the highest bits that would otherwise* never be used in index calculations because of table bounds.** 计算 key.hashCode() 并将散列的较高位（异或）传播到较低位。 由于该表使用二次幂掩码，* 因此仅在当前掩码之上位变化的散列集将始终发生冲突。* （众所周知的例子是在小表中保存连续整数的浮点键集。）* 所以我们应用了一种向下传播高位影响的变换。 位扩展的速度、效用和质量之间存在权衡。* 因为许多常见的哈希集已经合理分布（因此不会从传播中受益），* 并且因为我们使用树来处理 bin 中的大量冲突，* 所以我们只是以最便宜的方式对一些移位的位进行异或以减少系统损失，* 以及合并最高位的影响，否则由于表边界而永远不会在索引计算中使用。*/static final int hash(Object key) {int h;// 如果key为null，则hash值为0,// 否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,// 后与h无符号右移16位后的二进制进行按位 异或 得到最后的hash值,// 这样做是为了使计算出的hash更分散// 为什么要更分散呢？因为越分散，某个桶的链表长度就越短，之后生成的红黑树越少，效率越高return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
除上面的方法外，还有平方取中法，伪随机数法 和 取余数法。这三种效率都比较低，而无符号右移 16 位异或运算效率是最高的。
面试题：为什么要右移16位后异或？
当计算下标 (n - 1) & hash 时，n-1 就相当于一个低位掩码，在按位与时，它会把原散列值的高位置0，这样无论高位如何变化，低位相同，计算出的下标就相同，显然增大了冲突几率。而使用高低位异或，相当于变相的让键的高位也参与了运算，既降低冲突几率，也保证了效率
如下：
5.2 tableSizeFor
源码如下：
/*** Returns a power of two size for the given target capacity.** 返回比指定cap容量大的最小2的n次幂数*/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;}
流程如下：-------------------------------------------------------首先假定传入的cap = 10则，n = 10 -1 => 9n |= n >>> 1 就等同于 n = (n | n >>> 1),所以：9 => 0b1001 9 >>> 1 => 0b0100n |= n >>> 1; ===> 0b1001 | 0b0100 => 0b1101n |= n >>> 2; ===> 0b1101 | 0b0011 => 0b1111n |= n >>> 4; ===> 0b1111 | 0b0000 => 0b1111n |= n >>> 8; ===> 0b1111 | 0b0000 => 0b1111n |= n >>> 16; ===> 0b1111 | 0b0000 => 0b1111得到：0b1111 => 15返回：return 15 + 1 => 16
面试题： **int n = cap - 1** 为什么要减去1呢？
如果cap 不减去1，即直接使n等于cap的话，int n = cap;我们继续用上边返回的cap => 16 传入tableSizeFor(int cap)：cap = 16n = 1616 => 0b10000 16 >>> 1 => 0b01000n |= n >>> 1; ===> 0b10000 | 0b01000 => 0b11000n |= n >>> 2; ===> 0b11000 | 0b00110 => 0b11110n |= n >>> 4; ===> 0b11110 | 0b00001 => 0b11111n |= n >>> 8; ===> 0b11111 | 0b00000 => 0b11111n |= n >>> 16; ===> 0b11111 | 0b00000 => 0b11111得到：0b11111 => 31返回 return 31 +1 => 32而实际情况是应该传入cap = 16 , n = cap -1 = 1515 => 0b1111n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;经过上面运算后得到：还是15返回结果：return 15 + 1 = 16
根据上面例子可以发现，如果 cap 已经是 2 的幂，又没有这个减 1 操作，则执行完后面的几条无符号操作之后，返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。
面试题： 最后为什么有个 n + 1 的操作呢？
一方面 位运算后，所得的十进制刚好加1就是2的n次幂，另一方面， 如果 n 这时为 0 了（经过了cap - 1后），则经过后面的几次无符号右移依然是 0，返回0是肯定不行的，所以最后返回n+1最终得到的 capacity 是1。
注意：容量最大也就是 32bit 的正数，因此最后 n |= n >>> 16;最多也就 32 个 1（但是这已经是负数了，在执行 tableSizeFor 之前，对 initialCapacity 做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY，会执行位移操作。所以这里面的位移操作之后，最大 30 个 1，不会大于等于 MAXIMUM_CAPACITY。30 个 1，加 1 后得 2 ^ 30）。
5.3 put
public V put(K key, V value) {// 调用hash(key)计算出key的hash值return putVal(hash(key), key, value, false, 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;/*1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。2）(tab = table) == null 表示将空的table赋值给tab，然后判断tab是否等于null，第一次肯定是null。3）(n = tab.length) == 0 表示将数组的长度0赋值给n，然后判断n是否等于0，n等于0，由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化，并将初始化好的数组长度赋值给n。4）执行完n = (tab = resize()).length，数组tab每个空间都是null。*/if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中。2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给结点p。3) (p = tab[i = (n - 1) & hash]) == null 判断结点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的结点放入该位置的桶中。小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置。*/if ((p = tab[i = (n - 1) & hash]) == null)// 创建一个新的结点存入到桶中tab[i] = newNode(hash, key, value, null);else {// 执行else说明tab[i]不等于null，表示这个位置已经有值了Node<K,V> e; K k;/*比较桶中第一个元素(数组中的结点)的hash值和key是否相等1）p.hash == hash ：p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个hash值是否相等。说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}而在Node类中具有成员变量hash用来记录着之前数据的hash值的。2）(k = p.key) == key ：p.key获取原来数据的key赋值给k key 表示后添加数据的key比较两个key的地址值是否相等。3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等。*/if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))/*说明：两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录*/e = p;// hash值不相等或者key不相等；判断p是否为红黑树结点else if (p instanceof TreeNode)// 放入树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 说明是链表结点else {/*1)如果是链表的话需要遍历到最后结点然后插入2)采用循环遍历的方式，判断链表中是否有重复的key*/for (int binCount = 0; ; ++binCount) {/*1)e = p.next 获取p的下一个元素赋值给e。2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键，将该键值对插入链表中。*/if ((e = p.next) == null) {/*1）创建一个新的结点插入到尾部p.next = newNode(hash, key, value, null);Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个结点肯定是null。2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素。*/p.next = newNode(hash, key, value, null);/*1)结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树。2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历结点的个数。值是0表示第一个结点，1表示第二个结点。。。。7表示第八个结点，加上数组中的的一个元素，元素个数是9。TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7如果binCount的值是7(加上数组中的的一个元素，元素个数是9)TREEIFY_THRESHOLD - 1也是7，此时转换红黑树。*/if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 转换为红黑树treeifyBin(tab, hash);// 跳出循环break;}/*执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等。*/if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循环/*要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了直接执行下面的if语句去替换去 if (e != null)*/break;/*说明新添加的元素和当前结点不相等，继续查找下一个结点。用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表*/p = e;}}/*表示在桶中找到key值、hash值与插入元素相等的结点也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值这里完成了put方法的修改功能*/if (e != null) {// 记录e的valueV oldValue = e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue == null)// 用新值替换旧值// e.value 表示旧值 value表示新值e.value = value;// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 修改记录次数++modCount;// 判断实际大小是否大于threshold阈值，如果超过则扩容if (++size > threshold)resize();// 插入后回调afterNodeInsertion(evict);return null;}
面试题：为什么HashMap的长度为2的n次幂
为了让均匀分布，采用取模的方式，当n为2的n次幂时，(n - 1) & hash等价于取模运算，且位运算的效率要高于取模运算
面试题：为什么 Map 桶中结点个数超过 8 才转为红黑树？
hashCode 算法下所有 桶 中结点的分布频率会遵循泊松分布，这时一个桶中链表长度超过 8 个元素的槪率非常小，权衡空间和时间复杂度，所以选择 8 这个数宇。
面试题：源码中binCount >= TREEIFY_THRESHOLD - 1才树化，此时链表中有几个元素？
9个，能走到该else分支下 证明原节点已经有值，即bitCount为0时，链表已经有1个元素，那么bitCount为7时，链表已经有8个元素，上一步
p.next = newNode(hash, key, value, null);
又插入了一个元素，所以此时为9个元素。
5.4 resize
/*** 为什么需要扩容呢？* 为了解决哈希冲突导致的链化影响查询效率问题，扩容会缓解该问题*/final Node<K,V>[] resize() {// oldTab：表示扩容前的哈希表数组Node<K,V>[] oldTab = table;// oldCap：表示扩容之前table数组长度// 如果当前哈希表数组等于null 长度返回0，否则返回当前哈希表数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;// oldThr：表示扩容之前的阀值(触发本次扩容的阈值) 默认是12(16*0.75)int oldThr = threshold;// newCap：扩容之后的table散列表数组长度// newThr: 扩容之后，下次再出发扩容的条件(新的扩容阈值)int newCap, newThr = 0;// 如果老的哈希表数组长度oldCap > 0// 如果该条件成立，说明hashMap 中的散列表数组已经初始化过了，是一次正常扩容// 开始计算扩容后的大小if (oldCap > 0) {// 扩容之前的table数组大小已经达到 最大阈值后，则不再扩容// 且设置扩容条件为：int的最大值if (oldCap >= MAXIMUM_CAPACITY) {// 修改阈值为int的最大值threshold = Integer.MAX_VALUE;return oldTab;}// 扩容之前的table数组大小没超过最大值，则扩充为原来的2倍// (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量// oldCap >= DEFAULT_INITIAL_CAPACITY 原哈希表数组长度大于等于数组初始化长度16// 如果oldCap 小于默认初始容量16，比如传入的默认容量为8，则不执行下面代码else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新的扩容阈值扩大一倍newThr = oldThr << 1; // double threshold}// 如果老的哈希表数组长度oldCap == 0// 说明hashMap中的散列表还没有初始化，这时候是null// 如果老阈值oldThr大于0 直接赋值/*以下三种情况会直接进入该判断：(即，这时候oldThr扩容阈值已存在)1.new HashMap(initCap,loadFactor);2.new HashMap(initCap);3.new HashMap(Map);// 这个传入的map中已经有数据*/else if (oldThr > 0) // 老阈值赋值给新的数组长度newCap = oldThr;// 如果老的哈希表数组长度oldCap == 0// 说明hashMap中的散列表还没有初始化，这时候是null// 此时，老扩容阈值oldThr == 0else { // 直接使用默认值newCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12}// 如果执行到这个位置新的扩容阈值newThr还没有得到赋值，则// 需要计算新的resize最大上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 将新的阀值newThr赋值给thresholdthreshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})// 创建新的散列表// newCap是新的数组长度---> 32Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 说明：hashMap本次扩容之前，table不为nullif (oldTab != null) {// 把每个bucket桶的数据都移动到新的散列表中// 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置for (int j = 0; j < oldCap; ++j) {// 当前node节点Node<K,V> e;// 说明：此时的当前桶位中有数据，但是数据具体是// 1.单个数据 、 2.还是链表 、 3.还是红黑树 并不能确定if ((e = oldTab[j]) != null) {// 原来的数据赋值为null 便于GC回收oldTab[j] = null;// 第一种情况：判断数组是否有下一个引用(是否是单个数据)if (e.next == null)// 没有下一个引用，说明不是链表，// 当前桶上只有单个数据的键值对，// 可以将数据直接放入新的散列表中// e.hash & (newCap - 1) 寻址公式得到的索引结果有两种：// 1.和原来旧散列表中的索引位置相同，// 2.原来旧散列表中的索引位置i + 旧容量oldCapnewTab[e.hash & (newCap - 1)] = e;//第二种情况：桶位已经形成红黑树else if (e instanceof TreeNode)// 说明是红黑树来处理冲突的，则调用相关方法把树分开// 红黑树这块，我会单独写一篇博客给大家详细分析一下// 红黑树相关可以先跳过((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 第三种情况：桶位已经形成链表else { // 采用链表处理冲突// 低位链表：// 扩容之后数组的下标位置，与当前数组的下标位置一致 时使用Node<K,V> loHead = null, loTail = null;// 高位链表：扩容之后数组的下标位置等于// 当前数组下标位置 + 扩容之前数组的长度oldCap 时使用Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 通过上述讲解的原理来计算结点的新位置do {// 原索引next = e.next;// 这里来判断如果等于true// e这个结点在resize之后不需要移动位置// 举例：// 假如hash1 -> ...... 0 1111// 假如oldCap=16 -> ...... 1 0000// e.hash & oldCap 结果为0，则// 扩容之后数组的下标位置j，与当前数组的下标位置一致// 使用低位链表if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 举例：// 假如hash2 -> ...... 1 1111// 假如oldCap=16 -> ...... 1 0000// e.hash & oldCap 结果不为0，则// 扩容之后数组的下标位置为：// 当前数组下标位置j + 扩容之前数组的长度oldCap// 使用高位链表else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将低位链表放到bucket桶里if (loTail != null) {loTail.next = null;// 索引位置=当前数组下标位置jnewTab[j] = loHead;}// 将高位链表放到bucket里if (hiTail != null) {hiTail.next = null;// 索引位置=当前数组下标位置j + 扩容之前数组的长度oldCapnewTab[j + oldCap] = hiHead;}}}}}// 返回新散列表return newTab;}
扩容机制：
- 什么时候才需要扩容？
当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时，就会进行数组扩容，loadFactor 的默认值是 0.75。 - HashMap 的扩容是什么？
进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。
HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以结点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置。
例如我们从 16 扩展为 32 时，具体的变化如下所示：
因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的标记范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化。
正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了。
5.5 remove
// remove方法的具体实现在removeNode方法中，所以我们重点看下removeNode方法// 根据key删除public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}// 根据key,value 删除@Overridepublic boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) != null;}
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {// 参数：// matchValue 当根据 key和value 删除的时候该参数为true// movable 可以先不用考虑这个参数// tab：引用当前haashMap中的散列表// p：当前node元素// n：当前散列表数组长度// index：表示寻址结果Node<K,V>[] tab; Node<K,V> p; int n, index;// 根据hash找到位置// 如果当前key映射到的桶不为空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {// 进入这个if判断内部，说明桶位是有数据的，需要进行查询操作，并且执行删除// node：通过查找得到的要删除的元素// e：表示当前node的下一个元素// k,v 键 值Node<K,V> node = null, e; K k; V v;// 第一种情况：当前桶位中的元素 即为我们要删除的元素// 如果桶上的结点就是要找的key，则将node指向该结点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 如果桶位中的头一个元素不是我们要找的元素，且桶位中的e = p.next不为null// 说明该桶位中的节点存在下一个节点else if ((e = p.next) != null) {// 说明：当前桶位，要么是 链表，要么是 红黑树// 第二种情况：判断桶位中是否已经形成了红黑树if (p instanceof TreeNode)// 说明是以红黑树来处理的冲突，则获取红黑树要删除的结点node = ((TreeNode<K,V>)p).getTreeNode(hash, key);// 第三种情况：桶位中已经形成链表else {// 判断是否以链表方式处理hash冲突// 是的话则通过遍历链表来寻找要删除的结点do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 比较找到的key的value和要删除的是否匹配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);// 第二种情况：如果桶位中是链表else if (node == p)// 链表删除tab[index] = node.next;// 如果桶位中else// 第三种情况：将当前元素p的下一个元素设置为 要删除元素的 下一个元素p.next = node.next;// 记录修改次数++modCount;// 变动的数量--size;afterNodeRemoval(node);return node;}}return null;}
5.6 get
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}
final Node<K,V> getNode(int hash, Object key) {// tab：引用当前hashMap的散列表// first：桶位中的头元素// e：临时node元素// n：table数组的长度Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 如果哈希表不为空，并且key对应的桶不为空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {/*判断数组元素是否相等根据索引的位置检查第一个元素注意：总是检查第一个元素*/// 第一种情况：定位出来的桶位元素 就是我们要get的数据if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 桶位第一个元素不是我们要找的目标元素，且first.next不为null// 说明当前桶位不止一个元素，可能是链表，也可能是红黑树if ((e = first.next) != null) {// 第二种情况：桶位已经升级成了红黑树// 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点if (first instanceof TreeNode)// 调用与树相关的方法得到目标元素return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 第三种情况：桶位已经形成链表do {// 不是红黑树的话，那就是链表结构了// 通过循环的方法判断链表中是否存在该keyif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 如果没找到返回nullreturn null;}
6. 面试补充
面试题 头插尾插：
1.8 之前为头插，1.8之后为尾插
头插在并发环境下会导致死循环问题，参考该文章https://blog.csdn.net/maohoo/article/details/81531925
此处描述作为记录：
Entry<K,V> next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;
线程2 在 e -> a next -> b 时时间片用完
线程1 在遍历c时时间片用完，此时newTable[i] 还是 b -> a （b.next = a）
那么在切换为2后 e.next 被赋值为b，即a.next = b，由于在线程1中 b.next = a 此时节点ab相互引用，如果get就会触发死循环。
1.8全部赋值给next，变成了尾插。
参考 https://blog.csdn.net/weixin_45097458/article/details/103179093
JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插) 所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑JDK7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得
但是不管是头插还是尾插都可能会有数据覆盖或丢失的问题，所以多线程环境建议使用ConcurrentHashMap
面试题 为什么重写equals就必须重写hashCode?
HashMap 主要是通过hashcode来计算索引的，如果不重写会导致计算的索引有问题。
面试题 为什么不选择二叉查找树而选择红黑树?
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持”平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
面试题 红黑树的特点?
1、每个节点非红即黑
2、根节点总是黑色的
3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
4、每个叶子节点都是黑色的空节点(NIL节点)
5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
对红黑树的理解后续会新开篇章，目前我也不太熟
7. 附录
类注释：
跳转回第二节
Map接口的基于哈希表的实现。 此实现提供所有可选的映射操作，并允许空值和空键。（ HashMap类大致等同于Hashtable ，除了它是非同步的并且允许空值。）该类不保证映射的顺序；特别是，它不保证订单会随着时间的推移保持不变。此实现为基本操作（ get和put ）提供恒定时间性能，假设散列函数在存储桶中正确分散元素。迭代集合视图需要的时间与HashMap实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低），这一点非常重要。HashMap的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量就是哈希表创建时的容量。负载因子是衡量哈希表在其容量自动增加之前允许达到多满的指标。当哈希表中的条目数超过负载因子和当前容量的乘积时，重新哈希表（即重建内部数据结构），使哈希表具有大约两倍的桶数。作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了很好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put ）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。如果要在一个HashMap实例中存储许多映射，则创建具有足够大容量的映射将允许更有效地存储映射，而不是让它根据需要执行自动重新散列以增加表。请注意，使用具有相同hashCode()多个键是降低任何哈希表性能的可靠方法。为了改善影响，当键是Comparable ，此类可以使用键之间的比较顺序来帮助打破联系。请注意，此实现不是同步的。 如果多个线程并发访问一个散列映射，并且至少有一个线程在结构上修改了映射，则必须在外部进行同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常是通过同步一些自然封装映射的对象来完成的.如果不存在这样的对象，则应使用Collections.synchronizedMap方法“包装”地图。这最好在创建时完成，以防止对地图的意外不同步访问：Map m = Collections.synchronizedMap(new HashMap(...));此类的所有“集合视图方法”返回的迭代器都是快速失败的：如果在迭代器创建后的任何时间对映射进行结构修改，除了通过迭代器自己的remove方法外，迭代器将抛出ConcurrentModificationException .因此，面对并发修改，迭代器快速而干净地失败，而不是在未来不确定的时间冒着任意、非确定性行为的风险。请注意，无法保证迭代器的快速失败行为，因为一般而言，在存在非同步并发修改的情况下不可能做出任何硬保证。 快速失败的迭代器会尽最大努力抛出ConcurrentModificationException 。因此，编写一个依赖此异常来确保其正确性的程序是错误的：迭代器的快速失败行为应该仅用于检测错误。此类是Java Collections Framework的成员。
实现说明。该映射通常用作binned（bucketed）哈希表，但是当bins变得太大时，它们会被转换为 TreeNodes 的bins，每个分箱的结构类似于 java.util.TreeMap 中的分箱。大多数方法尝试使用普通 bins，但在适用时中继到 TreeNode 方法（简单地通过检查节点的实例）。TreeNodes 的 bins 可以像任何其他 bins 一样被遍历和使用，但另外支持在人口过多时更快的查找。然而，由于绝大多数正常使用的 bin 并没有过度填充，因此在 table 方法的过程中检查树 bin 的存在可能会延迟。Tree bins（即元素都是 TreeNode 的bins）主要按 hashCode 排序，但在相同的情况下，即如果两个元素是相同的“class C implements Comparable<C>”，则根据它们的 compareTo 方法排序。（我们通过反射保守地检查泛型类型以验证这一点——请参阅方法 compareClassFor）。当键具有不同的散列或可排序时，Tree bins 的增加的复杂性值得提供最坏情况的 O(log n) 操作，因此，在 hashCode() 方法返回的值很差的意外或恶意使用下，性能会优雅地降低分布式，以及其中许多键共享一个 hashCode 的那些，只要它们也是 Comparable 的。（如果这些都不适用，与不采取预防措施相比，我们可能会在时间和空间上浪费大约两倍。但唯一已知的情况源于糟糕的用户编程实践，这些实践已经很慢，这几乎没有什么区别。）因为 TreeNodes大约是常规节点大小的两倍，我们仅在 bins 包含足够的节点以保证使用时才使用它们（请参阅 TREEIFY_THRESHOLD）。当它们变得太小（由于移除或调整大小）时，它们会被转换回plain bins。在使用分布良好的用户哈希码的情况下，很少使用树箱。理想情况下，在随机 hashCodes 下，bins 中节点的频率遵循泊松分布(http:en.wikipedia.orgwikiPoisson_distribution)，对于默认调整大小阈值 0.75，参数平均约为 0.5，尽管由于调整大小粒度而存在较大差异.忽略方差，列表大小 k 的预期出现次数为 (exp(-0.5) pow(0.5, k) factorial(k))。所述第一值是：0：0.606530661：0.303265332：0.075816333：0.012636064：0.001579525：0.000157956：0.000013167：0.000000948：0.00000006更多：小于1千万树仓的根是通常它的第一节点。然而，有时（目前仅在 Iterator.remove 上），根可能在别处，但可以通过父链接（方法 TreeNode.root()）恢复。所有适用的内部方法都接受一个哈希码作为参数（通常由公共方法提供），允许它们相互调用而无需重新计算用户哈希码。大多数内部方法也接受一个“tab”参数，它通常是当前表，但在调整大小或转换时可能是新的或旧的。当 bin 列表被树化、拆分或未树化时，我们将它们保持在相同的相对访问遍历顺序（即字段 Node.next）中，以更好地保留局部性，并稍微简化调用iterator.remove 的拆分和遍历的处理。在插入时使用比较器时，为了在重新平衡之间保持总排序（或尽可能接近此处的要求），我们将类和 identityHashCodes 作为决胜局进行比较。由于子类 LinkedHashMap 的存在，普通模式与树模式之间的使用和转换变得复杂。请参阅下文，了解定义为在插入、删除和访问时调用的钩子方法，这些方法允许 LinkedHashMap 内部以其他方式保持独立于这些机制。（这还需要将映射实例传递给一些可能创建新节点的实用方法。）类似于并发编程的基于 SSA 的编码风格有助于避免在所有扭曲指针操作中出现别名错误。
若有收获，就点个赞吧
0 人点赞
