本篇文章为你整理了HashMap的哈希函数为何用(n（hashmap为什么是o1）的详细内容，包含有hashmap 0.75为什么 hashmap为什么是o1 hashmap的哈希算法 hashmap为什么用数组 HashMap的哈希函数为何用(n，希望能帮助你了解 HashMap的哈希函数为何用(n。

　　在上一篇Java 中HashMap详解(含HashTable, ConcurrentHashMap)中提到在map.put(key, value)的过程中，计算完key的hash值， 是通过hash (n-1)来得出该元素在Node数组中的下标的，其中n是Node数组的长度。 其实我们更容易想到的是hash % n，这样刚好会得到0~n-1之间的数字，可以用作数组下标。那么为何此处是用的位运算呢？

　　先说结论。 这里有一个前提，那就是HashMap中Node数组的长度始终保持是2^n， 比如默认的16， 如果创建HashMap的时候指定了初始的capacity,而这个capacity可能不是2^n, 会在内部转化一下，得到一个大于这个capacity的最小的2^n的数字来初始化数组。 每次扩容的时候也是进行2倍的扩容。

　　在这个前提下，hash (n-1) 与hash % n 是等价的。 而位运算更快一些。

　　先来看一组数字：

　　
此处我们可以看到规律，2^m的二进制就是1的后面加上m个0, 而2^m -1的二进制就是0的后面加上m个1.

　　下面我们来看 hash % n（求余数）的运算：

　　首先看hash/n，由于n=2^m， 我们先看hash/2的情况，这样一来就简单了，因为我们都知道，二进制的情况下，一个数字除以2其实就是右移一位，在左边加一个0，右边移出去一位。如果觉得不好理解，就类比十进制的数字除以10的情况，是一样的。举一反三一下，hash/4的情况自然就是右移2位，由于n=2^m， 其实hash/n的操作就是右移m位。

　　右移之后我们得到的是hash/n的整除，那么余数呢？其实就是我们移出去的数字。

　　举个例子，假设hash = 18, n=4,我们知道18/4=4 , 18%4 =2,看看按照我们上面的运算是否会得到相同的结果：

　　18=10010， 4=2^2

　　
通过运算可以很容易的验证18/4 = 00100 = 4 ， 而18%4 = 10 = 2， 是正确的。

　　现在假设Node数组进行了扩容n=8，再来看一下：

　　
同样经过运算18 / 8 = 10 = 2, 18 % 8 = 10 = 2， 是正确的。

　　现在我们可以看到规律， hash % (2^m)的结果， 其实是就是hash这个数字二进制表达的最后m位（被移出去的m位）

　　而前面我们又知道2^m-1其实就是0后面加上m个1. 还用上面的例子，我们看一下18 (2^3-1)的运算：

　　
我们知道，任何数字与1做与运算，还是得到该数字；任何数字与0做与运算，都得0，那么hash (2^m-1) ，高位的都是零,只得到低位的m个数字，与上面计算的hash % (2^m)是一样的结果。

　　证明完成。

　　以上就是HashMap的哈希函数为何用(n（hashmap为什么是o1）的详细内容，想要了解更多 HashMap的哈希函数为何用(n的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。