HashMap的容量为什么要设置为2的次幂

2021-05-17 14:59发布

站内问答 / 基础入门
3484 11 16
发送
11条回答
不不就不
1楼 · 2021-05-18 19:42.采纳回答

（1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。 (n - 1) & hash实际上是计算出 key 在 tab 中索引位置，当key的hash没有冲突时，key在HashMap存储的位置就是匹配的node中的第一个节点。如果hash有冲突，就会在node里面节点中查询，直至匹配到相等的key。

   (2)因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011） 当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1， 例如 00001111 & 10000011 = 00000011

这样做有2个好处  

1,运算速度快，至少比%取模运算块

2, 能保证 索引值 肯定在 capacity 中，不会超出数组长度 (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

小橘子
2楼 · 2021-05-17 15:43
1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。

(n - 1) & hash实际上是计算出 key 在 tab 中索引位置，当key的hash没有冲突时，key在HashMap存储的位置就是匹配的node中的第一个节点。如果hash有冲突，就会在node里面节点中查询，直至匹配到相等的key。


Danke - 四有青年
3楼 · 2021-05-17 16:21

理论上，扩容倍数用多少都行，1.5， 2.5 ，3.5都可以的，都能实现HashMap。实际上，HashMap选用了2倍，是为了做一个优化。

pipi雪
4楼 · 2021-05-17 22:02

HashMap：为什么容量总是为2的次幂

HashMap是根据key的hash值决策key放入到哪个桶（bucket）中，通过 tab=[(n - 1) & hash] 公式计算得出。其中tab是一个哈希表


1. 为什么要保证 capacity 是2的次幂呢？

（1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。

(n - 1) & hash实际上是计算出 key 在 tab 中索引位置，当key的hash没有冲突时，key在HashMap存储的位置就是匹配的node中的第一个节点。如果hash有冲突，就会在node里面节点中查询，直至匹配到相等的key。



（2）因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）

当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1，

例如 00001111 & 10000011 = 00000011


这样做有2个好处


&运算速度快，至少比%取模运算块

能保证 索引值 肯定在 capacity 中，不会超出数组长度

(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

2.为什么要通过 (n - 1) & hash 决定桶的索引呢？


（1）key具体应该在哪个桶中，肯定要和key挂钩的，HashMap顾名思义就是通过hash算法高效的把存储的数据查询出来，所以HashMap的所有get 和 set 的操作都和hash相关。

（2）既然是通过hash的方式，那么不可避免的会出现hash冲突的场景。hash冲突就是指 2个key 通过hash算法得出的哈希值是相等的。hash冲突是不可避免的，所以如何尽量避免hash冲突，或者在hash冲突时如何高效定位到数据的真实存储位置就是HashMap中最核心的部分。

（3）首先要提的一点是 HashMap 中 capacity 可以在构造函数中指定，如果不指定默认是2 的 (n = 4) 次方，即16。


public HashMap(int initialCapacity) {

    this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

1

2

3

（4）HashMap中的hash也做了比较特别的处理，(h = key.hashCode()) ^ (h >>> 16)。

先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。

实质上是把一个数的低16位与他的高16位做异或运算，因为在前面 (n - 1) & hash 的计算中，hash变量只有末x位会参与到运算。使高16位也参与到hash的运算能减少冲突。


例如1000000的二进制是 00000000 00001111 01000010 01000000

右移16位： 00000000 00000000 00000000 00001111

异或 00000000 00001111 01000010 01001111


static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

1

2

3

4

3.capacity 永远都是 2 次幂，那么如果我们指定 initialCapacity 不为 2次幂时呢，是不是就破坏了这个规则？

答案是不会的，HashMap的tableSizeFor方法做了处理，能保证n永远都是2次幂。


/**

 * Returns a power of two size for the given target capacity.

 */

static final int tableSizeFor(int cap) {

    //cap-1后，n的二进制最右一位肯定和cap的最右一位不同，即一个为0，一个为1，例如cap=17（00010001），n=cap-1=16（00010000）

    int n = cap - 1;

    //n = (00010000 | 00001000) = 00011000

    n |= n >>> 1;

    //n = (00011000 | 00000110) = 00011110

    n |= n >>> 2;

    //n = (00011110 | 00000001) = 00011111

    n |= n >>> 4;

    //n = (00011111 | 00000000) = 00011111

    n |= n >>> 8;

    //n = (00011111 | 00000000) = 00011111

    n |= n >>> 16;

    //n = 00011111 = 31

    //n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次方

    return (n < 0>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}



三岁奶猫
5楼 · 2021-05-18 11:13

因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）
当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1

想减肥的小徐
6楼 · 2021-05-18 14:58

因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1

好处:

&运算速度快，至少比%取模运算块

能保证 索引值 肯定在 capacity 中，不会超出数组长度

(16-1)&hash，计算的索引会落在[0,15]，不会越界 ,与运算的结果取决于hash值，这样只要保证hash是均匀散列的，也就是保证1均匀分布就能防止索引冲突。

杨晓春
7楼 · 2021-05-21 20:29

1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。

(n - 1) & hash实际上是计算出 key 在 tab 中索引位置，当key的hash没有冲突时，key在HashMap存储的位置就是匹配的node中的第一个节点。如果hash有冲突，就会在node里面节点中查询，直至匹配到相等的key。

（2）因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）

当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1，

例如 00001111 & 10000011 = 00000011


路小雨xiaoyu
8楼 · 2021-06-03 16:55

为了加快哈希计算以及减少哈希冲突

为什么可以加快计算？

我们都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算 hash(KEY) % 数组长度

但是！% 计算比 & 慢很多

所以用 & 代替 %，为了保证 & 的计算结果等于 % 的结果需要把 length 减 1

也就是 hash(KEY) & (length - 1)

这个 hash(KEY) 没什么可说的，调用 Object 里面的 native 方法完成计算，一般返回的是一个整数，至于是偶数还是奇数就不一定了

我做了一个小实验：

假设现在数组的长度：2 ^ 14 = 16384

String key = "zZ1!." 的 hash 值为 115398910

public static void main(String[] args) {
        String key = "zZ1!.";
        System.out.println(key.hashCode());// 115398910}

hash & (length - 1) = 115398910 & 16383 = 6398 （你可以使用电脑的计算机验证一下是不是对的）6398 的二进制是 ‭0001100011111110‬

hash % length = 115398910 384 = 6398

结果确实一样，但是 & 运算更快！

还有一个有意思的事就是：因为扩容为 2 的倍数，根据 hash 桶的计算方法，元素哈希值不变而通过 % 计算的方式会因为 length 的变化导致计算出来的 hash 桶的位置不断变化。数据一致在漂移，影响性能！！

为什么可以减少冲突？

假设现在数组的长度 length 可能是偶数也可能是奇数

length 为偶数时，length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。

例如 length = 4，length - 1 = 3, 3 的 二进制是 11
若此时的 hash 是 2，也就是 10，那么 10 & 11 = 10（偶数位置）
hash = 3，即 11 & 11 = 11 （奇数位置）

而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 hash & (length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间

length = 3， 3 - 1 = 2，他的二进制是 10
10 无论与什么树进行 & 运算，结果都是偶数

因此，length 取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

猫的想法不敢猜
9楼 · 2021-06-06 09:45

HashMap是根据key的hash值决策key放入到哪个桶（bucket）中，通过 tab=[(n - 1) & hash] 公式计算得出。其中tab是一个哈希表

（1）在get方法实现中，实际上是匹配链表中的 Node[] tab 中的数据。

(n - 1) & hash实际上是计算出 key 在 tab 中索引位置，当key的hash没有冲突时，key在HashMap存储的位置就是匹配的node中的第一个节点。如果hash有冲突，就会在node里面节点中查询，直至匹配到相等的key。

在这里插入图片描述

（2）因为 n 永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）

当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1，

例如 00001111 & 10000011 = 00000011


这样做有2个好处


&运算速度快，至少比%取模运算块

能保证 索引值 肯定在 capacity 中，不会超出数组长度

(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

————————————————

版权声明：本文为CSDN博主「Helloworld先生」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/u010841296/article/details/82832166

来源于网络，仅供网友们参考

1 2 下一页

相关问题推荐

  • java的话，自学很差，有什么办法能改善一下吗2020-03-11 11:20
    回答 156

    对于每一位才开始接触JAVA的新手来说，先不要管算法和数据结构，大多数简单的程序不需要用到算法和数据结构，所以当你真正需要时再去学习。编程一段时间以后，你就会知道在哪些地方用到他们。这时知道算法的名字并了解它们的功能，然后动手去实践。当我们在去...

  • 学习Java和Python哪个比较好就业2021-01-13 14:40
    回答 93

    2个都很好就业，更关键的是要学得到东西

  • 怎样获取map里面的所有key？JAVA应用 2021-05-06 09:24
    回答 12
    已采纳

    获取Map集合中所有的key可以通过map集合的keySet()方法获取例如:    Map map = new HashMap();    map.put(xx,xx); //存放数据    //.... 省略    Set set = map.keySet();    //可以通过迭代器进行测试    Iterator iter = set.iter...

  • Java学习结束就业薪水大概多少？2020-11-26 22:12
    回答 56
    已采纳

    不同年龄，不同掌握程度，学历，找工作城市，面试能力这是一个多方面影响的结果，如果是平均值的话，全国平均薪资14k左右

  • 目前JAVA学习要多久？自学能学会吗？2021-01-11 18:52
    回答 38

    具体学多久，根据自己的学习力，自律性、解决问题能力来决定若系统性学习，跟着讲师的节奏走，大概半年左右，有专业的讲师把课程进行规划，尽心系统学习，有问题，讲师会帮忙解决，学习的效率很高，避免了自学中出现各种问题解决不了，而耽误很多时间，可能会...

  • Idea卡顿如何解决？JAVA应用 2021-05-08 14:12
    回答 23
    已采纳

    （1）idea启动时会有两个快捷方式，安装完后默认生成在桌面的是32位的idea的快捷方式，如果我们使用这个快捷方式运行大项目，一般都会很卡。解决方法是找到idea的安装目录，然后进入bin文件夹，找到名称为idea64的应用程序，右键他生成桌面快捷方式。以后每次...

  • BIO与NIO、AIO的区别2020-05-19 15:59
    回答 4
    已采纳

    IO的方式通常分为几种，同步阻塞的BIO、同步非阻塞的NIO、异步非阻塞的AIO。一、BIO     在JDK1.4出来之前，我们建立网络连接的时候采用BIO模式，需要先在服务端启动一个ServerSocket，然后在客户端启动Socket来对服务端进行通信，默认情况下服务端需要...

  • Java方法的命名规则2021-04-06 19:07
    回答 31

    ava是一种区分字母的大小写的语言，所以我们在定义变量名的时候应该注意区分大小写的使用和一些规范，接下来我们简单的来讲讲Java语言中包、类、变量等的命名规范。(一)Package(包)的命名Package的名字应该都是由一个小写单词组成，例如com、xuetang9、compan...

  • 计算机小白求大佬解答2022-04-25 13:48
    回答 2

    public class Point {    private int x;    private int y;    public int getX() {        return x;    }    public void setX(int x) {        this.x = x;    }    public int getY() {        return y;    } ...

  • 单例模式的五种写法单例 2022-02-09 19:37
    回答 6

    经典版单例模式public class Singleton {        private static Singleton uniqueInstance;//利用一个静态常量来记录singleton类的唯一实例。     private Singleton() {     }     public static  Singleton getInstance()...

  • 哈希表的表长怎么算哈希表 2022-01-14 18:27
    回答 3

    哈希表的长度一般是定长的，在存储数据之前我们应该知道我们存储的数据规模是多大，应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大，那么就会浪费空间，因为我们跟不用不到那么大的空间来存储我们当前的数据规模；如果设计的太小，那么就会很容易发...

  • 举例JAVA中如何解析xml，不同方式有和优缺点？解析 2021-11-15 10:17
    回答 14

    1. DOM（Document Object Model)        DOM是用与平台和语言无关的方式表示XML文档的官方W3C标准。DOM是以层次结构组织的节点或信息片断的集合。这个层次结构允许开发人员在树中寻找特定信息。分析该结构通常需要加载整个文档和构造层次结构，然后才...

  • 异常处理中throws和throw的区别？异常处理机制 2021-11-11 09:39
    回答 19

    1)作用不同： throw用于程序员自行产生并抛出异常; throws用于声明在该方法内抛出了异常2) 使用的位置不同： throw位于方法体内部，可以作为单独语句使用; throws必须跟在方法参数列表的后面，不能单独使用。3)内容不同： throw抛出一个异常对象，且只能是...

  • Java异常处理try-catch-finally异常处理机制 2021-11-11 09:39
    回答 11

    基本执行过程如下：1)程序首先执行可能发生异常的try语句块。2)如果try语句没有出现异常则执行完后跳至finally语句块执行;3)如果try语句出现异常，则中断执行并根据发生的异常类型跳至相应的catch语句块执行处理。4)catch语句块可以有多个，分别捕获不同类型...

  • http状态码有那些？分别代表是什么意思？http协议 JAVA应用 2021-11-10 16:40
    回答 20

    100-199 用于指定客户端应相应的某些动作。 200-299 用于表示请求成功。 300-399 用于已经移动的文件并且常被包含在定位头信息中指定新的地址信息。 400-499 用于指出客户端的错误。 400 语义有误，当前请求无法被服务器理解。 401 当前请求需要用户验证...

  • 运行时异常与受检异常有何异同?异常处理机制 2021-11-10 09:22
    回答 16

    异常表示程序运行过程中可能出现的非正常状态，运行时异常表示虚拟机的通常操作中可能遇到的异常，是一种常见运行错误，只要程序设计得没有问题通常就不会发生。受检异常跟程序运行的上下文环境有关，即使程序设计无误，仍然可能因使用的问题而引发。Java编译...

没有解决我的问题，去提问