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

发布于

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

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

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

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

代码语言：javascript
复制
    /* ---------------- 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'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);
}</code></pre></div></div><p>然后, 数组元素的下标算法是:</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>javascript</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-javascript"><code class="language-javascript" style="margin-left:0">    public static final int index(int hash, int n) {
    return (n - 1) &amp; hash;
}</code></pre></div></div><p>代码拆解:</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>javascript</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-javascript"><code class="language-javascript" style="margin-left:0">    public static final int hash(Object key) {
    if (key == null) {
        return 0;
    }

    int h = key.hashCode();
    int rh = h &gt;&gt;&gt; 16;
    out.println(&#34;===================== hash(&#34; + key + &#34;) ===========================&#34;);
    out.println(&#34;key                  \t\t&#34; + key);
    out.println(&#34;h=key.hashCode()     \t\t&#34; + toBinary(h) + &#34;\t\t&#34; + h);
    out.println(&#34;rh=h&gt;&gt;&gt;16            \t\t&#34; + toBinary(rh) + &#34;\t\t&#34; + rh);

    return h ^ rh;
}

public static final int index(int hash, int n) {
    out.println(&#34;hash=h ^ rh          \t\t&#34; + toBinary(hash) + &#34;\t\t&#34; + hash);
    out.println(&#34;n    =               \t\t&#34; + toBinary(n) + &#34;\t\t&#34; + (n));
    out.println(&#34;n - 1=               \t\t&#34; + toBinary(n - 1) + &#34;\t\t&#34; + (n - 1));
    int index = (n - 1) &amp; hash;
    out.println(&#34;index=(n - 1) &amp; hash \t\t&#34; + toBinary(index) + &#34;\t\t&#34; + index);
    out.println();
    return index;
}</code></pre></div></div><p>运行测试数据:</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>javascript</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-javascript"><code class="language-javascript" style="margin-left:0">===================== hash(a) ===========================



key                         a

h=key.hashCode()            00000000000000000000000001100001        97

rh=h>>>16                   00000000000000000000000000000000        0

hash(a)=97

hash=h ^ rh                 00000000000000000000000001100001        97

n    =                      00000000000000000000000000000001        1

n - 1=                      00000000000000000000000000000000        0

index=(n - 1) & hash        00000000000000000000000000000000        0


===================== hash(b) ===========================

key                         b

h=key.hashCode()            00000000000000000000000001100010        98

rh=h>>>16                   00000000000000000000000000000000        0

hash(b)=98

hash=h ^ rh                 00000000000000000000000001100010        98

n    =                      00000000000000000000000000000010        2

n - 1=                      00000000000000000000000000000001        1

index=(n - 1) & hash        00000000000000000000000000000000        0


===================== hash(abc) ===========================

key                         abc

h=key.hashCode()            00000000000000010111100001100010        96354

rh=h>>>16                   00000000000000000000000000000001        1

hash(abc)=96355

hash=h ^ rh                 00000000000000010111100001100011        96355

n    =                      00000000000000000000000000000100        4

n - 1=                      00000000000000000000000000000011        3

index=(n - 1) & hash        00000000000000000000000000000011        3


===================== hash(abcde) ===========================

key                         abcde

h=key.hashCode()            00000101100001001111010001100011        92599395

rh=h>>>16                   00000000000000000000010110000100        1412

hash(abcde)=92598759

hash=h ^ rh                 00000101100001001111000111100111        92598759

n    =                      00000000000000000000000000001000        8

n - 1=                      00000000000000000000000000000111        7

index=(n - 1) & hash        00000000000000000000000000000111        7


===================== hash(abcdefg) ===========================

key                         abcdefg

h=key.hashCode()            10111000000110010111010001100100        -1206291356

rh=h>>>16                   00000000000000001011100000011001        47129

hash(abcdefg)=-1206268803

hash=h ^ rh                 10111000000110011100110001111101        -1206268803

n    =                      00000000000000000000000000001000        8

n - 1=                      00000000000000000000000000000111        7

index=(n - 1) & hash        00000000000000000000000000000101        5

算法图解:

源码分析:

代码语言：javascript
复制
    /**

* 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;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}


/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node&lt;K,V&gt; getNode(int hash, Object key) {
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;
    if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
        (first = tab[(n - 1) &amp; hash]) != null) { // index = (n - 1) &amp; hash
        if (first.hash == hash &amp;&amp; // always check first node
            ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}</code></pre></div></div><h3 id="25n5t" name="HashMap-%E4%B8%AD%E7%9A%84-tableSizeFor()-%E6%96%B9%E6%B3%95%E8%AF%A6%E8%A7%A3">HashMap 中的 tableSizeFor() 方法详解</h3><p>输入: int  cap;



返回: n = tableSizeFor(cap)

其中, n % 2 ==0, and cap <=n.
代码语言：javascript
复制
    /**

* Returns a power of two size for the given target capacity.

*/

static final int tableSizeFor(int cap) {

// 先 cap 减 1

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; // 再加 1

}
我们来运行测试一下:
代码语言：javascript
复制
===============tableSizeFor(2)==================

cap = 2

n = cap - 1         00000000000000000000000000000001

n = n | (n >>> 1)   00000000000000000000000000000001

n = n | (n >>> 2)   00000000000000000000000000000001

n = n | (n >>> 4)   00000000000000000000000000000001

n = n | (n >>> 8)   00000000000000000000000000000001

n = n | (n >>> 16)  00000000000000000000000000000001

tableSizeFor = 2

2

===============tableSizeFor(5)==================

cap = 5

n = cap - 1         00000000000000000000000000000100

n = n | (n >>> 1)   00000000000000000000000000000110

n = n | (n >>> 2)   00000000000000000000000000000111

n = n | (n >>> 4)   00000000000000000000000000000111

n = n | (n >>> 8)   00000000000000000000000000000111

n = n | (n >>> 16)  00000000000000000000000000000111

tableSizeFor = 8

8

===============tableSizeFor(10)==================

cap = 10

n = cap - 1         00000000000000000000000000001001

n = n | (n >>> 1)   00000000000000000000000000001101

n = n | (n >>> 2)   00000000000000000000000000001111

n = n | (n >>> 4)   00000000000000000000000000001111

n = n | (n >>> 8)   00000000000000000000000000001111

n = n | (n >>> 16)  00000000000000000000000000001111

tableSizeFor = 16

16

===============tableSizeFor(25)==================

cap = 25

n = cap - 1         00000000000000000000000000011000

n = n | (n >>> 1)   00000000000000000000000000011100

n = n | (n >>> 2)   00000000000000000000000000011111

n = n | (n >>> 4)   00000000000000000000000000011111

n = n | (n >>> 8)   00000000000000000000000000011111

n = n | (n >>> 16)  00000000000000000000000000011111

tableSizeFor = 32

32

===============tableSizeFor(58)==================

cap = 58

n = cap - 1         00000000000000000000000000111001

n = n | (n >>> 1)   00000000000000000000000000111101

n = n | (n >>> 2)   00000000000000000000000000111111

n = n | (n >>> 4)   00000000000000000000000000111111

n = n | (n >>> 8)   00000000000000000000000000111111

n = n | (n >>> 16)  00000000000000000000000000111111

tableSizeFor = 64

64

===============tableSizeFor(100)==================

cap = 100

n = cap - 1         00000000000000000000000001100011

n = n | (n >>> 1)   00000000000000000000000001110011

n = n | (n >>> 2)   00000000000000000000000001111111

n = n | (n >>> 4)   00000000000000000000000001111111

n = n | (n >>> 8)   00000000000000000000000001111111

n = n | (n >>> 16)  00000000000000000000000001111111

tableSizeFor = 128

128

===============tableSizeFor(896)==================

cap = 896

n = cap - 1         00000000000000000000001101111111

n = n | (n >>> 1)   00000000000000000000001111111111

n = n | (n >>> 2)   00000000000000000000001111111111

n = n | (n >>> 4)   00000000000000000000001111111111

n = n | (n >>> 8)   00000000000000000000001111111111

n = n | (n >>> 16)  00000000000000000000001111111111

tableSizeFor = 1024

1024

===============tableSizeFor(1073741000)==================

cap = 1073741000

n = cap - 1         00111111111111111111110011000111

n = n | (n >>> 1)   00111111111111111111111011100111

n = n | (n >>> 2)   00111111111111111111111111111111

n = n | (n >>> 4)   00111111111111111111111111111111

n = n | (n >>> 8)   00111111111111111111111111111111

n = n | (n >>> 16)  00111111111111111111111111111111

tableSizeFor = 1073741824

1073741824
参考资料
https://blog.csdn.net/fan2012huan/article/details/51097331

https://www.jianshu.com/p/cbe3f22793be

https://www.jianshu.com/p/dbbecc36200d
#hashmap#https#网络安全#编程算法