V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ukipoi
V2EX  ›  Java

Java HashMap 里,在 getNode 方法中关于&的一个问题。

  •  
  •   ukipoi · 2019-06-04 13:25:03 +08:00 · 2394 次点击
    这是一个创建于 1990 天前的主题,其中的信息可能已经有所发展或是发生改变。

    HashMap.java里第 569 行,tab[(n - 1) & hash]&的意思是随机取一个小于等于 n-1 的值吗?

    第 1 条附言  ·  2019-06-04 14:02:42 +08:00

    以下是我做的测试

    Map<Integer, Integer> map = new HashMap<>();
    map.put(3, 11);
    map.put(8, 12);
    map.put(1, 13);
    System.out.println(map.containsKey(8));
    

    我传入的值是8,debug看到getNdoe里hash是8,key是8。
    我这里tab.length应该是3吧
    为什么first = tab[(n - 1) & hash]的first得到的结果是tab[2]//"8" -> "123"呢?
    2&8的值是0才对啊

    8 条回复    2019-06-04 16:37:39 +08:00
    tchqiq
        1
    tchqiq  
       2019-06-04 13:39:40 +08:00
    可以这么认为.hash 是用高 16 位和低 16 位异或得到.所以更为"随机"
    cookii
        2
    cookii  
       2019-06-04 13:42:50 +08:00
    n 是之前获取的 table 的长度,n 的值总是 2 的次方(16/32/64/128...),(n-1)转换成二进制低位全部是 1,和 hash 值&操作相当于对 n 取余。
    ukipoi
        3
    ukipoi  
    OP
       2019-06-04 14:03:57 +08:00
    @imzhoukunqiang 请教一下为什么 n 的值总是 2 的次方呢?关于我的 第 1 条附言 希望能解答一下
    neuthself
        4
    neuthself  
       2019-06-04 14:07:55 +08:00
    jdk1.7 中 HashMap 通过 h & (length-1) 来得到数组位置,而底层数组的长度总是为 2 的 n 次方。当 length 为 2 的 n 次方时,h & (length-1) 运算等价与对 length 取模,也就是 h % length,但是 & 比 % 具有更高的效率。

    jdk1.8 中 HashMap 优化了高位运算的算法,通过 hashcode() 的高 16 位异或低 16 位实现的: (h = key.hashCode()) ^ (h >>> 16) ,这样做可以在数组 table 的 length 比较小的时候,也能保证考虑到高低 Bit 都参与到 hash 运算中,同时不会有太大的开销。
    neuthself
        5
    neuthself  
       2019-06-04 14:08:42 +08:00
    并且由于每次扩容是上一次的两倍。Jdk1.8 中,扩容之后元素要么是在原来的位置,要么实在原来的位置再移动 2 次幂的位置。
    cookii
        6
    cookii  
       2019-06-04 14:22:19 +08:00   ❤️ 1
    @ukipoi table 的 length ≠ map 的 size,此时 table 的 size 应该是 16 吧(默认容量 没记错的话),,hashmap 中 table 长度是由 tableSizeFor(int cap)计算得来的。这个方法总会返回最接近且大于等于 cap 的 2 的幂。 使用这个方法取余的原因可以参照 4L 说的,效率问题。
    Caturra
        7
    Caturra  
       2019-06-04 14:22:48 +08:00 via Android
    @ukipoi 不严谨的说下自己的想法,n 保持 2 的幂可以保证 n-1 永远是二进制全 1,符合原来算法的实现(&hash 那一段,替代性能低下的 mod 操作),其次,假设( n-1 )&hash 在扩容前算法足够均匀( hash 的处理是和自己的高 16 位取 xor ),那下一个 index 比原来的 index 在二进制上只是多了最高位的 0 和 1 的区别,也就是只要重新分布一半数目的 index 即可
    limuyan44
        8
    limuyan44  
       2019-06-04 16:37:39 +08:00 via Android
    就是为了扩容不二次 hash 而已
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1863 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:36 · PVG 00:36 · LAX 08:36 · JFK 11:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.