[Java8HashMap详解系列]2.HashMap中Key的index是怎样计算的?

1.HashMap 的存储数据结构

2.HashMap 中 Key 的 index 是怎样计算的?

3.HashMap 的 put() 方法执行原理

4.HashMap 的 get() 方法执行原理

5.HashMap 的 remove() 方法执行原理

6.HashMap 的扩容 resize() 原理

7.HashMap 中的红黑树原理

HashMap中的 table 是怎样确定数组索引位置的?

对于HashMap内的所有实现来说&＃xff0c;首先第一步是定位对键值对所在数组的索引下标位置&＃xff0c;这是后续所有操作的基础.

如下代码是展示索引下标获取的基本逻辑:

/* ---------------- Static utilities -------------- *//*** 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&＃39;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 &＃61;&＃61; null) ? 0 : (h &＃61; key.hashCode()) ^ (h >>> 16);}

然后, 数组元素的下标算法是:

public static final int index(int hash, int n) {return (n - 1) & hash;}


代码拆解:

public static final int hash(Object key) {if (key &＃61;&＃61; null) {return 0;}int h &＃61; key.hashCode();int rh &＃61; h >>> 16;out.println("&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(" &＃43; key &＃43; ") &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;");out.println("key \t\t" &＃43; key);out.println("h&＃61;key.hashCode() \t\t" &＃43; toBinary(h) &＃43; "\t\t" &＃43; h);out.println("rh&＃61;h>>>16 \t\t" &＃43; toBinary(rh) &＃43; "\t\t" &＃43; rh);return h ^ rh;}public static final int index(int hash, int n) {out.println("hash&＃61;h ^ rh \t\t" &＃43; toBinary(hash) &＃43; "\t\t" &＃43; hash);out.println("n &＃61; \t\t" &＃43; toBinary(n) &＃43; "\t\t" &＃43; (n));out.println("n - 1&＃61; \t\t" &＃43; toBinary(n - 1) &＃43; "\t\t" &＃43; (n - 1));int index &＃61; (n - 1) & hash;out.println("index&＃61;(n - 1) & hash \t\t" &＃43; toBinary(index) &＃43; "\t\t" &＃43; index);out.println();return index;}


运行测试数据:


&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(a) &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
key a
h&＃61;key.hashCode() 00000000000000000000000001100001 97
rh&＃61;h>>>16 00000000000000000000000000000000 0
hash(a)&＃61;97
hash&＃61;h ^ rh 00000000000000000000000001100001 97
n &＃61; 00000000000000000000000000000001 1
n - 1&＃61; 00000000000000000000000000000000 0
index&＃61;(n - 1) & hash 00000000000000000000000000000000 0&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(b) &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
key b
h&＃61;key.hashCode() 00000000000000000000000001100010 98
rh&＃61;h>>>16 00000000000000000000000000000000 0
hash(b)&＃61;98
hash&＃61;h ^ rh 00000000000000000000000001100010 98
n &＃61; 00000000000000000000000000000010 2
n - 1&＃61; 00000000000000000000000000000001 1
index&＃61;(n - 1) & hash 00000000000000000000000000000000 0&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(abc) &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
key abc
h&＃61;key.hashCode() 00000000000000010111100001100010 96354
rh&＃61;h>>>16 00000000000000000000000000000001 1
hash(abc)&＃61;96355
hash&＃61;h ^ rh 00000000000000010111100001100011 96355
n &＃61; 00000000000000000000000000000100 4
n - 1&＃61; 00000000000000000000000000000011 3
index&＃61;(n - 1) & hash 00000000000000000000000000000011 3&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(abcde) &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
key abcde
h&＃61;key.hashCode() 00000101100001001111010001100011 92599395
rh&＃61;h>>>16 00000000000000000000010110000100 1412
hash(abcde)&＃61;92598759
hash&＃61;h ^ rh 00000101100001001111000111100111 92598759
n &＃61; 00000000000000000000000000001000 8
n - 1&＃61; 00000000000000000000000000000111 7
index&＃61;(n - 1) & hash 00000000000000000000000000000111 7&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61; hash(abcdefg) &＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
key abcdefg
h&＃61;key.hashCode() 10111000000110010111010001100100 -1206291356
rh&＃61;h>>>16 00000000000000001011100000011001 47129
hash(abcdefg)&＃61;-1206268803
hash&＃61;h ^ rh 10111000000110011100110001111101 -1206268803
n &＃61; 00000000000000000000000000001000 8
n - 1&＃61; 00000000000000000000000000000111 7
index&＃61;(n - 1) & hash 00000000000000000000000000000101 5

算法图解:

源码分析:

/*** Returns the value to which the specified key is mapped,* or {&＃64;code null} if this map contains no mapping for the key.**

More formally, if this map contains a mapping from a key* {&＃64;code k} to a value {&＃64;code v} such that {&＃64;code (key&＃61;&＃61;null ? k&＃61;&＃61;null :* key.equals(k))}, then this method returns {&＃64;code v}; otherwise* it returns {&＃64;code null}. (There can be at most one such mapping.)**

A return value of {&＃64;code null} does not necessarily* indicate that the map contains no mapping for the key; it&＃39;s also* possible that the map explicitly maps the key to {&＃64;code null}.* The {&＃64;link #containsKey containsKey} operation may be used to* distinguish these two cases.** &＃64;see #put(Object, Object)*/public V get(Object key) {Node e;return (e &＃61; getNode(hash(key), key)) &＃61;&＃61; null ? null : e.value;}/*** Implements Map.get and related methods** &＃64;param hash hash for key* &＃64;param key the key* &＃64;return the node, or null if none*/final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k;if ((tab &＃61; table) !&＃61; null && (n &＃61; tab.length) > 0 &&(first &＃61; tab[(n - 1) & hash]) !&＃61; null) { // index &＃61; (n - 1) & hashif (first.hash &＃61;&＃61; hash && // always check first node((k &＃61; first.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))return first;if ((e &＃61; first.next) !&＃61; null) {if (first instanceof TreeNode)return ((TreeNode)first).getTreeNode(hash, key);do {if (e.hash &＃61;&＃61; hash &&((k &＃61; e.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))return e;} while ((e &＃61; e.next) !&＃61; null);}}return null;}


HashMap 中的 tableSizeFor() 方法详解

输入: int cap;
返回: n &＃61; tableSizeFor(cap)
其中, n % 2 &＃61;&＃61;0, and cap <&＃61;n.

/*** Returns a power of two size for the given target capacity.*/static final int tableSizeFor(int cap) {// 先 cap 减 1int n &＃61; cap - 1;n |&＃61; n >>> 1;n |&＃61; n >>> 2;n |&＃61; n >>> 4;n |&＃61; n >>> 8;n |&＃61; n >>> 16;return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1; // 再加 1}


我们来运行测试一下:

&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(2)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 2
n &＃61; cap - 1 00000000000000000000000000000001
n &＃61; n | (n >>> 1) 00000000000000000000000000000001
n &＃61; n | (n >>> 2) 00000000000000000000000000000001
n &＃61; n | (n >>> 4) 00000000000000000000000000000001
n &＃61; n | (n >>> 8) 00000000000000000000000000000001
n &＃61; n | (n >>> 16) 00000000000000000000000000000001
tableSizeFor &＃61; 2
2
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(5)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 5
n &＃61; cap - 1 00000000000000000000000000000100
n &＃61; n | (n >>> 1) 00000000000000000000000000000110
n &＃61; n | (n >>> 2) 00000000000000000000000000000111
n &＃61; n | (n >>> 4) 00000000000000000000000000000111
n &＃61; n | (n >>> 8) 00000000000000000000000000000111
n &＃61; n | (n >>> 16) 00000000000000000000000000000111
tableSizeFor &＃61; 8
8
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(10)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 10
n &＃61; cap - 1 00000000000000000000000000001001
n &＃61; n | (n >>> 1) 00000000000000000000000000001101
n &＃61; n | (n >>> 2) 00000000000000000000000000001111
n &＃61; n | (n >>> 4) 00000000000000000000000000001111
n &＃61; n | (n >>> 8) 00000000000000000000000000001111
n &＃61; n | (n >>> 16) 00000000000000000000000000001111
tableSizeFor &＃61; 16
16
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(25)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 25
n &＃61; cap - 1 00000000000000000000000000011000
n &＃61; n | (n >>> 1) 00000000000000000000000000011100
n &＃61; n | (n >>> 2) 00000000000000000000000000011111
n &＃61; n | (n >>> 4) 00000000000000000000000000011111
n &＃61; n | (n >>> 8) 00000000000000000000000000011111
n &＃61; n | (n >>> 16) 00000000000000000000000000011111
tableSizeFor &＃61; 32
32
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(58)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 58
n &＃61; cap - 1 00000000000000000000000000111001
n &＃61; n | (n >>> 1) 00000000000000000000000000111101
n &＃61; n | (n >>> 2) 00000000000000000000000000111111
n &＃61; n | (n >>> 4) 00000000000000000000000000111111
n &＃61; n | (n >>> 8) 00000000000000000000000000111111
n &＃61; n | (n >>> 16) 00000000000000000000000000111111
tableSizeFor &＃61; 64
64
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(100)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 100
n &＃61; cap - 1 00000000000000000000000001100011
n &＃61; n | (n >>> 1) 00000000000000000000000001110011
n &＃61; n | (n >>> 2) 00000000000000000000000001111111
n &＃61; n | (n >>> 4) 00000000000000000000000001111111
n &＃61; n | (n >>> 8) 00000000000000000000000001111111
n &＃61; n | (n >>> 16) 00000000000000000000000001111111
tableSizeFor &＃61; 128
128
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(896)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 896
n &＃61; cap - 1 00000000000000000000001101111111
n &＃61; n | (n >>> 1) 00000000000000000000001111111111
n &＃61; n | (n >>> 2) 00000000000000000000001111111111
n &＃61; n | (n >>> 4) 00000000000000000000001111111111
n &＃61; n | (n >>> 8) 00000000000000000000001111111111
n &＃61; n | (n >>> 16) 00000000000000000000001111111111
tableSizeFor &＃61; 1024
1024
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;tableSizeFor(1073741000)&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
cap &＃61; 1073741000
n &＃61; cap - 1 00111111111111111111110011000111
n &＃61; n | (n >>> 1) 00111111111111111111111011100111
n &＃61; n | (n >>> 2) 00111111111111111111111111111111
n &＃61; n | (n >>> 4) 00111111111111111111111111111111
n &＃61; n | (n >>> 8) 00111111111111111111111111111111
n &＃61; n | (n >>> 16) 00111111111111111111111111111111
tableSizeFor &＃61; 1073741824
1073741824

参考资料

https://blog.csdn.net/fan2012huan/article/details/51097331
https://www.jianshu.com/p/cbe3f22793be
https://www.jianshu.com/p/dbbecc36200d

国内第一Kotlin 开发者社区公众号&＃xff0c;主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界&＃xff0c;越需要宁静的思考。