# 建议先了解 ## Java位运算 [Java 位运算(移位、位与、或、异或、非）_Ely&#39;s Blog-CSDN博客_java 位运算](https://blog.csdn.net/xiaochunyong/article/details/7748713) ## hashcode和equals ## HashMap计算哈希值为 `hash` 的 `key` 对应的数组下标 `i` 的方法 ```java i = (数组长度 - 1) & hash ``` ## 一些变量 ### MAXIMUM_CAPACITY > 最大容量，在两个带参数的构造函数隐式指定更高值时使用。 > > **必须是 2 的幂，并且 小于等于 2^30(1<<30)。** ```java // 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. static final int MAXIMUM_CAPACITY = 1 << 30 = 1073741824 ``` ### DEFAULT_INITIAL_CAPACITY > 默认初始化容量 > > **必须是 2 的幂** ```java // The default initial capacity - MUST be a power of two static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16 ``` # 获取元素 ## 1. public V get(Object key); ### 方法注释翻译 > 返回 `key` 对应的 `value` ，不存在则返回 `null` > > 假设 `HashMap` 内部存在 `KEY->VALUE` 这样的一对映射 > > - 如果传进来的 `key` 为 `null` ，并且本地的 `KEY` 也为 `null` ，返回 `VALUE` > - 否则如果 `KEY.equals(k)` ，返回 `VALUE` > - 否则返回 `null` > > 返回值为 `null` 可能代表两种情况： > > 1. `HashMap` 不存在 `key` 的映射 > 2. 存在 `key->null` 的这样一对映射 > > **可以使用 `containsKey()` 区分这两种情况** ### 源码注释 ```java /** * 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类型对象e Node<K,V> e; // 调用getNode方法，将返回值赋给e并判断，null直接返回null，否则返回e.value return (e = getNode(hash(key), key)) == null ? null : e.value; } ``` ### 注意 get方法的key可以为null ## 2. static final int hash(Object key); ### 方法注释翻译 > 计算 key.hashCode() 并将散列的较高位（异或）传播到较低位。 > > 由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。 （众所周知的例子是在小表中保存连续整数的浮点键集。）所以我们应用了一种向下传播高位影响的变换。 > > 位扩展的速度、效用和质量之间存在权衡。 因为许多常见的哈希集已经合理分布（因此不会从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，所以我们只是以最便宜的方式对一些移位的位进行异或以减少系统损失，以及合并最高位的影响，否则由于表边界而永远不会在索引计算中使用。 ### 源码注释 ```java /** * 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; // key为null直接返回0 // 否则调用key.hashCode方法并赋值给h，然后和h无符号右移16位进行 异或 运算返回 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` ## 3. final Node<K,V> getNode(int hash, Object key); ### 方法注释翻译 > 实现 `Map.get` 以及相关方法 > > 参数 `hash` ： `key` 的哈希值 > > 参数 `key` ：`key` > > 返回值： `Node` 或者 `null` ### 源码注释 ```java /** * 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) { // 变量声明 // 1. 声明Node类型数组tab // 2. 声明Node类型first、e // 3. 声明int类型n // 4. 声明泛型K的k Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 1. 将table赋值给tab并判断是否不为null，不为null进行下一个判断 // 2. 将tab.length赋值给n并判断是否大于0，大于0进行下一个判断 // 3.1 将传进来的key的哈希值（hash）和（tab长度 - 1）进行（按位与）运算 // 3.2 将运算结果作为tab数组的下标，获取对应位置的Node赋值给first并判断是否为null // 以上条件全部满足则继续执行 // 否则，若不满足1或2表示HashMap为空，若不满足3表示不存在key，直接返回null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 1. 判断第一个元素的hash值和key的hash是否相等，相等进行下一个判断 if (first.hash == hash && // always check first node // 2.1 将第一个元素的key赋值给k并判断和key的地址是否相等，不相等进行下一个判断 // 2.2.1 传进来的key是否不为null，不为null进行下一个判断 // 2.2.2 传进来的key equals 第一个元素的key // 以上条件全部满足则继续执行，返回第一个元素 // 第一个Node的hash值和传入的key的哈希值相等并且第一个Node的key和传入的key地址一样或者equals方法返回true，代表第一个传入的key指向的是第一个元素 ((k = first.key) == key || (key != null && key.equals(k)))) // 返回第一个元素 return first; // 将first的next赋值给e，并判断first是否为链表 if ((e = first.next) != null) { // 如果first是TreeNode，代表链表转为了红黑树 if (first instanceof TreeNode) // 调用TreeNode的getTreeNode方法获取对应的Node return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 遍历链表找到key对应的Node do { // 和上面判断first的逻辑一样，改了一下比较的变量而已，从first变为e（链表中first下面的元素） if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; // 终止条件 } while ((e = e.next) != null); } } // （key的哈希值 & table长度 - 1）对应下标没有存放Node // 或者存放了Node，但还是没找到（遍历first和first下的所有元素，调用equals都返回了false），返回null return null; } ``` ## 4. final TreeNode<K,V> getTreeNode(int h, Object k) **注意，这个方法是HashMap里面的TreeNode类里的方法**  ### 方法注释翻译 > 找到 root node ### 源码注释 ```java /** * Calls find for root node. */ final TreeNode<K,V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } ``` # 添加元素 ## 1. public V put(K key, V value)； ```java /** * 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); } ``` ## 2. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) ; ### 方法注释翻译 > 实现 `Map.put` 和相关方法 > > 参数： > > ``` > > ``` > > `hash` ：`key` 的哈希值 > `key` ：`key` > `value` ：要放置的值 > `onlyIfAbsent` ：如果为真，则不更改现有值 > `evict` ：如果为 false，则表处于创建模式 > > 返回： > > ``` > 以前的值，如果没有，则为 null > ``` ### 源码注释 ```java /** * Implements Map.put and related methods. * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @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; // Node数组为空则resize()，并赋值tab和n if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // i = 长度-1 & key的哈希值，p = Node数组下标i的元素，判断是否为空 if ((p = tab[i = (n - 1) & hash]) == null) // 为空则直接新建Node tab[i] = newNode(hash, key, value, null); else { // 不为空继续判断 Node<K,V> e; K k; // get方法中出现过两次了，传入的key和经过位运算后的得到的下标为i的元素的key对应 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 将该Node赋值给e e = p; // 否则判断是否是红黑树 else if (p instanceof TreeNode) // 调用红黑树的putTreeVal方法，将返回值赋值给e e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 遍历链表，并记录binCount for (int binCount = 0; ; ++binCount) { // e表示链表第二个到最后一个元素 // 遍历到了最后一个位置，表示本地不存在传入的key if ((e = p.next) == null) { // 调用newNode方法，尾插法增加节点 p.next = newNode(hash, key, value, null); // 如果个数超过TREEIFY_THRESHOLD - 1 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 转化为红黑树 treeifyBin(tab, hash); // 退出循环，不执行下面的判断传入的key链表是否存在语句 break; } // 还是判断传入的key是否已存在 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // e赋值给p p = e; } } // 如果传入的key本地已存在 if (e != null) { // existing mapping for key // 用oldValue保存本地的value V oldValue = e.value; // 如果不存在的时候也添加 或者 存的值为null if (!onlyIfAbsent || oldValue == null) // 更新本地存在的Node的value e.value = value; // 调用一个空方法，主要给LinkedHashMap移动元素到最后用 afterNodeAccess(e); // 返回替换前的值 return oldValue; } } // transient int modCount // 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). ++modCount; // 大小加一并判断，如果大于threshold（The next size value at which to resize (capacity * load factor).），则调用resize()方法 if (++size > threshold) resize(); // 调用一个空方法，参数为是否为创建模式 afterNodeInsertion(evict); // 返回null return null; } ``` ## 3. resize() ### 方法注释翻译 > 初始化size或使size加倍。 > > 如果为空，则根据字段阈值中持有的初始容量目标进行分配。 > > 否则，因为我们使用的是 2 的幂扩展，所以每个 bin 中的元素必须保持相同的索引，或者在新表中以 2 的幂的偏移量移动。 > > 返回： `table` 数组 ### 源码注释 ```java /** * 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() { // 声明oldTab变量，赋值为当前table数组 Node<K,V>[] oldTab = table; // 记录当前table数组长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 记录当前旧的数组的容量阈值（总容量 * 负载因子） int oldThr = threshold; // 声明新的数组长度、新的容量阈值，默认为0 int newCap, newThr = 0; // 如果旧的数组不为空 if (oldCap > 0) { // 如果旧的数组长度 超过 最大容量 if (oldCap >= MAXIMUM_CAPACITY) { // 当前容量阈值设置为整数的最大值 threshold = Integer.MAX_VALUE; // 直接返回旧数组 return oldTab; } // 1.1 新数组长度赋值为旧数组长度的两倍 // 1.2 加倍后判断是否小于最大容量，如果小于进行下一个判断 // 2. 旧的数组长度 是否超过 默认长度16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 将新的容量阈值更新为旧的 * 2 newThr = oldThr << 1; // double threshold } // 否则 如果旧的数组为空，并且旧的容量阈值 大于 0 else if (oldThr > 0) // initial capacity was placed in threshold // 新的容量等于旧的容量阈值 newCap = oldThr; // 否则 如果旧的数组为空，并且旧的容量阈值 <= 0 else { // zero initial threshold signifies using defaults // 新的容量等于默认默认容量 newCap = DEFAULT_INITIAL_CAPACITY; // 新的容量阈值 = 默认负载因子 * 默认容量 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的容量阈值为0 if (newThr == 0) { // 计算新的容量阈值 ft = 新的容量 * 负载因子 float ft = (float)newCap * loadFactor; // 根据新的容量是否小于最大容量 并且 ft是否小于最大容量 // 新的容量阈值 为 ft // 或者 Integer.MAX_VALUE newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 更新容量阈值为newThr threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 创建新的Node数组，长度为newCap Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 更新table为新创建的Node数组 table = newTab; // 判断旧Node数组是否不是null if (oldTab != null) { // 遍历旧的Node数组 for (int j = 0; j < oldCap; ++j) { // 存储当前遍历到的元素 Node<K,V> e; // 判断是否不为null，为null不需要操作，继续遍历下一个位置 if ((e = oldTab[j]) != null) { // 将当前位置指向null oldTab[j] = null; // 如果不是链表 if (e.next == null) // 将当前位置的元素直接 复制到 新Node数组 // 新的下标为 key哈希值 逻辑与 （新容量 - 1） newTab[e.hash & (newCap - 1)] = e; // 红黑树 else if (e instanceof TreeNode) // 调用红黑树的split方法 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 链表 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 遍历链表每一个节点 do { next = e.next; // 判断是否需要移位，为0不需要，连接到loTail后面 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 需要移位，连接到hiTail后面 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; // 不需要移位的放到新Node数组原来的下标上 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; // 需要移位的，移动到新的Node数组往后移动 旧的容量 位 newTab[j + oldCap] = hiHead; } } } } } // 返回新的Node数组 return newTab; } ``` ## 4. newNode() 创建一个常规（非树）节点 ```java // Create a regular (non-tree) node Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } ``` ### Node<K,V> ```java /** * 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; 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; } } ``` ## 5. putTreeVal() // TODO ## 6. treeifyBin() // TODO ## 7. afterNodeAccess() ```java // Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { } ``` ## 8. split() // TODO # 补充 `HashMap` 和 `HashTable` 的区别