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

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

  •  
  •   ukipoi · 169 天前 · 1119 次点击
    这是一个创建于 169 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  169 天前

    以下是我做的测试

    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
        1
    tchqiq   169 天前
    可以这么认为.hash 是用高 16 位和低 16 位异或得到.所以更为"随机"
        2
    imzhoukunqiang   169 天前
    n 是之前获取的 table 的长度,n 的值总是 2 的次方(16/32/64/128...),(n-1)转换成二进制低位全部是 1,和 hash 值&操作相当于对 n 取余。
        3
    ukipoi   169 天前
    @imzhoukunqiang 请教一下为什么 n 的值总是 2 的次方呢?关于我的 第 1 条附言 希望能解答一下
        4
    neuthself   169 天前
    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 运算中,同时不会有太大的开销。
        5
    neuthself   169 天前
    并且由于每次扩容是上一次的两倍。Jdk1.8 中,扩容之后元素要么是在原来的位置,要么实在原来的位置再移动 2 次幂的位置。
        6
    imzhoukunqiang   169 天前   ♥ 1
    @ukipoi table 的 length ≠ map 的 size,此时 table 的 size 应该是 16 吧(默认容量 没记错的话),,hashmap 中 table 长度是由 tableSizeFor(int cap)计算得来的。这个方法总会返回最接近且大于等于 cap 的 2 的幂。 使用这个方法取余的原因可以参照 4L 说的,效率问题。
        7
    Caturra   169 天前 via Android
    @ukipoi 不严谨的说下自己的想法,n 保持 2 的幂可以保证 n-1 永远是二进制全 1,符合原来算法的实现(&hash 那一段,替代性能低下的 mod 操作),其次,假设( n-1 )&hash 在扩容前算法足够均匀( hash 的处理是和自己的高 16 位取 xor ),那下一个 index 比原来的 index 在二进制上只是多了最高位的 0 和 1 的区别,也就是只要重新分布一半数目的 index 即可
        8
    limuyan44   169 天前 via Android
    就是为了扩容不二次 hash 而已
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   953 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 21:39 · PVG 05:39 · LAX 13:39 · JFK 16:39
    ♥ Do have faith in what you're doing.