加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 编程开发 > Java > 正文

Hashmap为什么容量是2的幂次，什么是负载因子

发布时间：2020-12-14 06:38:12 所属栏目：Java 来源：网络整理
导读：转自： p style="font-size:15px;color:rgb(102,102,102);line-height:26px;font-family:'Microsoft YaHei';" 本人在准备求职面试的时候，面经里经常会有这样的一个面试题：“Hashmap为什么容量是2的幂次，什么是负载因子？” p style="font-size:15px;color

转自：

<p style="font-size:15px;color:rgb(102,102,102);line-height:26px;font-family:'Microsoft YaHei';">
本人在准备求职面试的时候，面经里经常会有这样的一个面试题：“Hashmap为什么容量是2的幂次，什么是负载因子？”


<p style="font-size:15px;color:rgb(102,102);line-height:26px;font-family:'Microsoft YaHei';">
在最初的时候，我也反复搜索，但是没有一篇博文能完整或清晰解答这个问题。


<p style="font-size:15px;color:rgb(102,102);line-height:26px;font-family:'Microsoft YaHei';">
在下此文为博采众长，总结了多篇文章对于这个问题的解答，希望对大家有所帮助。


<p style="font-size:15px;color:rgb(102,102);line-height:26px;font-family:'Microsoft YaHei';">

?

  • ? ? ? ?当我们看到实现这两个方法有这么多要求时，立刻凌乱了，幸好有IDE来帮助我们，Eclipse中可以通过快捷键alt+shift+s调出快捷菜单，选择Generate hashCode() and equals()，根据业务需求，勾选需要生成的属性，确定之后，这两个方法就生成好了，我们通常需要在JavaBean对象中重写这两个方法。
    • java.util? 类 HashMap 
      
      java.util.HashMap
    也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在 ，则存放新的键值对到位置。文字描述有些乱，通过下面的流程图来梳理一下整个put过程。

  • ? ? ? ?来鉴赏一下HashMap中put方法源码：
  • ?e?=?table[i];?e?!=?

    • ? ? ? ?到这里，我们了解了HashMap工作原理的一部分，那还有另一部分，如，加载因子及rehash，HashMap通常的使用规则，多线程并发时HashMap存在的问题等等，这些会留在下一章说明。

    第二篇：

    和。默认初始容量是16，加载因子是0.75。容量是哈希表中桶(Entry数组)的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。 ? ? ? ?HashMap中定义的成员变量如下：

    ?
  • ?
  • ?
  • ?
  • ?
  • ?
  • ?
  • ?
  • []?table;
  • ?
  • ?
  • ?
  • =threshold就会扩容
  • ?
  • ?
    • ??????????构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空?HashMap。 ??????????构造一个带指定初始容量和默认加载因子 (0.75) 的空?HashMap。 ??????????构造一个带指定初始容量和加载因子的空?HashMap。?m) ??????????构造一个映射关系与指定?Map?相同的?HashMap。
  • ?MAXIMUM_CAPACITY)??
  • =?initialCapacity
  • =?Holder.ALTERNATIVE_HASHING_THRESHOLD);??

    • 开发时，必须要严格控制入参，可以参考一下Java源码及各种开源项目源码，如果参数不合法，适时的抛出一些运行时异常，最后到应用层捕获。看第14-16行代码，这里做了一个移位运算，保证了初始容量一定为2的幂，假如你传的是5，那么最终的初始容量为8。源码中的位运算随处可见啊=。=! ? ? ? ?到现在为止，我们有一个很强烈的问题，为什么HashMap容量一定要为2的幂呢？HashMap中的数据结构是数组+单链表的组合，我们希望的是元素存放的更均匀，最理想的效果是，Entry数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较K，而且空间利用率最大。那如何计算才会分布最均匀呢？我们首先想到的就是%运算，哈希值%容量=bucketIndex，SUN的大师们是否也是如此做的呢？我们阅读一下这段源码：

    ?
    • 10000，15 -> 01111，那根据&位运算的规则，都为1(真)时，才为1，那0≤运算后的结果≤15，假设h <= 15，那么运算后的结果就是h本身，h >15，运算后的结果就是最后三位二进制做&运算后的值，最终，就是%运算后的余数，我想，这就是容量必须为2的幂的原因。HashTable中的实现对容量的大小没有规定，最终的bucketIndex是通过取余来运算的。减法>乘法>除法>取模(这里指的是正常的算法，不包括速算)，CPU也应是如此。





  • （编辑：李大同）

    【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

      • 相关内容
        推荐文章
          站长推荐
          热点阅读

            【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

            建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

            Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同