前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Java 8 HashMap 详解系列] 2.HashMap 中 Key 的 index 是怎样计算的?

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

作者头像
一个会写诗的程序员
发布2020-03-24 16:45:43
1.1K0
发布2020-03-24 16:45:43
举报
文章被收录于专栏:一个会写诗的程序员的博客

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);
    }

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

代码语言:javascript
复制
    public static final int index(int hash, int n) {
        return (n - 1) & hash;
    }

代码拆解:

代码语言:javascript
复制
    public static final int hash(Object key) {
        if (key == null) {
            return 0;
        }

        int h = key.hashCode();
        int rh = h >>> 16;
        out.println("===================== hash(" + key + ") ===========================");
        out.println("key                  \t\t" + key);
        out.println("h=key.hashCode()     \t\t" + toBinary(h) + "\t\t" + h);
        out.println("rh=h>>>16            \t\t" + toBinary(rh) + "\t\t" + rh);

        return h ^ rh;
    }

    public static final int index(int hash, int n) {
        out.println("hash=h ^ rh          \t\t" + toBinary(hash) + "\t\t" + hash);
        out.println("n    =               \t\t" + toBinary(n) + "\t\t" + (n));
        out.println("n - 1=               \t\t" + toBinary(n - 1) + "\t\t" + (n - 1));
        int index = (n - 1) & hash;
        out.println("index=(n - 1) & hash \t\t" + toBinary(index) + "\t\t" + index);
        out.println();
        return index;
    }

运行测试数据:

代码语言:javascript
复制
===================== 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<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { // index = (n - 1) & hash
            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 中的 tableSizeFor() 方法详解

输入: 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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2.HashMap 中 Key 的 index 是怎样计算的?
    • HashMap中的 table 是怎样确定数组索引位置的?
      • HashMap 中的 tableSizeFor() 方法详解
      • 参考资料
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档