在元素的装载数量明确的时候HashMap的大小应该如何选择。

本是古典何须时尚 2021-06-22 15:36 218阅读 0赞

今天看到美团招聘给出了一道小题目，关于HashMap的性能问题。问题如下：

java hashmap，如果确定只装载100个元素，new HashMap(?)多少是最佳的，why？

要回答这个问题，首先得知道影响HashMap性能的参数有哪些。咱们翻翻JDK。

在JDK6中是这么描述的：

HashMap的实例有两个参数影响其性能：初始容量和加载因子。

首先我们来看初始容量和加载因子的定义。

容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。

当哈希表中条目的数目超过 容量乘加载因子 的时候，则要对该哈希表进行rehash操作，从而哈希表将具有大约两倍的桶数。（以上摘自JDK6）

HashMap默认的加载因子是0.75 .它在时间和空间成本上寻求了一种折中。

回到本文的问题。根据JDK中的描述，如果这个只装载100个元素的HashMap没有特殊的用途，那么为了在时间和空间上达到最佳性能，HashMap的初始容量可以设为

100/0.75 = 133.33。为了防止rehash，向上取整，为134。

但是还有另外一个问题，就是hash碰撞的问题。如果我们将HashMap的容量设置为134，那么如何保证其中的哈希碰撞会比较少呢？

除非重写hashcode()方法，否则，似乎没有办法保证。

那么这里不得不提HashMap如何为元素选择下标的方法了。

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

其中h为key哈希后得到的值，length为哈希表的长度。

134-1 = 128 + 6 -1；

那么 length-1的二进制值的最后3位为101；

假设这100个装载的元素中他们的key在哈希后有得到两个值（h），他们的二进制值除了低3位之外都相同，而第一个值的低3位为011，第二个值的低3位为001；

这时候进行java的&预算，011 & 101 = 001 ；001 & 101 = 001；

他们的值相等了，那么这个时候就会发生哈希碰撞。

除此之外还有一个更加严重的问题，由于在101中第二位是0，那么，无论我们的key在哈希运算之后得到的值h是什么，那么在&运算之后，得到的结果的倒数第二位均为0；

因此，对于hash表所有下标的二进制的值而言，只要低位第二位的值为1，（例如0010,0011,0111,1111）那么这个下标所代表的桶将一直是空的，因为代码中的&运算的结果永远不会产生低位第二位为1的值。这就大大地浪费了空间，同时还增加了哈希碰撞的概率。这无疑会降低HashMap的效率。

那么如何才能减少这种浪费呢？最佳的方法当然是让length-1的二进制值全部位均为1.那么length的值是多少合适呢？

没错，length=2^n。

只要将hash表的长度设为2的N次方，那么，所有的哈希桶均有被使用的可能。

再次回到美团提出的问题，与134最靠近的2^n无疑是128。

如果只修改HashMap的长度而不修改HashMap的加载因子的话，HashMap会进行rehash操作，这是一个代价很大的操作，所以不可取。

那么应该选择的就应该是256。

而由于空间加大和有效利用哈希桶，这时的哈希碰撞将大大降低，因此HashMap的读取效率会比较高。

所以，最后结论就是：HashMap的大小应该设置为256。

结果的补充：其实在Java中，无论你的HashMap(x)中的x设置为多少，HashMap的大小都是2^n。2^n是大于x的第一个数。因为HashMap的初始化代码中有以下这行代码：

int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;

但是这就带来了一个问题，如果x=100，那么HashMap的初始大小应该是128.但是100/128=0.78，已经超过默认加载因子的大小了。因此会resize一次，变成256。所以最好的结果还是256。

最后发个参考链接：http://www.iteye.com/topic/539465

发表评论取消回复

表情：

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

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

相关阅读

相关如何明确的选择IT方向？

一、明确目标作为初学者，先树立自己目标，找到自己感兴趣的IT行业，IT行业分很多种，听的最多次的无非不就是web前端工、程序员、后端、大数据、网络运维等。学习知...

冷不防/ 2024年04月17日 11:42/ 0 赞/ 65 阅读

相关如何在 Python 中获取列表中的元素数量？

问：如何获取列表 items 中的元素数？ items = ["apple", "orange", "banana"] There are

迷南。/ 2024年03月29日 14:45/ 0 赞/ 90 阅读

相关如何选择适合网站的图标大小？

网站图标（“收藏夹”和“图标”的组合）是用于快速识别网站的小图像。这些可以在浏览器选项卡的左侧找到，也可以在移动设备的主屏幕上作为触摸图标找到。要为网站制作网站图标，您可以

Love The Way You Lie/ 2024年03月17日 13:24/ 0 赞/ 54 阅读

相关 jquery在选择元素的时候，可以写成var div=$("div")

$(document).ready(function()\{ $("button").click(function()\{ var div=$("div")

港控/mmm°/ 2022年09月22日 11:48/ 0 赞/ 133 阅读

相关 SpringBoot启动的时候获取Controller的数量

昨天在一个技术群里看到一个话题，在Spring容器启动的时候，获取Controller的数量，并打印到控制台，这个问题没仔细想过，刚才花了几分钟写了出来，主要是通过Applic

╰半橙微兮°/ 2022年05月23日 11:09/ 0 赞/ 148 阅读

相关 CSS的:nth-child选择器：如何选择相同元素中指定的元素

现象： CSS中出现多个相同元素需要获取，依次给所有元素写class或者id又太麻烦方法：使用CSS的:nth-child选择器一：首先写一个div容器里面

深碍√TFBOYSˉ_/ 2022年05月21日 03:22/ 0 赞/ 402 阅读

相关当你想进行简单性能测试监控的时候应该如何选择监控命令？

此文已由作者赵慧莉授权网易云社区发布。欢迎访问[网易云社区][Link 1]，了解更多网易技术产品运营经验。一、前言在进行性能测试前，有些参数需

￡神魔★判官ぃ/ 2022年04月16日 03:35/ 0 赞/ 140 阅读

相关在元素的装载数量明确的时候HashMap的大小应该如何选择。

HashMap的性能问题。问题如下： java hashmap，如果确定只装载100个元素，new HashMap(?)多少是最佳的，why？要回答这个问题，首先得知

缺乏、安全感/ 2021年09月29日 10:22/ 0 赞/ 200 阅读

相关 G1的Region是如何划分数量和大小的？

> 说明：JDK7和JDK8的Region划分实现略有不同（差异非常小，且只有-Xmx和-Xms的值不一样才有区别），本篇文章讲解的是JDK8中Region的划分实现；如果要了

谁践踏了优雅/ 2021年06月24日 13:58/ 0 赞/ 961 阅读

相关在元素的装载数量明确的时候HashMap的大小应该如何选择。

今天看到美团招聘给出了一道小题目，关于HashMap的性能问题。问题如下： java hashmap，如果确定只装载100个元素，new HashMap(?)多少是最佳的，w

本是古典何须时尚/ 2021年06月22日 15:36/ 0 赞/ 219 阅读