基于
Hash table的Map接口实现。实现了Map定义的所有方法，并允许key和value为null。(除了非线程安全和允许 null 之外，HashMap与Hashtable大致相同)这个类不保证map的顺序；尤其是，它不能保证顺序随时间的推移保持不变。
这个实现为基本操作(get和put)提供了恒定时间的性能，假设hash函数将元素适当地分散到桶中。在集合视图上迭代所需的时间与HashMap实例的容量(桶的数量)加上它的大小(键-值映射的数量)成正比。因此，如果迭代性能很重要，就不要将初始容量设置得太高(或负载因子设置得太低)。
HashMap的实例有两个参数影响其性能：初始容量和负载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了负载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认负载因子 (0.75) 在时间和空间成本上寻求一种折衷。负载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数HashMap类的操作中，包括get和put操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其负载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以负载因子，则不会发生rehash操作。
如果很多映射关系要存储在HashMap实例中，则相对于按需执行自动的rehash操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
此类是 Java Collections Framework 的成员。
| 属性 | 默认值 | 说明 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 1<<4==16 | 默认的初始容量 16。必须是2的幂。 |
| MAXIMUM_CAPACITY | 1<<30==230 | table 的最大容量 ，必须小于等于该值。且必须是2的幂。230= 01000000 00000000 00000000 00000000 |
| DEFAULT_LOAD_FACTOR | 0.75f | 默认负载因子 |
| TREEIFY_THRESHOLD | 8 | 树化阈值。当向哈希桶中添加元素时，如果 结点数 >= TREEIFY_THRESHOLD - 1 则将链表转换为树。取值范围(2, 8]。（还需要满足前提条件 MIN_TREEIFY_CAPACITY） |
| UNTREEIFY_THRESHOLD | 6 | 取消树化阈值。在split时如果发现桶中的结点数 <=此阈值，则将红黑树转为链表。取值应小于 TREEIFY_THRESHOLD，且最多为6。 |
| MIN_TREEIFY_CAPACITY | 64 | 触发树化的前提条件。 除了 哈希桶 中链表长度达到阈值 外还需要 哈希表.容量 >= 64，才能触发树化。(否则，如果一个 bin中有太多的结点，则会调整表的大小。)应该至少是4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。 |
不会序列化| 属性 | 说明 |
|---|---|
transient Node<K,V>[] table | 哈希表本质是一个数组。HashMap 是由 数组+链表or红黑树实现的，这就是那个数组。它的每个索引位置是一个哈希桶，桶中存放的是链表的头结点或树的根结点。在刚 new出来的新 HashMap 对象中table = null。在第一次使用时通过 resize() 初始化，并根据需要调整 哈希表大小。分配的长度必定是2的幂。(We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed. 这句只知道他说允许长度为0，但他所指的“当前不需要的引导机制”不知道是指的啥。不会翻555) |
transient Set<Map.Entry> entrySet | 缓存entrySet()的结果。作为一个当前 HashMap 所有键值对的视图。 |
transient int size | 此 Map 中实际包含的元素（键-值）数量。 |
transient int modCount | 结构修改次数。结构修改是指改变 HashMap 中的映射数量或以其他方式修改其内部结构(例如，重新哈希)的操作。该字段用于 HashMap 迭代器的并发冲突检测。(见ConcurrentModificationException)。 |
int threshold | 扩容阈值。键值对（entry）的个数大于阈值时，会触发扩容。( threshold = 容量 * 负载因子)。 |
final float loadFactor | 哈希表的负载因子。 |
| ——————————————————— |
| 访问修饰符&返回类型 | 方法 | 描述 |
|---|---|---|
| static final int | hash(Object key) | 计算 key 的 hash 值。为了尽量避免碰撞，使用 异或 和 位移。是出于性能考虑。 |
| static Class<?> | comparableClassFor(Object x) | 如果x的形式是Class C implements Comparable<C> 返回 C.class。否则返回 null。 |
| static int | compareComparables(Class<?> kc, Object k, Object x) | 如果 x的类型是 kc 就返回 kpareTo(x) 的结果，否则返回 0。 |
| static final int | tableSizeFor(int cap) | 返回大于 cap 的最近的一个 2 的倍数。 |
| ——————— | —————————————— |
计算 key 的 hash 值。为了尽量避免碰撞，使用 异或 和 位移。是出于性能考虑。
@Test
public void hashCodeTest(){int h = 0b11111111111111110000000000000000; // 0b开头表示二进制数int i = h >>> 16; // 无符号右移16位（包括符号位一起移）log.info("{}", BinaryString( i )); // 00000000000000001111111111111111 原本高位的16个1都移到了左边，左边空出的位置补0int hash = h ^ i; // 异或运算log.info("{}", BinaryString( hash )); // 11111111111111111111111111111111 i高16位没东西，直接照搬 h，低16位，不同为1，相同为 0
}
hash(Object key)hashCode() 获取 hash值。^ + >>>，把 hash 值搅拌一下，尽可能的减少不同 key 出现 hash 相同的情况。static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为何要使用异或和位移来减少碰撞？
如果x的形式是Class C implements Comparable<C> 返回其类的类型。否则为空。
x 的类型 C 和比较器的参数类型 Comparable<C> 一样时就返回 C）// 形式为 Class C implements Comparable<C>
Class C implements Comparable<C>;
C c = new C;
Class<?> clazz = comparableClassFor(c);
System.out.Name()); // C
// Class C implements Comparable<如果这里不是C> 返回 null
comparableClassFor(Object x)Comparable 否则直接返回 nullString.class，因为我们知道String实现了 Comparable<String>Comparable 并且泛型参数不为空，则返回此参数类型。static Class<?> comparableClassFor(Object x) {// 如果 x 是 Comparable 的实例。如果是继续，否则返回 null;if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;// 如果 x 是个 String 直接返回类型。if ((c = x.getClass()) == String.class) // bypass checksreturn c;// 获取 c 所实现的接口们（可能有多个所以放数组里）。如果不为 null 继续，否则返回 null;if ((ts = c.getGenericInterfaces()) != null) {// 逐个遍历接口类型for (int i = 0; i < ts.length; ++i) {if (// 1. 如果此接口 t 是某种 ParameterizedType（参数化类型，如 Collection<String>）((t = ts[i]) instanceof ParameterizedType)// 2. 并且，接口 t 的类型正好是 Comparable（为了调用 getRawType() 获取类型，做了强转）&& ((p = (ParameterizedType)t).getRawType() == Comparable.class)// 3. 并且，获取 p 的参数类型数组。不为 null。（Comparable<T>就是这里替换 T 的实参）&& (as = p.getActualTypeArguments()) != null// 4. 并且，只有 1 个&& as.length == 1 // 5. 并且，Comparable<参数> 中的 ‘参数’ == 给定的 x 的类型。&& as[0] == c) return c;}}}return null;
}
如果 x的类型是 kc 就返回 kpareTo(x) 的结果，否则返回 0。
此方法是要配合上面的 comparableClassFor(Object x) 一起用的。
@Test
public void compareComparablesTest(){String k = "jerry1";String x = "jerry2";Class<?> kc = comparableClassFor(k);int i = compareComparables(kc, k, x);log.info("{}", i); // -1
}
compareComparables(Class<?> kc, Object k, Object x)k：就是 key，比如类型是我们最见的“字符串”。String 就实现了 Comparable<String>。
kc ： 通过 comparableClassFor(k) 获取 k 实现的 Comparable<T> 中的实参。在 HashMap 的源码 find 、treeify、putTreeVal 这些方法中能看到它的身影。kc 都有先判断 非null 然后才使用。
以下情况中假设 k、x 的类型都是 String
x 为 null 直接返回 0 （表示比个毛）kc 是从 k 上获取的比较器 Comparable<String> 的参数的类型 String.class。k 没有实现 Comparable<String> 则 kc 为 null，否则 kc 为 String.classk 没有实现 Comparable<String> 比较器，就没法比，直接返回 0k 实现了 Comparable<X> 才会执行到 ((Comparable)k)pareTo(x) 这里。@SuppressWarnings({"rawtypes","unchecked"}) // 压制强转警告
static int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 : ((Comparable)k)pareTo(x));
}
返回大于 cap 的最近的一个 2 的倍数。
@Test
public void tableSizeForTest(){int cap = 50;int n = cap - 1; // n: 49。int MAXIMUM_CAPACITY = 1 << 30; // 1_073_741_824//int x,y;//log.info("原值={}; {} = {} | {}; Binary: {} = {} | {} ", x=y=n, x |= x >>> 1, y, y>>>BinaryString(x), BinaryString(y), toBinary(y>>>1, 6));n |= n >>> 1; // 原值=49; 57 = 49 | 24; Binary: 111001 = 110001 | 011000n |= n >>> 2; // 原值=57; 61 = 57 | 28; Binary: 111101 = 111001 | 011100n |= n >>> 4; // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111n |= n >>> 8; // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111n |= n >>> 16; // 原值=63; 63 = 63 | 31; Binary: 111111 = 111111 | 011111n = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;System.out.println(n); // 64
}
cap：目标容量传进来前已确保 >= 0
static final int tableSizeFor(int cap) { // cap = 50// 因为末尾需要 + 1 达到 0111 + 1 = 1000 效果。所以此处配合先 -1// 最终效果：确保当 cap 正好是 2的n次方时，最终结果是 cap 本身。int n = cap - 1; // 这一通 >>> 与 | 配合下来，使得最高位的 1 不变，右边所有的 0 都变成 1// （ 也就是找到最高位并将其右侧所有位都设置成 1 ）// 如： 1000 0000 变成 1111 1111; // 0010 1010 变成 0011 1111;n |= n >>> 1; n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;// 小于 0 直接返回 1 ( 2 的 0 次方 )// 如果大于最大值直接返回最大值，否则当前值 +1 返回。// +1 能保存是 2的二次幂。因为最高位后所有都是 1 时，再+1，肯定是一个 2 的幂。// 例：0000 1111 + 1 = 0001 0000 = 16return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
10000000 00000000 00000000 00000000
01000000 00000000 00000000 00000000 // >>> 1
————————————————————————————————————// 或
11000000 00000000 00000000 00000000
00110000 00000000 00000000 00000000 // >>> 2
————————————————————————————————————// 或
11110000 00000000 00000000 00000000
00001111 00000000 00000000 00000000 // >>> 4
————————————————————————————————————// 或
11111111 00000000 00000000 00000000
00000000 11111111 00000000 00000000 // >>> 8
————————————————————————————————————// 或
11111111 11111111 00000000 00000000
00000000 00000000 11111111 11111111 // >>> 16
————————————————————————————————————// 或
11111111 11111111 11111111 11111111
| 方法 | 描述 |
|---|---|
| HashMap(int initialCapacity, float loadFactor) | 指定初始容量和负载因子，构造一个空的 HashMap 。 |
| HashMap(int initialCapacity) | 指定初始容量，构造一个空的 HashMap 。负载因子 默认 0.75。 |
| HashMap() | 构造一个空的 HashMap【容量默认16 】，【负载因子默认0.75】 |
| HashMap(Map<? extends K, ? extends V> m) | 用指定的 Map，构造一个新的 HashMap。【负载因子默认 0.75】，容量足够存放给定的 Map。 |
指定初始容量和负载因子，构造一个空的 HashMap。
/*** @param initialCapacity 初始容量* @param loadFactor 负载因子* @throws 如果【初始容量 < 0】，或【负载因子 <= 0】，抛 IllegalArgumentException*/
public HashMap(int initialCapacity, float loadFactor) {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;// 返回大于 initialCapacity 的最小 2 次幂数。this.threshold = tableSizeFor(initialCapacity);
}
指定 初始容量，构造一个空的 HashMap。负载因子 默认 0.75。
/*** @param initialCapacity 初始容量* @throws 如果【初始容量 < 0】抛 IllegalArgumentException */
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); // DEFAULT_LOAD_FACTOR = 0.75f;
}
构造一个空的 HashMap 容量默认16 、负载因子默认0.75
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // DEFAULT_LOAD_FACTOR = 0.75f; 其它都是默认值。
}
用指定的 Map，构造一个新的 HashMap。负载因子使用默认的0.75，容量等于给定的 Map 大小。
/*** @param m 用来创建 HashMap 的给定 map* @throws 如果给定 map 为空，抛 NullPointerException */
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}
用给定的 map 填充当前 HashMap。主要是实现 Map.putAll 和 Map 构造 的底层逻辑，供它们调用 .
/*** @param m 用来创建 HashMap 的 map* @param evict 在最初构造这个 Map 时为 false，否则为true(最终会传给 afternodeinsert 方法 )。 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {// 取出给定 map 的大小，好用来创建新的 HashMapint s = m.size();// 没有内容直接跳过if (s > 0) {// 为 null 表示尚未初始化if (table == null) { // pre-size// 计算所需的初始容量（向上取整尽量避免频繁扩容）float ft = ((float)s / loadFactor) + 1.0F;// 如果没超最大值，直接使用。否则用最大值。int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 如果大于扩容阈值，则计算出新的扩容阈值（大于 t 的最小 2 次幂）。if (t > threshold) // 初始化时 threshold = 0 必触发threshold = tableSizeFor(t);// 给定的 map 比当前 HashMap 大。进行扩容。} else if (s > threshold)resize();// 遍历给定的 m 填充当前 HashMapfor (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();// 被构造函数调用时 evict = false putVal(hash(key), key, value, false, evict); }}
}
分析1：
((float)s / loadFactor) + 1.0F 通过+1.0F 努力避免刚出生没扑腾 put几下就触发扩容的尴尬。
1. (int)( float + 1 ) 的含义是向上取整。常用于小数部分不应舍弃的场景，比如1.5瓶饮料，需要2个瓶子装。
2. 以 s = 12 为例：如不 +1.0F 那么 threshold = (12 / 0.75) = 16 离下一次扩容近在咫尺。构造出来的新 map 几乎一抬脚就要触发一次扩容。
但如果有了 +1.0F 那么 (12 / 0.75) + 1 = 17 经过 tableSizeFor(17) 结果是 32。新 map 可以开心的扑腾put 不用尴尬了。
分析2：
在网上搜了一下，看到有一种说法，如果不+1，舍弃小数，会导致放不下（触发扩容浪费）。但是 size + 1 > size / 0.75 不可能成立，size > size / 0.75 更不可能。
更何况有tableSizeFor(t)的存在，size 要正好是 2的n次方，然后再满足上面的条件。
无论如何，实际PUT的个数永远不可能放不下啊？？？？这个疑惑困扰了我几天5555
分析3：
看了 anlian523-JDK8 HashMap源码 putMapEntries解析 发现：我把程序员们想得太好了，我认为他们会遵守基本的编码规范（如果你不知道为何 loadFactor 是 0.75 请别动它），但是如果有人不用 0.75 非要传一个奇怪的小数，就可能满足 16 + 1 > 16 / 0.95 == true ，所以我是不是可以理解为，这个 +1 不是用来防止容量不够，而是用来防刁民的
按给定的 hash 和 key 获取结点。找到就返回结点，否则返回 null。
注意： 返回 null 不一定是没找到。因为 HashMap 的 Value 也是允许为 null 的。
哈希表不为空且目标哈希桶不为空。继续处理，否则返回 nullTreeNode 调用树专用的get方法 getTreeNode final Node<K,V> getNode(int hash, Object key) {// tab 临时变量缓存哈希表（数组）// first 桶中的第一个结点（可能是链表的头结点，也可能是树的根结点）// n 哈希表的长度// k 临时变量缓存 keyNode<K,V>[] tab; Node<K,V> first, e; int n; K k;// 如果hash桶不为 null 且 长度 > 0，并且桶中第一个结点不为 null 则处理。// 否则返回 nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 总是检查第一个结点，如果 hash 和 key 都相等，说明找到目标，直接返回if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果头结点不是要找的目标，则继续看下一个是否为空，不为空就继续找。if ((e = ) != null) {// 判断头结点的类型，是否 TreeNode// 1. 如果是则调用树专用的get方法 getTreeNode// 2. 否则遍历链表逐个查找。找到 hash 和 key 都相等的结点就返回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;}
哈希表为null，则执行初始化。hash 值算出索引，找到对应的哈希桶，桶为空，直接创建结点填充。hash 和 key查找目标。putTreeVal 方法。否则遍历链表。value。/*** 用于实现 Map.put 和相关方法。（供它用调用）** @param hash 用 key 算出的 hash 值* @param key the key* @param value the value to put* @param onlyIfAbsent 如果为 true，则不更改现有值 (只有 putIfAbsent方法调用时会传 true)* @param evict 如果为false，则表处于创建模式。* @return 返回原先的值。如果原来没有返回 null*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果数组（哈希表）是空的，则初始化。并从返回的数组中获取长度。（也就是容量）if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 用 hash 算出索引，获取对应哈希桶上的第一个结点。// 1. 如果：哈希桶为空，则创建新结点并填充。// 2. 否则：向链表or树中追加。（当前桶中不为空，则按索引拿到的就是第一个结点）// 2.1. 如果：hash相同，key也相同，先选定此结点。（如果头结点不是。接下去需要遍历后续结点）// 2.2. 再如果：当前结点是红黑树结点。调用树专用的 putTreeVal 方法处理。// 2.3. 否则：遍历链表，找到目标修改 value，找到最后都没有，就追加在尾结点之后。if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 临时变量：e 用来缓存迭代过程中的当前结点// 临时变量：k 用来缓存迭代过程中当前结点的键Node<K,V> e; K k; 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 {// 遍历链表for (int binCount = 0; ; ++binCount) {// 从当前结点 p 中取出下一结点 e// 如果是 null 表示当前就是尾结点，用给定值 new 新结点，追加。// 再判断如果：满足树化条件，传入【数组、hash值】执行树化操作。// 完成后跳出循环。if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// hash 和 key 都一样，这就是我们要找的结点。跳出循环，进行后续操作。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 这不是要找的结点，更新 p 指向下一个结点，继续迭代。p = e;}}// 如果最终找到 hash 和 key 都与给定参数一样的结点。if (e != null) { // existing mapping for keyV oldValue = e.value; // 取出原值// 有值存在 || 值为null 就更新 valueif (!onlyIfAbsent || oldValue == null)e.value = value;// 调用给 LinkedHashMap 预留的回调函数，处理后续。此方法在HashMap中是空的。afterNodeAccess(e);return oldValue; // 返回原值}}// ========= 末尾追加新结点，会来到这里，需要做一些扫尾工作 =========// 更新修改计数。（检测并发冲突用的）++modCount;// 所拥有的元素个数 +1，如果大于【扩容阈值】就触发扩容。if (++size > threshold)resize();// 调用给 LinkedHashMap 预留的回调函数，处理后续。此方法在HashMap中是空的。afterNodeInsertion(evict);return null;
}
tab[i = (n - 1) & hash] 用 hash 与 数组长度取模，算出哈希桶位置。
2的幂可利用 & 实现取模。(hash % 2^n) == (hash & (2^n)-1)2的幂。（早有预谋）。2^n 二进制数的特点：高位1其它全是0。比如1 0000-1 实现去掉最高位，后面全变成 1。比如1 0000 - 1 = 1111table 长 16，hash 后 4 位是0101。（前面的 28 位 &0 后肯定都是 0 了，可以忽略）???????? ???????? ???????? ????0101 = 5 // hash
00000000 00000000 00000000 00001111 = 15 // table.length: 16-1 得 15
--------------------0 1 0 1 = 5 // 5 % 16 == 5
(hash % 2^n) == (hash & (2^n)-1) 推导：x2 就是左移1位，÷2就是右移1位。丢弃，空出的位置补0。// 首先已知：9527 % 16 = 7
// 工具方法便于直接 F12 验算
var toBinary = n=&String(2).padStart(32, 0).match(/.{8}/g).join(' ');
00000000 00000000 00100101 00110111 // toBinary(9527);
// 除以16等于 9527 ÷2, ÷2, ÷2, ÷2 也就是右移 4 位。商 595 就拿到了。
00000000 00000000 00000010 01010011 // toBinary(9527>>4);
// 但是余数呢？ 经过观察发现，余数正好就是移出右侧边界被丢弃的部分 7。其实，我们直接取后 4 位就行了。0000 00000000 00000010 01010011 0111
// 16 - 1 = 15 正好后 4 位 1 得到一个完美的掩码。00000000 00000000 00000000 00001111 // toBinary(16-1)
& 00000000 00000000 00100101 00110111 // toBinary(9527)
—————————————————————————————————————0111 // 通过 & 前 28 位都被消除，得到了末尾 4 位。也就是余数了。
初始化或将数组 table 扩容到原来的 2 倍。
如果为 table 为 null，则按照扩容阈值 threshold 分配初始容量。
另外，因为我们使用的是2的幂展开，所以每个bin中的元素要么必须保持相同的索引，要么在新表中以2的幂偏移量移动。
返回完成初始化或扩容后的 table
哈希表，扩容阈值，新容量、阈值oldThr，则使用它初始化【容量】哈希表，并填充数据newCap 创建哈希表。哈希表，否则遍历旧哈希表向新数组填充。final Node<K,V>[] resize() {// ================= 一、准备工作：先声明一堆临时变量 =================// 临时变量 oldTab、newTab 缓存 【数组 table】：扩容前的原值/扩容后的新值。// 临时变量 oldThr、newThr 缓存 【扩容阀值 threshold】：扩容前的原值/扩容后的新值。// 临时变量 oldCap、newCap 缓存 【数组table的长度】：扩容前的原值/扩容后的新值。Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// ================= 二、计算新的【容量、扩容阈值】=================// 1. 扩容：oldCap > 0 表示当前 HashMap 已经初始化过，需要执行的是扩容操作。// 2. 否则：如果有【扩容阀值】threshold，则使用它初始化【容量】// 3. 否则：全都用默认值。if (oldCap > 0) {// 如果当前容量 >= 上限。// 将扩容阈值 threshold 设为 Integer.MAX_VALUE，因为永远不可能达到就再也不会触发扩容了。// 未进行扩容操作，直接将【原数组】返回。 if (oldCap >= MAXIMUM_CAPACITY) { // 01000000 00000000 00000000 00000000 2^30threshold = Integer.MAX_VALUE; // 01111111 11111111 11111111 11111111 2^31-1return oldTab;}// 否则：如果(扩容前原容量x2 < 上限)并且(扩容前原容量 >= 默认的初始容量) else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // DEFAULT_INITIAL_CAPACITY = 16{// 扩容阈值X2，得到新的扩容阈值newThr = oldThr << 1; }}// 初始化：// 在初始化前，有调用其他操作，已经算出了扩容阈值。else if (oldThr > 0)newCap = oldThr; // 初始化容量 = 扩容阈值// 初始化：// 例如：new无参构造后，没调用过会初始化 threshold 的操作，直接调用 put 就会来到这里else { newCap = DEFAULT_INITIAL_CAPACITY; // 16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12}// 如果至此尚未算出新的 threshold，就算一下。（从上面第2个分支来的）if (newThr == 0) {// 扩容阀值 = 新容量 * 负载因子float ft = (float)newCap * loadFactor;// (新容量 < 容量上限) && (扩容阀值 < 容量上限) 返回 ft 否则返回无法触及的 Integer.MAX_VALUEnewThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr; // 更新扩容阀值 // ================= 三、创建新数组，并填充数据 =================// 按前面算出来的容量，new 一个新 Node 数组。（ HashMap的根容器 ）@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;// 取出索引 j 位置上的结点。（也是这个坑里的链表的头结点）if ((e = oldTab[j]) != null) {// 设置为 null 方便垃圾回收oldTab[j] = null; // 1. 如果当前结点无后，表示已经是最后一个。直接按 hash 算出新的索引并填充到数组中。// 2. 否则如果是 TreeNode 结点，说明已经树化。调用调整 TreeNode 专用的方法。// 3. 否则（是链表结点）遍历链表，搬运结点到扩容后的新数组来。（部分结点要移到新的索引）if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else {// --- 遍历链表 ---// 搬运结点到新数组。保持原链表顺序。// 新数组分为高低两部分，低表示原有索引区域，高表示新扩展出来的索引区域。// 当前类源码规范定义数组大小只能是 2^n Node<K,V> loHead = null, loTail = null; // 临时变量：低位的头结点、尾结点。Node<K,V> hiHead = null, hiTail = null; // 临时变量：高位的头结点、尾结点。Node<K,V> next; // 临时变量：当前结点的下一结点do {next = e.next;// 1. 如果 (e.hash & oldCap) == 0 索引不变，无需移动。// 2. 否则表示结点要移到新扩展的高低区域。if ((e.hash & oldCap) == 0) {// 如果尾结点为 null，表示链表是空的，先设置头结点。// 否则追加到末尾。/// 最后更新尾结点变量。if (loTail == null) loHead = = e;loTail = e;}else { // 同上 if (hiTail == null)hiHead = = e;hiTail = e;}} while ((e = next) != null);// 扫尾工作// 如果尾结点不为 null，将其 next 设置为 null (既然是末尾了，后没肯定是空的)// 然后将链表的头结点，装进数组的当前索引位置。if (loTail != null) { = null;newTab[j] = loHead;}// 向新扩展区域填充时，索引 + 偏移量。其他同上。if (hiTail != null) { = null;newTab[j + oldCap] = hiHead;}}}}}return newTab; // 最终返回初始化完成 or 扩容后的新数组。
}
(e.hash & oldCap) == 0
假设：
e.hash = 9527
oldCap = 16
newCap = 32
原理：
扩容前取hash的后4位算索引，所以后4位相同的 hash 都蹲同一个坑。
扩容后取hash的后5位算索引，只有后5位都相同的 hash 才蹲同一个坑。
如果有两个hash 分别是 01000、11000 那么在容量为16时只取后4位计算索引，它们的值相同，都蹲一个坑里。
而扩容后，取后5位计算索引，它两就尿不到一壶了。
并且多出来的这一位肯定是 2^n（而且正好等于 oldCap 此例中是16），原索引加上它，可以完美的实现向新增区域偏移。
例子：
// 扩容前计算索引 (9527 & (16-1))
00000000 00000000 00100101 00110111 // toBinary(9527);
00000000 00000000 00000000 00001111 // oldCap 后四位保留
—————————————————————————————————————————————————————————0111 // 得到索引 7// 扩容后计算索引 (9527 & (32-1))
00000000 00000000 00100101 00110111 // toBinary(9527);
00000000 00000000 00000000 00011111 // newCap 后五位保留
—————————————————————————————————————————————————————————10111 // 得到索引 16 + 7 = 23
newCap 扩容1倍，也就是左边多出1位可用于计算。hash 是0，那计算出来的索引与扩容前完全一样。我们让此hash原位不会。1则算出来的索引 = oldCap + 7 = 16 + 7 落在了新扩容的区域。&1 看结果是0还是1就行了。oldCap 正是此位上为 1 其他位都是 0的数 ，完美工具人。将哈希桶中的链表转成红黑树。前提条件 ：MIN_TREEIFY_CAPACITY = 64
哈希表长度 < MIN_TREEIFY_CAPACITY 时，冲突的主要原因归咎于 哈希表 容量太小，扩大点自然能解决。（扩容后hash值多出来的那一位上为1 的元素，就会移到新扩的区域，自然链表的长度就下来了）
但是当数组长度达到 64 后再无脑扩容就不划算了，所以执行树化操作，将链表转为红黑树。
64，直接扩容解决。>= 64 并且按 hash 取到了头结点，则执行树化：头结点放进数组的相应索引中。头结点非空，在头结点上调用 treeify 执行树化。在遍历中可以看到有prev，next，说明在树化前，我们已经得到了一个双向链表。
并且转换完成后双向链表的信息并不会受影响，所以我们得到的结果既是一个红黑树也是一个双向链表。
/**
* @param tab 哈希表（HashMap底层的数组容器）
* @param hash 需要树化的结点的 hash 值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 1. 如果数组为空或长度小于 MIN_TREEIFY_CAPACITY 则直接扩容 // 2. 否则按【hash】算出索引，找到目标桶，将其内容从【链表】转成【红黑树】if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) { // 取出头结点作为当前结点 e// 声明新链表的：头结点、尾结点TreeNode<K,V> hd = null, tl = null;// 遍历结点逐个移到新声明的头结点后（直到整个链表都移完）// 1. 循环的第一轮中，让新链表的【头结点】和【尾结点】都指向【当前结点】，// 2. 后面每次循环中，将【当前结点】追加到【尾结点】后面，然后更新【尾结点】。do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = = p;}tl = p;} while ((e = e.next) != null);// 把【头结点】hd 放进 tab[index]。如果 hd 非空，正式开始树化if ((tab[index] = hd) != ify(tab); // 在头结点上调用树化方法。}
}
按给定参数，移除结点。返回被移除的结点，如果没找到返回 null
哈希表非空且桶中第一个结点也非空，才继续，否则直接返回 null/*** @param hash key 生成的 hash 值* @param key 键* @param value 用于时行匹配的值，只在 matchValue = true 时有用。否则请忽略* @param matchValue 如果为 true 则只移除 value 匹配的结点。* @param movable 当结构是树时会用到。如果为 true 会将红黑树的根结点移动到最前面（桶中的第一个结点）* @return */
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {// tab 临时变量缓存哈希表（数组）// p 临时变量缓存结点// n 哈希表（数组）的长度// index 用 hash 算出来的索引Node<K,V>[] tab; Node<K,V> p; int n, index;// 哈希表不为空且长度 > 0，并且头结点也不为 null 则继续处理，否则返回 nullif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {// node 临时变量缓存结点（要移除的目标结点）// e 临时变量缓存结点（遍历链表时用到）// k key// v valueNode<K,V> node = null, e; K k; V v;// ----- 找结点 -----// 1. 判断头结点，hash和key都相等就是目标，用临时变量 node 存好。// 2. 如果头结点不是目标，且下一结点不为null，则继续查找：// 2.1. 如果结点类型是 TreeNode 则调用树专用的查找方法 getTreeNode// 2.2. 否则遍历链表逐个对比hash和key都相等就是目标，赋给临时变量 node。// 一旦找到直接跳出循环，不浪费时间。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// ----- 移除结点 -----// 1. 判断条件满足才继续处理移除逻辑。// 1.1. 目标结点 node 是否为 null，为null直接结束// 1.2. 并且：matchValue == true 时要判断 value 是否与给定值相等// 2. 判断结点类型：// 2.1. 如果结点类型是 TreeNode 则调用树专用的移除方法 removeTreeNode// 2.2. 否则如果：目标结点就是第一个结点，直接将 tab[index] 替换成它的 next// 2.3. 否则：p 是目标结点的父结点，断开链表，将 p.next 指向 自己的next。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] = ; = ;++modCount; // 结构修改计数+1--size; // 大小-1afterNodeRemoval(node); // 移除结点后回调return node; // 返回被移除的结点}}return null;
}
// 供 HashSets 的 writeObject 方法调用
final float loadFactor() { return loadFactor; }
哈希表非空，返回其长度。threshold 扩容阈值 > 0，则返回扩容阈值。默认的初始容量 16final int capacity() {return (table != null) ? table.length :(threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY;
}
将HashMap实例的状态保存到流中(即序列化它)。
会被序列化的内容：
private void writeObject(java.io.ObjectOutputStream s) throws IOException {int buckets = capacity(); // 获取容积// 将当前类的非静态non-static 和非瞬态 non-transient 字段写入此流。// 此字段只能从正在序列化的类的 writeObject 方法中调用。// 如果从其他地方调用该字段，则将抛出 NotActiveException。s.defaultWriteObject(); s.writeInt(buckets); // 容积，作为32位整型写入流。s.writeInt(size); // size，作为32位整型写入流。internalWriteEntries(s); // 当前 hashMap的所有 key、value 写到输出流 s
}
从流重新构造 HashMap 实例(即，反序列化它)。
从流读入数据前会先重置当前 HashMap。与序列化方法 writeObject 的操作相对应。
private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {// 从此流读取当前类的非静态和非瞬态字段。// 此方法只能从正在反序列化的类的 readObject 方法中调用。// 如果从其他地方调用该字段，则将抛出 NotActiveException。s.defaultReadObject();// 重置到初始默认状态。reinitialize();// 负载因子 <= 0 或 不是浮点数 就抛锅if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new InvalidObjectException("Illegal load factor: " + loadFactor);s.readInt(); // 读取一个32位整型。这个值是：容积int mappings = s.readInt(); // 读取一个32位整型。这个值是：size// 如果 size < 0 直接抛锅// 否则如果 size > 0// 1. 先算：负载因子// 2. 再算：容积// 3. 按容积创建数组（哈希表）// 4. 遍历 i从输入流中逐个读取 key、value 填进 HashMapif (mappings < 0)throw new InvalidObjectException("Illegal mappings count: " + mappings);else if (mappings > 0) { // (if zero, use defaults)// ----- 计算容积 -----// 计算负载因子。确保在 0.25 - 4.0 范围内float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);// 算出容积 fc = size / loadFactor + 1.0f// 如果：fc < 【默认的初始容量 16】 则使用【默认容量】// 否则如果： fc >= 【容量最大值】，则使用 【容量最大值】// 否则：返回大于 fc 的最小2的幂。float fc = (float)mappings / lf + 1.0f;int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? DEFAULT_INITIAL_CAPACITY :(fc >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)fc));// ----- 更新扩容阈值 -----// 扩容阈值（临时变量） = 容量 * 负载因子float ft = (float)cap * lf;// 如果 容积cap < 容积最大值，并且 ft < 容积最大值，使用 ft// 否则：使用 Integer.MAX_VALUEthreshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?(int)ft : Integer.MAX_VALUE);// 按容量创建数组（哈希表）@SuppressWarnings({"rawtypes","unchecked"}) // 压制警告Node<K,V>[] tab = (Node<K,V>[])new Node[cap];table = tab;// 循环从输入流中读取 key 和 value 填入当前 HashMapfor (int i = 0; i < mappings; i++) {@SuppressWarnings("unchecked") // 压制警告K key = (K) s.readObject();@SuppressWarnings("unchecked") // 压制警告V value = (V) s.readObject();putVal(hash(key), key, value, false, false);}}
}
以下受包保护的方法被设计成可以被LinkedHashMap覆盖，但不能被任何其他子类覆盖。几乎所有其他内部方法都是包保护的，但都声明为final，因此可以由LinkedHashMap、视图类和HashSet使用。
/*** @param hash 结点的 hash 值* @param key 结点的 key 值* @param value 结点的 value 值* @param next 指向的下一个结点对象*/Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}
/*** @param p 指向的下上个结点对象* @param next 指向的下一个结点对象*/Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);}
/*** @param hash 结点的 hash 值* @param key 结点的 key 值* @param value 结点的 value 值* @param next 指向的下一个结点对象*/TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {return new TreeNode<>(hash, key, value, next);}
/*** @param p 指向的下上个结点对象* @param next 指向的下一个结点对象*/TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);}
重置至初始默认状态. 供 clone 和 readObject 两个方法调用。
void reinitialize() {table = null;entrySet = null;keySet = null;values = null;modCount = 0;threshold = 0;size = 0;}
void afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }
仅供 writeObject 调用，以确保兼容的排序。
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {Node<K,V>[] tab;if (size > 0 && (tab = table) != null) {// 遍历数组for (int i = 0; i < tab.length; ++i) {// 遍历链表（此处红黑树的结点同时也是一个双向链表结点。treeifyBin干的）for (Node<K,V> e = tab[i]; e != null; e = e.next) {s.writeObject(e.key);s.writeObject(e.value);}}}}
| 访问修饰符&返回类型 | 方法 | 描述 |
|---|---|---|
| void | clear() | Removes all of the mappings from this map. |
| Object | clone() | Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned. |
| V | compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping). |
| V | computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) | If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null. |
| V | computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value. |
| boolean | containsKey(Object key) | Returns true if this map contains a mapping for the specified key. |
| boolean | containsValue(Object value) | Returns true if this map maps one or more keys to the specified value. |
| Set<Map.Entry<K,V>> | entrySet() | Returns a Set view of the mappings contained in this map. |
| void | forEach(BiConsumer<? super K,? super V> action) | Performs the given action for each entry in this map until all entries have been processed or the action throws an exception. |
| V | get(Object key) | Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. |
| V | getOrDefault(Object key, V defaultValue) | Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key. |
| boolean | isEmpty() | Returns true if this map contains no key-value mappings. |
| Set<K> | keySet() | Returns a Set view of the keys contained in this map. |
| V | merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) | If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. |
| V | put(K key, V value) | Associates the specified value with the specified key in this map. |
| void | putAll(Map<? extends K,? extends V> m) | Copies all of the mappings from the specified map to this map. |
| V | putIfAbsent(K key, V value) | If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value. |
| V | remove(Object key) | Removes the mapping for the specified key from this map if present. |
| boolean | remove(Object key, Object value) | Removes the entry for the specified key only if it is currently mapped to the specified value. |
| V | replace(K key, V value) | Replaces the entry for the specified key only if it is currently mapped to some value. |
| boolean | replace(K key, V oldValue, V newValue) | Replaces the entry for the specified key only if currently mapped to the specified value. |
| void | replaceAll(BiFunction<? super K,? super V,? extends V> function) | Replaces each entry’s value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception. |
| int | size() | Returns the number of key-value mappings in this map. |
| Collection<V> | values() | Returns a Collection view of the values contained in this map. |
Class HashMap<K,V>
笑虾：Java 学习笔记 HashMap 中的 hash 方法为何要进行异或和位移？
笑虾：Java 集合学习笔记：HashMap - 静态内部类 Node、TreeNode
CSDN-程序员的时光-详细理解HashMap数据结构，太齐全了！
本文发布于:2024-01-31 00:37:56，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170663275423990.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
