HashMap中如何计算数组索引下标？

野性酷女 2023-10-05 14:38 16阅读 0赞

## [计算hash值的方法][hash] ##

对于key的hashCode做hash操作，无符号右移16位然后做异或运算。  
还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。  
集合中的初始化容量（必须是二的n次幂）

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

## HashMap中如何计算数组索引下标？ ##

hash值与数组长度减一做按位与运算得到数组下标索引

## 问题： 为什么必须是2的n次幂？如果输入值不是2的幂比如10会怎么样？ ##

举例分析：  
说明：按位与运算：相同的二进制数位上，都是1的时候，结果为1，否则为零。

例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

例如长度length为8时候，8是2的3次幂。二进制是：1000
    length-1 二进制运算：
    	1000
    -	   1
    ---------------------
         111
    如下所示：
    hash&(length-1)
    3   &(8    - 1)=3  
    	00000011  3 hash
    &   00000111  7 length-1
    ---------------------
    	00000011-----》3 数组下标
    	
    hash&(length-1)
    2 &  (8 -    1) = 2  
    	00000010  2 hash
    &   00000111  7 length-1
    ---------------------
    	00000010-----》2  数组下标
    说明：上述计算结果是不同位置上，不碰撞；

例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；

例如长度为9时候，3&(9-1)=0  2&(9-1)=0 ，都在0上，碰撞了；
    例如长度length为9时候，9不是2的n次幂。二进制是：00001001
    length-1 二进制运算：
    	1001
    -	   1
    ---------------------
        1000
    如下所示：
    hash&(length-1)
    3   &(9    - 1)=0  
    	00000011  3 hash
    &   00001000  8 length-1 
    ---------------------
    	00000000-----》0  数组下标
    	
    hash&(length-1)
    2 &  (9 -    1) = 2  
    	00000010 2 hash
    &   00001000 8 length-1 
    ---------------------
    	00000000-----》0  数组下标
    说明：上述计算结果都在0上，碰撞了；

## 总结： ##

1.  由上面可以看出，当我们根据key的hash确定其在数组的位置时，**如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突**。
2.  另一方面，一般我们可能会想通过 % 求余来确定位置，这样也可以，只不过性能不如 & 运算。而且当n是2的幂次方时：hash & (length - 1) == hash % length
3.  因此，HashMap 容量为2次幂的原因，**就是为了数据的的均匀分布，减少hash冲突**，毕竟hash冲突越大，代表数组中一个链的长度越大，这样的话会降低hashmap的性能
4.  如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字。

[hash]: https://blog.csdn.net/weixin_43811057/article/details/110287480

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java中ArrayIndexOutOfBoundsException：数组下标越界

`ArrayIndexOutOfBoundsException` 是 Java 中一个常见的运行时异常，它发生在试图访问数组的某个不存在的索引位置时。例如： ```java

àì夳堔傛蜴生んèń/ 2024年12月12日 04:03/ 0 赞/ 83 阅读

相关 ArrayIndexOutOfBoundsException: 数组下标越界

`ArrayIndexOutOfBoundsException` 是Java中一种常见的运行时异常，主要由于尝试访问一个不存在于数组中的索引位置而引发。例如： ```jav

向右看齐/ 2024年11月15日 02:18/ 0 赞/ 108 阅读

相关新手疑惑：Java中如何处理数组下标越界？

在Java中，数组下标是整数类型，因此你不能使用超出数组长度的值作为下标。例如，如果你有一个包含10个元素的数组，下标的范围应该是0（包括）到9（不包括）。如果你尝试访问`

水深无声/ 2024年09月19日 10:09/ 0 赞/ 117 阅读

相关环形数组：介绍、应用、下标计算

一、环形数组介绍对于普通数组来说，头尾的下标都是固定的，头下标为0,尾下标为length-1。而环形数组(circular array)通常使用两个额外的数字去标识

╰+攻爆jí腚メ/ 2024年03月25日 16:47/ 0 赞/ 101 阅读

相关 HashMap中如何计算数组索引下标？

[计算hash值的方法][hash] 对于key的hashCode做hash操作，无符号右移16位然后做异或运算。还有平方取中法，伪随机数法和取余数法。这三种效率都

野性酷女/ 2023年10月05日 14:38/ 0 赞/ 17 阅读

相关 php输出数组下标

　　项目使用PHP语言开发，其中用到了MONGO DB存储;MONGO DB里的数据是强类型，PHP里的数据是弱类型，上周五我在MONGODB里查询一个数据总是找不到，最后发现

素颜马尾好姑娘i/ 2023年09月24日 08:15/ 0 赞/ 118 阅读

相关 php数组下标不规则,PHP数组下标类型陷阱

项目使用PHP语言开发，其中用到了MONGO DB存储;MONGO DB里的数据是强类型，PHP里的数据是弱类型，上周五我在MONGODB里查询一个数据总是找不到，最后发现问题

忘是亡心i/ 2022年11月18日 01:27/ 0 赞/ 228 阅读

相关数组与指针-下标索引操作符的交换性

内建的下标索引操作符的可交换性，不管是数组还是指针，它们的下标索引表达式都可以“反过来写”。像这样：正常写法 int ar\[5\]; int \p = ar;求 a\

╰半橙微兮°/ 2022年08月12日 00:27/ 0 赞/ 42 阅读

相关数组下标重载

可以用类定义数组，其实数组的个数就是对象实例化的个数，如下： include <iostream> using namespace std; clas

ゞ浴缸里的玫瑰/ 2022年06月09日 11:20/ 0 赞/ 274 阅读

相关 [work] shell中数组下标访问

shell中数组的下标默认是从0开始的 1。将字符串放在数组中，获取其长度 \!/bin/bash str="a b --n d" array=($str) l

ゝ一世哀愁。/ 2022年05月03日 16:30/ 0 赞/ 414 阅读