美文网首页
2018-04-26(hashmap对数组长度取模)

2018-04-26(hashmap对数组长度取模)

作者: MiaLing007 | 来源:发表于2018-04-26 15:51 被阅读0次

    在学习hashmap原码时候,发现一个很有趣的事情,
    hashmap是由数组和链表组成,而在put时候首先要确定key应该插入到数组中位子
    之前学习时候记得是用key的hashcode对数组长度取模,也就是用key.hashcode() % length

    但是今天查看原码发现并不是像我想的那么通过key.hashcode() % length该方法确定数组中位置

    而是采用如下代码

     static int indexFor(int h, int length) {
            return h & (length-1);
        }
    

    当时看到该方法就很奇怪,为什么不是我理解的方式呢?
    按道理不应该是如下代码吗

     static int indexFor(int h, int length) {
            return h % length;
        }
    

    后来发现原来 h & (length-1) 和 h % length 在某种情况下是等价的。

    测试一下

        public static void main(String args[]) {
            System.out.println("19 & 15 = " + (19 & 15));
            System.out.println("19 % 16 = " + (19 % 16));
            
            System.out.println("30 & 15 = " + (30 & 15));
            System.out.println("30 % 16 = " + (30 % 16));
            
            
            System.out.println("25 & 7 = " + (25 & 7));
            System.out.println("25 % 8 = " + (25 % 8));
            
            
            System.out.println("25 & 9 = " + (25 & 9));
            System.out.println("25 % 10 = " + (25 % 10));
        }
    

    运算结果如下:

    19 & 15 = 3
    19 % 16 = 3
    30 & 15 = 14
    30 % 16 = 14
    25 & 7 = 1
    25 % 8 = 1
    25 & 9 = 9
    25 % 10 = 5
    

    通过测试我们发现如果
    k & (len -1) 和 k % len 加入len为2的n次幂时,他们计算结果是相同的。
    而我们知道hashmap的初始容量为16, 每次扩容都是len*2。 所以hash的容量肯定是2的n次幂,所以用return h & (length-1)该方法计算也就相当于对容量取模

    相关文章

      网友评论

          本文标题:2018-04-26(hashmap对数组长度取模)

          本文链接:https://www.haomeiwen.com/subject/oooplftx.html