- 联系方式：1761430646@qq.com
- 菜鸟摸索，有误勿喷，烦请联系
1. HashMap的存储结构
-
在JDK1.7及以前，HashMap使用数组（也叫桶）+链表的方式实现的，也就是采用链表法处理冲突
-
而在hash值相等的元素比较多，集中在某条链表时，此链表的长度特别特别长，那么此时通过key值依次查询的效率呈直线下降，特别低，依次，在JDK1.8,重写了resize()方法，把它设计为当链表长度超过某个特定的阈值后，就将链表转化为红黑树结构
- 红黑树不太懂，这幅图的红黑树可能有错
2. 内置变量
2.1 初始容量–DEFAULT_INITIAL_CAPACITY
- HashMap默认的初始容量，1左移4位，即为2^4 = 16，必须为2的n次幂
2.2 最大容量–MAXIMUM_CAPACITY
-
-
表示最大的容量，容量必须是2的n次幂，用int类型，所以最大为2^30，这是为了方便求下标，后面会具体讲为什么
2.3 默认加载因子–DEFAULT_LOAD_FACTOR
-
-
含义：乘以数组容量得到的值，用来表示当元素个数达到多少时，需要扩容
-
加载因子与扩容机制有关，具体的扩容后面会讲
-
HashMap的第一次扩容就是在DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12 时进行
-
默认加载因子取0.75是为了时间和空间的权衡，取小了空间使用率大大降低，而取大了会增大hash冲突的概率，影响查询效率
2.4 树化阈值–TREEIFY_THRESHOLD
-
-
当某条链表的长度过长时，超过这个阈值8，就会将其转化为红黑树–JDK1.8特性
2.5 链表阈值–UNTREEIFY_THRESHOLD
-
-
当红黑树上的元素个数减少至<6个时，红黑树将退化为链表
2.6 树化最小容量–MIN_TREEIFY_CAPACITY
-
-
链表转化为红黑树，除了要求有树化阈值的限制，还有另外一个限制，就是需要数组容量至少达到64后才会树化
-
这是为了避免数组扩容和数组阈值之间的冲突，优先进行扩容，而不是树化
2.7 存放所有结点的数组–table
-
-
-
这是底层数据结构实现中的数组
-
存放所有Node结点链表的数组
2.8 存放所有键值对的集合-entrySet
2.9 总键值对数量–size
- 表示当前HashMap总共存放的键值对数量
2.10 修改次数–modCount
- 表示修改次数，每次结构改变时，都会自增，用于做并发修改HashMap时的快速失败-fail-fast机制，这是一种错误检测机制
- 不太懂
2.11 扩容阈值–threshold
- 表示数组扩容的阈值，也就是 初始容量 * 负载因子的值，当元素个数超过此数时，则进行数组扩容
2.12 加载因子–loadFactor
- 此HashMap实际的加载因子，表示的是HashMap中的密集程度
3. 内部类
3.1 Node–存放普通单向链表节点类
-
static class Node<K,V> implements Map.Entry<K,V> { // 这个hash值是K通过hashCode()方法的返回值再进行高低16位混合运算得到的，后面会讲具体原理，这里知道并不是单纯通 过K的hashCode()赋值即可 final int hash; final K key; V value; 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; } } -
HashMap中单向链表的每个键值对都是用这个形式来表现的
3.2 TreeNode–转化为红黑树后的节点类
-
/** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } -
HashMap中单向链表转化为红黑树结构后，使用这个TreeNode来存储表示键值对
4. 构造函数
4.1 HashMap()–默认无参构造函数
-
/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } -
生成一个空的HashMap，初始容量为默认初始容量16，加载因子为默认加载因子0.75f
4.2 HashMap(int initialCapacity)–可指定初始容量的有参构造
-
/** * 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. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } -
会调用下面的带两参的构造函数，加载因子为默认的加载因子0.75f
-
注意：这里指定的容量并不一定是实际的容量，实际的容量是你传入参数值的最接近且>=参数值的最小的2的n次幂，后面会讲具体
4.3 HashMap(int initialCapacity, float loadFactor)–可指定初始容量和加载因子的有参构造
-
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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或者是一个不是数字的数字的话，不合理，抛异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 设置加载因子 this.loadFactor = loadFactor; // 设置HashMap的阈值， // tableSizeFor方法是计算理应的数组容量长度，把我们指定容量改为一个大于等于它的最小的2的n次幂，,比如传入14，返回 16 // 注意不是直接赋值给capacity，即保证数组容量总是2的n次幂，而是赋值给threshold // 后面会讲为什么赋值给threshold，而不是capacity this.threshold = tableSizeFor(initialCapacity); } -
指定初始容量和加载因子，会对这两个参数做有效检验，并且指定的初始容量并不一定是实际给的容量
-
注意：这里的加载因子可以是>1的
4.2 HashMap(Map<? extends K, ? extends V> m)–可传入一个已有的Map
-
/** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { // Map是一个接口，里面不含有加载因子属性，所以新构建的HashMap集合的加载因子使用默认加载因子 this.loadFactor = DEFAULT_LOAD_FACTOR; // 一个将参数集合的所有元素放入新的HashMap集合的方法，就是具体怎么放进新的HashMap中 putMapEntries(m, false); } -
根据一个已有的Map，将其中所有的键值对元素放进一个新的HashMap集合中
5. 重要方法
5.1 hash(Object key)
-
/** * 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. */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } -
作用：给定一个对象，为空返回0，不为空的话返回其哈希码与右移16位的本身做异或运算的值，即对哈希码高低16位进行混合运算
-
提问一：为什么要对哈希码hashCode进行高低16位混合运算，而不是直接返回？
-
答：进行高低16位混合是为了尽量保留高16位的特征，减少hash冲突的概率
-
需要结合i = (n - 1) & hash这一段运算来理解
-
在put方法中，i = (n - 1) & hash是用来计算当前键值对所应该放在数组哪个位置的索引，其中n为数组长度（一定为2的k次幂），hash值是键作为参数传给hash()方法返回的值
-
我们知道，对于给定一个固定长度的数组，以及一个数，在寻找此数在数组中的下标位置时，直接使用模运算即可，比如数组长度为16（HashMap的数组长度一定为2的k次幂，为了方便演示，这里也假设数组的长度为2的k次幂），数为18，直接利用18%16 = 2 即能求得18应该放在索引为2的位置处
-
而i = (n - 1) & hash也可以求，此时n为16，hash为18
-
16 - 1的二进制: 0000 0000 0000 0000 1111 18的二进制: 0000 0000 0000 0001 0010 &运算后的二进制: 0000 0000 0000 0000 0010 十进制也即为2 为什么可以这样求？ 1. 我们知道，n是数组的长度，即一定为2的k次幂，那么它的二进制一定形如如同如下表示 0000 0000 0010 0000 0000 2. 也就是在其二进制上一定总是有一位为1，其他全为0 3. 所以，当n-1后，其二进制一定形如如同如下表示 0000 0000 0001 1111 1111 4. 也就是高位全部是0，低位部分全部为1 5. 那么它不管与任何数做&运算，其取值范围一定在0 ~ n-1这个区间内 * &运算的逻辑为俩1为1，否则为0 A: 0000 0000 0001 1111 1111 B: xxxx xxxx xxxx xxxx xxxx * A的高位部分全部为0，那么对应B的高位部分，不管是0还是1，结果中对应的高位部分一定全为0 0000 0000 000x xxxx xxxx * 那么结果的最终取值决定于B的低位部分 * 取最大值时无非B的低位部分全为1，结果也即为n - 1 * 取最小值时无非B的低位部分全为0，结果也即为0 * 所以&运算后取值的取值范围为0 ~ n-1 -
所以i = (n - 1) & hash可以求得该key在数组的下标，所以这种求法必须要求n为2的n次幂
-
至于为什么不直接采用模运算，是因为位运算的速度比较快
-
回归问题，我们知道hash()方法返回的值是给键值对找对应数组下标处的
-
那么，当我们有两个对象A,B，其中A的hashCode值为0110 1101 0110 1111 0110 0110 1110 0010 1000，B的hashCode值为0100 0101 1110 1011 0110 0110 0010 1000,也就是这两个对象的hashCode值的相似度非常高，低位部分都是0010 10000
-
A: 0110 1101 0110 1111 0110 0110 1110 0010 1000 B: 0100 0101 1110 1011 0110 0110 0101 0010 1000 n-1: 0000 0000 0000 0000 0000 0000 0000 0000 1111 假设n为16 1. 如果hash方法直接返回hashCode值的话，通过i = (n - 1) & hash获得下标 * 那么我们发现A,B求的下标都是1000，也就8 * 也就是在存放的时候产生了hash冲突 * A,B二进制的前面高位部分的特征就没有用到 2. 如果A,B进行高低16位混合运算后，那么A,B就没有产生了hash冲突 -
当然，在实际中就算进行了高低16位混合运算，那么求下标的时候也很有可能产生hash冲突
-
而不直接返回对象的hashCode值的原因是产生hash冲突的概率会比做高低16位混合运算后的值大上很多，其哈希码的高位部分全部丢失，没有使用到–数学证明不会。。。
-
两个数尽管差别很大，但是只要低位部分相似度很高，并且HashMap如果初始容量很小，后面进行扩充也不会扩充的很大很大，那么低位部分相同的数非常非常容易发生hash冲突
-
-
提问二：做高低16位混合运算，为什么要用 ^ 运算，不用& 或 | ？
-
答：^ 运算结果的比例可以达到1:1的平衡状态
-
5.2 putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
-
/** * Implements Map.putAll and Map constructor. * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { // 获取参数Map集合的大小，即键值对数量 int s = m.size(); // 如果参数Map不是空&&存在存放键值对 if (s > 0) { // 如果当前Map的数组为null，即还未初始化Map if (table == null) { // pre-size // 计算对于参数Map，要用多大容量的HashMap才能装进来 // 比如参数Map中键值对数量为12，那么在新的Map集合中，采用默认的加载因子 // 12/0.75+1为新HashMap中数组的大小，+1很重要，如果不加1，那么12/0.75为16，但12已经是16的0.75了,此 // 时是已达到扩容阈值，是需要扩容的，所以要加+1为17，构造容量为17的数组，能够正常存放数量为12的键值 float ft = ((float)s / loadFactor) + 1.0F; // 如果新数组容量大于最大容量，则设置新数组容量为最大容量，否则对新数组容量取整 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 由于数组容量必须是2的n次幂，所以要调用tableSizeFor()方法，其作用为返回把参数值修改为一个>=原值的最小 // 的2的n次幂的值，比如传入14或16，返回的都是16,后面会具体讲怎么求 // 注意：返回的值是赋值给扩容阈值，而不是赋值给加载因子，这点很重要，后面会用到 if (t > threshold) threshold = tableSizeFor(t); } // 如果当前HashMap集合已经实例化了，则判断参数Map集合大小是否大于当前HashMap集合的扩容阈值，如果大于，则需要 // 扩容，resize()方法时具体进行扩容的，后面会讲 else if (s > threshold) resize(); // 上面做的就是实例化当前HashMap并且扩容，让它的容量可以存放你参数集合的所有元素，并且不会达到扩容阈值 // 此时当前的HashMap集合已经实例化了，并且参数Map的键值对数量是小于扩容阈值的，则遍历参数Map元素，重新映射在 // 当前的HashMap集合上 // putVal(hash(key), key, value, false, evict)是具体放键值对入HashMap的操作，后面会讲 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } -
作用：在带Map的构造函数中调用此方法，将参数Map中所有键值对映射在新的Map上
5.3 tableSizeFor(int cap)
-
/** * Returns a power of two size for the given target capacity. */ 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; } -
作用：返回一个给定参数的最接近(比原参数要大)的2的n次幂的值，比如传入13或16，返回的都是16
-
具体实现：
-
假设参数n为13，先忽略 n = cap - 1这个让参数值先减一的操作
-
也就进行了参数n，13 进行了 n |= n >>> 1;n |= n >>> 2;n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;的操作
-
我们的传入的参数n都可以转化成二进制的形式
-
比如我们传入13，其二进制是
0000 0000 0000 0000 0000 0000 0000 1101
-
-
而我们的目的是获取最接近当前值的(比原参数13要大)2的n次幂的值，就是其二进制中只能有一个1
-
对于13，则目标为16，即2^4，其二进制是
0000 0000 0000 0000 0000 0000 0001 0000
-
-
这样我们会发现一个规律，即在原数n的最高位1往左移动一位，然后其他为全部化为0即可
-
那么有没有一种办法可以做的呢？
-
有的，如果我们把原数n的二进制在最高位1极其右边部分全部化为1，其他位为0，最终在此中间数基础上加上1即为所求
-
具体如何将原数转化为中间数，简单来说我们可以理解为任何给出的在取值范围的数，转化为二进制后都有一个最高位1，而其后边部分可能含有1的位可以把它们都成0来处理，因为等下实际处理其实并不影响，后面会解释为什么不会影响。我们拿原数n与往右移1位的n做逻辑或处理，结果又赋予给n，这样循环，分别与往右移动1,2,4,8,16位的n做逻辑或处理，最终会得到中间数
-
n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; -
为什么可以这样做？
- 第一次处理
-
第一次处理后，获得的n则保证了前面有二个1，这样后面进行第二次处理后，获得的n前面就有了4个1，以此类推，1+2+4+8+16=31，即我们可以弄出31个1出来，除了最高位的符号位外都是1。
-
一个概念：前导1—自己定义的，实际中不知道存不存在
- 对于一个二进制的数n，第一次认为其最高位的1是默认是前导1，最高位后面可能存在的1不理
- 第二次认为其最高位的前面两个1默认是前导1–连续的，最高位后面可能存在的1不理
- 以此类推
- 注意n的值是可变的
-
-
获得中间数后，我们直接让其加1即为目标值，即获取到当前传入值的最接近（比传入值大）得一个2的n次幂的值
-
补充
-
为什么我们假设n的最高位1后面都是0，那些最高位1后面可能出现1的数不会对运算造成影响吗？
- 不会，因为我们的运算实际上就是每次翻倍填充在原来n的前导1的个数，即前导1有1个，运算后就让它变成2个，前导1有2个，运算后就让它变成4个，直至不能填充为止，由于我们不知道在原数n的具体大小，不知道要填充多少个，多少次，所以我们会让其一直到与16做运算
- 由于逻辑或的运算逻辑为有1为1，否则为0，就算原数n的最高位1后面还有零零散散的1存在，但每次运算我们的关注点在于前导1的翻倍填充，再加上逻辑或的运算规则，并无影响,这里用12做例子
- 假设n的存在只是为了理解每次做运算都是为了翻倍填充前导1，所以只要理解了运算的性质后就可以忘记假设n的存在，这只是辅助理解罢了，不要认为实际运算就是真的弄个假设n出来，把最高位1的后面全部化为0，
-
让参数减一在做位移异或运算为什么？
- 这是一种特殊情况，比如我们传入8，即最小的2的n次幂的值就是它本本身
- 如果我们不让它先减去1的话，经过上述运算，则获得的最终结果就是为16了，明显不是正确答案，自己可以验证
- 所以为了防止其本身就是目标值（答案）这种特殊情况，我们会让参数先减1（为7）再去运算，这样获得的最终答案明显是8
- 这样是不会对其他非特殊情况的最终答案造成影响的，比如不管是15，还是14，最终求得目标值都是16
-
对于边界值1和2^31 -1，都可以求得正确目标值，自己可以推算一遍
-
比如对于13，其实做了一次位移逻辑或运算后就已经填充完了所有可以填充的前导1，后面再做运算时，是不会再改变n的值的
-
-
-
5.4 put(K key, V value)
-
/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } -
作用：我们通常使用的放入键值对方法，具体操作会调用多参数的重载方法putVal(hash(key), key, value, false, true)来实施
5.5 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
-
/** * Implements Map.put and related methods. * * @param hash hash for key * 这个参数hash是将key作为参数调用hash()方法--进行其hashCode高低16位混合运算返回的值，后面主要用来计算key理应放入的 * 数组下标位置，所以不同对象A,B其hash值可能相同 * * @param key the key * @param value the value to put * * @param onlyIfAbsent if true, don't change existing value * onlyIfAbsent如果为true，表明发生了键重复时不能修改已经存在的值，在这里我们传入false， * * @param evict if false, the table is in creation mode. * 这个evit只在最后得afterNodeInsertion(boolean evict)中用的到，而在HashMap的afterNodeInsertion(boolean * evict)中是一个空实现，在其他集合中才会有具体实现，这里有这个参数只是为了统一集合结构（个人理解）所以一句话，不鸟它 * * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果当前HashMap的数组未实例化或者其容量为0，则首先进行扩容 // 这种情况时发生在当我们new了一个HashMap后，第一次存放键值对进来时会执行这里 if ((tab = table) == null || (n = tab.length) == 0) // 调用resize()方法进行扩容，后面会讲 n = (tab = resize()).length; // i = (n - 1) & hash 是具体计算当前key在数组中的下标位置的，之前在讲hash()的时候讲过具体原理 // 判断对应下标位置处是否为null // 如果是，说明当前下标位置处之前根本没有存放过元素，直接将键值对构成新的结点链接在此下标位置处，具体存放操作 // 已完成 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 如果不是，说明当前下标位置处已经存放元素 // 这个e是记录当发生键重复时的那个原本的结点，执行完后如果为null则说明没有发生键重复 Node<K,V> e; K k; // 不管怎样，总要判断第一个元素是否就发生了键重复 // 如果是，那么第一个元素就发生了键重复，用e记录那个发生键重复的结点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 此时说明第一个元素没有发生键重复，那么此下标处可能会含有一条链表或者是一棵红黑树 // 如果是红黑树结构的，就执行下面红黑树结构的存放方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 走到这里说明第一个元素没有发生键重复，并且此下标位置处存放的是一条链表 // 总体思想： 遍历链表，如果找到键重复的结点，就用e记录 // 如果没有找到键重复的结点，将传入的键值对构造成新节点使用尾插法链接到链表末尾 for (int binCount = 0; ; ++binCount) { // 遍历到了末尾，没有找到键重复的点，那么直接将传入的键值对构造成新的结点链接到链表末尾处。 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 如果当前链表长度>树化阈值，则调用方法将链表转化为红黑树结构 // 以树化阈值取8为例，binCount至少为7才行，为7的话那么原本链表就有0 -- 7 就是8个，再加上新加 // 入的结点，就是9个，这时候就>树化阈值了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 发生键重复，用e记录键重复的点，后面会对键重复做统一处理 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 这时候有两种情况： // 1、说明了发生键重复的情况，直接用新值取代旧值，这个很好理解 // 2、说明e是插入链表或者红黑树成功后的新节点 ---不是很理解，都构造好节点了为什么还要多此一举，为了代码统 // 一性？ // 上面中在红黑树差插入节点以及在链表中插入节点都有赋值e为新节点 if (e != null) { // existing mapping for key // 发生键重复时新值替换旧值 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 看方法名可知，这是在node被访问后需要做的操作，对于HashMap，这里是一个空实现 // 只有LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，HashMap不提供排序功能 afterNodeAccess(e); // 返回旧值 return oldValue; } } // fail-fast机制 // 记录修改结构的次数,这在迭代器迭代时不能修改HashMap中有很大作用，具体还未详细了解过 ++modCount; // 如果当前HashMap中键值对的个数超过阈值，则扩容 if (++size > threshold) resize(); // 同样的空实现 afterNodeInsertion(evict); return null; } -
作用：HashMap中具体的将键值对进行映射操作
-
不懂：
- 如果没有发生键重复，直接构造新节点链接，最后为什么还要进入if(e != null)这个？
- modCount的具体使用不怎么懂
-
注意：JDK1.7采用头插法，由线程问题可能导致链表死循环，JDK1.8采用尾插法
-
图解：正常逻辑处理，实际代码实现有点不太一样
5.6 get(Object key)
-
/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { Node<K,V> e; // 调用具体的查找结点方法，以key的hash值和key本身作为参数传进去 return (e = getNode(hash(key), key)) == null ? null : e.value; } -
作用：查找key所映射的值，如果不存在这对映射关系，则返回Null，当然，返回Null不一定是不存在此映射关系，也有可能此
key所映射的value本身就为Null，所以HashMap中是可以存放value为Null的–方法注解中也提到了这一点
5.7 getNode(int hash, Object key)
-
/** * Implements Map.get and related methods. * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 首先要确保数组不为空且长度>0，即已经实例化，并且计算key的hash值所对应的数组下标处是至少存在一个元素的，不存在元 // 素的话肯定就是没有这个key的映射关系 if ((tab = table) != null && (n = tab.length) > 0 && (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); // 如果是链表的话，则向后遍历，直到找到或者遍历到链表末尾为止 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 没有找到 return null; } -
作用：具体的在HashMap中查找结点的步骤
-
不懂：
- 判断是否找到结点时为什么要判断hash值先相等？直接判断key是否相等不就可以了么？
- 判断是否找到结点时的(key != null && key.equals(k)) 是干嘛用的？
5.8 resize()
-
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 取旧数组的容量，如果还未实例化就取0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 老数组的扩容阈值 int oldThr = threshold; // 初始化新数组的容量以及扩容阈值 int newCap, newThr = 0; // 如果老数组的容量>0，那么之前肯定扩容过(即调用过此方法-resize())一次，所以才会导致旧数组容量不为0 // 为什么？ // * 在之前的四个构造函数，只有指定了初始容量的构造方法才调用过此方法 // * 但是，其返回值赋给的是扩容阈值threshold，可以回看一下源代码 // * 我们在这之前，根本没有看到过哪里是有给capacit赋值的 // * 所以，第一次调用此方法时，旧数组容量OldCap一定为0，现在>0，说明之前扩容过一次 if (oldCap > 0) { // 容量达到最大容量值，扩容不了，只能改扩容阈值为int能装的下的最大值Integer.MAX_VALUE if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新数组的容量和扩容阈值都扩大原来的2倍 // * 扩容后的容量要小于最大容量？？ // * 因为已经扩容过一次，所以老数组容量oldCap至少为8，但为什么多加一个判断，正常来说不都是>=的么？ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 到这里说明oldCap<=0，并且oldThr(threshold)>0，这是map初始化的时候，第一次调用resize()方法 // 这里是只有使用了指定容量的构造方法才会走这里，指定容量后，会把tableSizeFor方法得到的一个2的n次幂赋给扩容阈值 // oldThr，所以此时的oldThr才会>0 else if (oldThr > 0) // initial capacity was placed in threshold // 此时的扩容阈值为2的n次幂，含义为目标数组的容量，而不是容量*加载因子的含义--这里比较特殊 // 新数组的容量就是扩容阈值，至于新数组的扩容阈值newThr，此时为0，后面会做同一赋值 newCap = oldThr; // 这里是oldCap<=0，并且oldThr<=0，也就是调用无参构造函数时，第一次扩容才会走这里 // 所以新数组的容量，加载因子，扩容阈值都采用默认的 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 这里是处理上述oldThr>0的情况，只有那里的新扩容阈值newThr还未赋值，即为0 // 新扩容阈值 = 新数组容量 * 加载因子 = newCap * loadFactor if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 赋予threshol扩容后正确的值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 赋予table扩容后正确的值 table = newTab; // 如果原来的数组不为空，那么我们需要将原来数组中的所有元素重新转移分配到新的数组中取 // 如果是上述的第二，三种情况，也就第一次调用resize（）扩容，那么数组中肯定是空的，没有元素，也就不需要重新分 // 配元素 if (oldTab != null) { // 遍历就数组 // 一个很重要的知识点： // * 如果A在原数组中的索引为x，那么A在新数组中的索引要么为x，要么为x+旧数组容量 = x + oldCap // * 后面会讲为什么，这里先记住这个结论 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 旧数组对应下标处是存在元素的，就获取 if ((e = oldTab[j]) != null) { // 释放原数组对应下标处的指针--我把它理解为垃圾回收 oldTab[j] = null; // e.next 为null，即这个对应下标处只含一个元素---不知道为什么官网很喜欢总是检查第一个元素的情况 if (e.next == null) // 计算这个元素在新数组中的下标 newTab[e.hash & (newCap - 1)] = e; // 此时说明对应下标处存在多个元素 // 这多个元素如果是属于红黑树结构，就拆分红黑树，必要时退化为链表(其中有些元素在新数组的下标可能与在 // 原数组的下标不一样,此红黑树的个数可能会减少) else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 此时说明对应下标处存放的是链表结构的多个元素 // * 所以要遍历此链表，获取每个元素，计算它在新数组的下标 // * 之前说过某个元素的新下标要么不变，要么就是在原来的基础上 + 旧数组的容量 // * 不过这里的做法跟我们想的不太一样 // * 它是通过旧数组的链表A，先构造处新数组中的两条链表B,C，再把这两条链表拼接到对应新数组的下标处 // * 链表B对应的下标跟链表A对应的下标相同，链表C对应的下标为链表B对应的下标 + 旧数组的容量 else { // preserve order // loHead和loTail分别代表链表旧位置的头尾结点--链表B Node<K,V> loHead = null, loTail = null; // hiHead和hiTail分别代表链表移动到新位置的头尾结点--链表C Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { // e为当前结点 next = e.next; // 如果当前结点的hash与旧数组容量做&运算后为0，即此节点在新数组的对应下标还是不变，即为在旧 // 数组的下标，后面会讲为什么，先记住即可 if ((e.hash & oldCap) == 0) { // 拼接到链表B上 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 此结点在新数组的下标是在原本旧数组的下标 + 旧数组容量 else { // 把节点拼接到链表C上 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 链表B整条拼接到新数组上 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 链表C整条拼接到新数组上 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } // 把扩容后的新数组返回 return newTab; } -
作用：扩容机制
-
整个扩容流程可以分成两部分：
-
数组的容量和扩容阈值扩容（变成原来的2倍）
-
图解：具体实现代码不太一样
-
将旧数组中的所有元素重新装到新数组中去
-
图解：
-
-
提问一：为什么元素在新数组的下标要么就是在旧数组中的下标不变，要么就是 旧数组中的下标+ 旧数组容量？
-
提问二：在提问一基础上，那么计算索引的时候为什么不是hash值&新数组容量，而是hash&旧数组容量？
- 原理其实是一样的，以旧数组容量为16为例，关键点在于key的hash值的倒数第五位，若是0，则结果下标对应倒数第五位为0，否则为1
- 而旧数组容量的1恰好就是倒数第5位，所以通过旧数组容量与hash值做&运算，除了倒数第五位有可能为1，其他位全为0
- 当运算结果为0的话，也就说明了hash值的倒数第五位也为0.
- 以此类推
6. 总结
-
HashMap不是一个线程安全的容器，不安全性体现在多线程并发对HashMap进行put操作
- 如果有两个线程A和B，首先A希望插入一个键值对到HashMap中去，在决定好数组下标的位置进行put时，此时A的时间片正好用完，然后线程B运行，线程B运行后执行跟A一样的操作，只不过B是成功插入键值对进去，如果A和B插入的位置是一样的话，那么线程A继续执行时会把B插入的结点给覆盖掉，造成了数据不一致性问题
-
在存放键值对时，JDK1.7及以上采用头插法，JDK1.8后采用尾插法
-
一个点：之所以可以判断得到的结点Noode是否属于TreeNode类型
- 是因为
- instanceof：当对象是右边类或子类所创建的对象时，返回true，否则返回false
- null用instanceof跟任何类型比较时都是false
-
HashMap可以存放键值为null的键值对
-
在具体的存放方法putVal()中，并没有对key和value是否为null做判断加限制，也就是默认可以为null
-
当key为null时，调用hash()方法返回的值为0，所以key为null的键值对永远只会存放在数组索引为0的地方
-
- 同一个HashMap中，key为null的键值对只有一个（不管value是不是null）
- 同一个HashMap中，value为null但key各个不相同的键值对可以有多个
-
-
拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一致使用红黑树？
- 之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在比较特殊的情况下回变成一条线性结构(这就跟原来的链表结构一样了，造成很深的问题)，遍历查找会非常慢。
- 而红黑树在插入新数据后可能需要通过左旋，右旋，变色这些操作来保持平衡，引入红黑树就是为了查找数据块，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而很慢
- 引用程序员乔戈里
-
容量为什么一定要2的n次幂：
-
使用位运算计算元素所在数组的下标效率比较高
-
在扩充的时候，原本的所有元素都要重新进行计算所在新桶位置的运算，并根据结果移动到对应的新位置–这也叫重哈希操作
-
先讲移动方式，对于某个桶上的链表A-B-C-D，扩充的时候，遍历此表的每一个元素，移动到扩充后的桶中有两种方式可以采取
-
第一种：拿到当前元素A，计算它在新桶中的下标位置为x，然后进行具体的移动操作，移动完元素A后再开始下一个元素B的移动。 这就相当于每一个元素都要进行一遍插入操作
-
第二种：拿到当前元素A，计算它在新桶中的下标位置为x，不先进行移动操作，而是知道它对应新下标后，把它添加到一条新下标对应的临时链表中去（此链表现在不是具体放在新桶下标位置那条），然后继续遍历下一个元素，重复操作，直到遍历完为止。遍历完后我们对于一条在原本数组的链表，拆分成了多条链表，其中每一条链表都是对应在新桶中的新下标位置，然后最后再把每一条链表插入到对应映射的新桶中的位置中去。
- 假设某条链表的长度为x，不管哪种方式的计算哈希操作时间复杂度都一样的，而方式一的插入操作一定为O(k)–（k为插入元素过程中时需要遍历的链表长度总和，特别对于某些元素下标都是同一个下标时，会有很多无效重复的遍历），而方式二的插入操作则是省略了这个重复遍历的过程,插入操作方式二的总体时间复杂度比较低， 所以我们会采取方式二进行插入操作，而且后面我们还可以优化，在最坏情况下的插入操作实际复杂度优化为O(2)
- 或许有人会问在拆分某条在原数组的链表时，此时组合成多条临时链表的过程中不是会增加其空间复杂度么。。其实在后面优化的过程中，临时的链表只有两条，可以忽略不计
-
-
如果数组容量是固定为2的n次幂，那么元素要么是原本的下标位置不变，要不就是在原本的下标位置 + 原本桶的容量（具体为什么会有这样的效果在讲resize()方法那有讲到），总体来讲**一条原链表只会最大拆分成两条链表O(x)，然后进行这两条链表的插入操作O(2 + d)，所以这样移动量会比较少O(x + 2 + d)**。
- d为链表插入到新下标对应的位置的链表末尾时要遍历的值，上图中比如链表C-F-M，插入到下标为12的末尾位置时，要先遍历下标12的原本含有的链表Y–链表拼接知识
-
相反，如果容量的大小没有固定住，可以按任意大小扩充，那么某个元素在新的桶中的位置是什么可能都会发生，一条原链表会拆分成多条链表，那么此时的移动量对比来说会比较大，最坏情况下O(x + y + d)–y为当前原链表长度值
-
-
7.疑问
-
在存放键值对时判断发生键重复时的条件为什么不是直接判断key的hashCode是否相同，而是(e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) -
modCount的fail-fast机制到底是怎么回事
-
对于数组容量为什么不采用long或者short来存？
8. 参考
-
[Java建设者]:看完这篇 HashMap ，和面试官扯皮就没问题了 (qq.com)
9. 补充
9.1 HashMap的问题
9.3.1 程序问题
9.3.1.1 死循环
9.3.1.2 数据覆盖
-
数据覆盖问题发生在并发添加元素的场景下，它不止发生在JDK 1.7版本中，具体流程如下
-
线程A进行添加元素时，通过key1计算得知具体的桶位置x1(并且对应桶位置还未存放元素，为null–对应桶位置已存在链表也可以，这是为了便于描述原理场景设简单一点），但是还没有进行真正的插入操作，线程A的时间片就用完了
-
这时刚好线程B也要进行添加元素，通过其key2计算得知具体的桶位置刚好也为x1，也就是线程B准备存放的键值对元素刚好与线程A要存放的键值对元素位置相同，因为此时线程A并还没有真正的插入了元素，所以对应桶的位置还是为null，所以线程B理所当然的按照正常流程往这位置插入，线程B执行完
-
线程A恢复执行，因为线程A的信息还停留在这个桶位置还没存放元素，它不知道线程B已经往里面插入了一个键值对元素，所以就把自己的键值对元素也插入到了这个位置，那么线程B插入的键值对就被线程A插入的键值对元素给覆盖了。
-
9.3.2 业务问题
9.3.2.1 无序性
-
这里的无序性问题指的是HashMap添加和查询的顺序不一致，导致程序执行的结果和程序员预期的结果不相符
-
示意图：
-
解决方案：使用
LinkedHashMap代替HashMap
10. 面试
10.1 拉链法导致的链表过度深问题为什么不用二叉搜索树代替，而选择红黑树？又为什么不一直使用红黑树？
-
之所以不使用二叉搜索树，是因为二叉搜索树有一种极端情况：当顺序插入时，会导致二叉搜索树变成跟链表那样的线性结构， 当元素过多时，遍历查找会非常慢
-
而红黑树是一棵平衡二叉树，在插入数据时通过左旋，右旋，变色这些操作来保持平衡。这样就保证了不会出现二叉搜索树那种在顺序插入时导致的极端情况，虽然保持“平衡”是需要付出代价的，但是在元素多的时候构造出来的红黑树，该代价所损耗的资源 要比遍历线性链表要少。
-
当元素比较少时，直接遍历链表就好，根本不需要引用红黑树。
