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

Java 前端之家
前端之家收集整理的这篇文章主要介绍了Hashmap为什么容量是2的幂次，什么是负载因子，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

转自：

<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';">

，原文地址：，转载请注明。        HashMap可以说是中最常用的集合类框架之一，是Java语言中非常典型的，我们总会在不经意间用到它，很大程度上方便了我们日常开发。在很多Java的笔试题中也会被问到，最常见的，“HashMap和HashTable有什么区别？”，这也不是三言两语能说清楚的，这种笔试题就是考察你来笔试之前有没有复习功课，随便来个快餐式的复习就能给出简单的答案。        HashMap计划写两篇文章，一篇是HashMap工作原理，也就是本文，另一篇是多线程下的HashMap会引发的问题。这一年文章写的有点少，工作上很忙，自己业余时间也做点东西，就把博客的时间占用了，以前是力保一周一篇文章，有点给自己任务的意思，搞的自己很累，文章质量也不高，有时候写技术文章也是需要灵感的，为了举一个例子可能要绞尽脑汁，为了一段代码可能要验证好多次，现在想通了，有灵感再写，需要一定的积累，才能把自己了解的知识点总结归纳成文章。        言归正传，了解HashMap之前，我们需要知道Object类的两个方法hashCode和equals，我们先来看一下这两个方法的默认实现：

 
在CODE上查看代码片

派生到我的代码片
    调用底层其它语言实现 */
方法我们太熟悉了，我们经常用于字符串比较，String类中重写了equals方法，比较的是字符串值，看一下源码实现：

    • 调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。 
    方法实现对象上差别可能性最大的相等关系；即，对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象时，此方法才返回 true（x == y 具有值 true）。 当此方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
    方法，这个方法我们平时通常是用不到的，它是为哈希家族的集合类框架(HashMap、HashSet、HashTable)提供服务，hashCode 的常规协定是：
    调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。 
  • 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 
  • 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
    •        当我们看到实现这两个方法有这么多要求时，立刻凌乱了，幸好有IDE来帮助我们，Eclipse中可以通过快捷键alt+shift+s调出快捷菜单，选择Generate hashCode() and equals()，根据业务需求，勾选需要生成的属性，确定之后，这两个方法就生成好了，我们通常需要在JavaBean对象中重写这两个方法。
    方法介绍完之后，我们回到HashMap。HashMap是最常用的集合类框架之一，它实现了Map接口，所以存储的元素也是键值对映射的结构，并允许使用null值和null键，其内元素是无序的，如果要保证有序，可以使用LinkedHashMap。HashMap是线程不安全的，下篇文章会讨论。HashMap的类结构如下：
    也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在 ，则存放新的键值对到位置。文字描述有些乱，通过下面的流程图来梳理一下整个put过程。

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

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

    第二篇：

    比较深入的分析了HashMap在put元素时的整体过程，中实际操作的都是数组或者链表，而我们通常不需要显示的维护集合的大小，而是集合类框架中内部维护，方便的同时，也带来了性能的问题。        HashMap有两个参数影响其性能：和。默认初始容量是16，加载因子是0.75。容量是哈希表中桶(Entry数组)的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。        HashMap中定义的成员变量如下：

     
    在CODE上查看代码片

     
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  • [] table;
  •  
  •  
  •  
  • =threshold就会扩容
  •  
  •  
    • ()           构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。(int initialCapacity)           构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。(int initialCapacity,float loadFactor)           构造一个带指定初始容量和加载因子的空 HashMap。(,? extends> 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也应是如此。



    文章

  •

    猜你在找的Java相关文章

    ArrayList源码分析
    ArrayList简介：ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的...
    java多线程与并发（基础篇）
    一、进程与线程 进程：是代码在数据集合上的一次运行活动，是系统进行资源分配和调度的基本...
    LinkedList 的实现原理
    本文为博客园作者所写：&#160;一寸HUI，个人博客地址：https://www.cnblogs.com/zsql/...
    java之面向对象详解
    #############java面向对象详解#############1、面向对象基本概念2、类与对象3、类和对象的...
    java之异常详解
    一、什么是异常? 异常就是有异于常态，和正常情况不一样，有错误出错。在java中，阻止当前...
    Map的四种遍历
    //Map的四种遍历方法 //Map不能直接遍历 ，只能通过遍历Key与Value间接遍历 public static...
    throw和throws的区别以及try,catch,finally在有return的情况下执行的顺序
    一，抛出异常有三种形式，一是throw,一个throws，还有一种系统自动抛异常。下面它们之间的...
    Jdk14 都要出了，Jdk9 的新特性还不了解一下？
    中最大的亮点是 Java 平台模块化 的引入，以及模块化 JDK。但是 还有很多其他新功能，这篇...
    还看不懂同事代码？快来补一波 Java 7 语法特性
    Jdk 频繁更新，新特性了解吗？每次更新都注重提高生产效率，提高 JVM 性能，推行模块化等，...
    Java 12 新特性介绍，快来补一补
    Java 12 早在 2019 年 3 月 19 日发布，这些新特性你知道吗
    PHPJavaJava SEPythonC#C&C++RubyVBasp.NetGoPerlnettyDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole
    文件时间pythonm相等性PHP Warning时间问题问题解决pcntl_signal采样点wav模块动态文本调用频率限制对外暴露多个访问请求更新数据表模型结构type()方法比较速度手写体sobel算子保存模型Image类nn.Conv2dpytorch1.0kaggleDCGAN交并比range()用法打印模型反卷积卷积