HashMap扩容为什么每次都是之前的2倍

一. 背景介绍

HashMap的底层是通过数组+链表+红黑树的数据结构来存放数据的。我们知道,当新添加元素的key值出现了hash碰撞,就会在同一个bucket中形成链表或者红黑树。当键值对的数量超过阈值时就会扩容,将以前处于同一个链表或者红黑树上的元素打散,在新数组的 bucket 上进行重新分布。

当HashMap在初始化没有指定容量的情况下,首次添加元素时,数组的容量为16;当超出阈值,数组容量为扩容为之前的2倍。

那么问题来了,为什么HashMap会将首次初始化容量设置为16,而后续每次扩容都是之前的2倍?而不是像ArrayList首次为10,后续为1.5倍呢?这可是我们在面试时的一个高频考点哦!

二. 问题解答

2.1 对应源码分析

其实要想回答出上面提出的问题,我们可以从HashMap的源码里找到答案,如下图所示:

其中 n 为数组的长度,n - 1 为数组的最大索引值。(n - 1)& hash 的意思是将每个元素key的hash值,与最大索引值进行相与操作。然后判断对应的 bucket 位置是否有元素,如果没有元素则在对应的 bucket 位置直接添加;如果有元素,则形成链表或者红黑树

2.2 深入分析

各位看官,你现在可能对上面的内容还是有点云里雾里,别急,让我们再来看一组数据:

长度最大索引二进制数

当数组初始长度为16的时候,每次扩容都为之前的2倍,那么就保证了每次扩容之后新数组的最大索引值对应的二进制数为全1。根据2.1小节中,图片标识的(n-1)&hash,那么就能保证添加到HashMap中key的hash值与最大索引相与时,能够最大化的分散到HashMap所有的 bucket 中,进而最大化避免出现 hash碰撞而形成链表或者红黑树。

我们再反向地跟各位看官论证一下。假如说 HashMap的初始化长度是10,那么最大索引值为9,而9对应的二进制数是 1001。那么key的hash值与 9相与,结果只可能为 0、1、8、9,那么新增的数据永远只能放到数组索引为 0、1、8、9这四个位置,这就大大增加了出现链表和红黑树转换的概率。

所以初始化为16,每次扩容是之前的2倍,这就大大降低了链表和红黑树转换的概率,自然也就提高了HashMap的性能。


举例说明:

向集合中添加元素时,会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置,其中n是集合的容量,hash是添加的元素进过hash函数计算出来的hash值。

HashMap的容量为什么是2的n次幂,和这个(n - 1) & hash的计算方法有着千丝万缕的关系,符号&是按位与的计算,这是位运算,计算机能直接运算,特别高效,按位与&的计算方法是,只有当对应位置的数据都为1时,运算结果也为1,当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的,这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,减少hash碰撞,下面举例进行说明。

当HashMap的容量是16时,它的二进制是10000,(n-1)的二进制是01111,与hash值得计算结果如下

上面四种情况我们可以看出,不同的hash值,和(n-1)进行位运算后,能够得出不同的值,使得添加的元素能够均匀分布在集合中不同的位置上,避免hash碰撞。

下面就来看一下HashMap的容量不是2的n次幂的情况,当容量为10时,二进制为01010,(n-1)的二进制是01001,向里面添加同样的元素,结果为:

可以看出,有三个不同的元素与不同的hashCode经过&运算得出了同样的结果(index),严重的hash碰撞了。

终上所述,HashMap计算添加元素的位置时,使用的位运算,这是特别高效的运算;另外,HashMap的初始容量是2的n次幂,扩容也是2倍的形式进行扩容,是因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1094.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

持续集成 在 Linux 上搭建 Jenkins,自动构建接口测试

本篇把从 0 开始搭建 Jenkins 的过程分享给大家,希望对小伙伴们有所帮助。 文章目录 在 Linux 上安装 Jenkins在 Linux 上安装 Git在 Linux 上安装 Python在 Linux 上安装 Allure配置 Jenkinsjenkins 赋能 - 使用邮箱发送测试报告jenkins 赋能 - 优化测试报告内容…

C语言刷题(6)(猜名次)——“C”

各位CSDN的uu们你们好呀,今天,小雅兰还是在复习噢,今天来给大家介绍一个有意思的题目 题目名称: 猜名次 题目内容: 5位运动员参加了10米台跳水比赛,有人让他们预测比赛结果: A选…

测试管理之路 —— 如何优化测试计划以提高测试覆盖率

😏作者简介:博主是一位测试管理者,同时也是一名对外企业兼职讲师。 📡主页地址:🌎【Austin_zhai】🌏 🙆目的与景愿:旨在于能帮助更多的测试行业人员提升软硬技能&#xf…

Github的使用

Github Date: March 8, 2023 Sum: Github的使用 Github 了解开源相关的概念 1. 什么是开源 2. 什么是开源许可协议 开源并不意味着完全没有限制,为了限制使用者的使用范围和保护作者的权利,每个开源项目都应该遵守开源许可协议( Open Sou…

node多版本控制

前言 最近在折腾Python,并将node升级至v18.14.2。突然发现一个旧项目无法运行,也无法打包,里面的node-sass报错,显然这是因为node版本过高导致的。 将node版本降低至以前的v14.16.0,果然立马就能正常运行。 存在不同…

mysql-日志备份

1.binlog 用于数据恢复, 用于数据复制。 mysql> show variables like %log_bin%; -------------------------------------------------------------- | Variable_name | Value | ----------------------------------…

前端代码复用学习笔记:整洁架构与清晰架构

基础代码的复用往往比较简单,但是业务代码的复用通常是困难的,如果没有特殊的手段去治理项目会逐渐发展为难以维护的巨石应用,按照维基百科记载,代码的复用形式主要有三种,程序库,应用框架,设计…

【无标题】 6UVPX 总线架构的高性能实时信号处理

VPX630 是一款基于 6U VPX 总线架构的高速信号处理平台,该平台采用一片 Xilinx 的 Kintex UltraScale 系列 FPGA(XCKU115)作为主处理器,完成复杂的数据采集、回放以及实时信号处理算法。 采用一片带有 ARM内核的高性能嵌入式处理…

GeoServer发布一张纯图片作为地图教程

从事GIS行业的小伙伴们可能会有这样的需求,就是客户给了一张纯图片。可能是一张手工绘图,也可能是一张影像图片,总归来说就是png,jpeg格式的纯图片,现在需要把这张图片加载到我们的地图上,该如何做呢?本文带你从0开始操作一遍。 首先我先准备好测试数据,是一张jpg格式…

LeetCode刷题——贪心法(C/C++)

这里写目录标题[中等]买卖股票的最佳时机 II[中等]移掉k位数字[中等]跳跃游戏[中等]跳跃游戏 II[中等]加油站[中等]划分字母区间[中等]无重叠区间[中等]用最少数量的箭引爆气球[中等]买卖股票的最佳时机 II 原题链接题解 最简单的思路,效率不高,只要明天…

基于 pytorch 的手写 transformer + tokenizer

先放出 transformer 的整体结构图,以便复习,接下来就一个模块一个模块的实现它。 1. Embedding Embedding 部分主要由两部分组成,即 Input Embedding 和 Positional Encoding,位置编码记录了每一个词出现的位置。通过加入位置编码可以提高模型的准确率,因为同一个词出现在…

Web3中文|政策影响下的新加坡Web3步伐喜忧参半

如果说“亚洲四小龙”是新加坡曾经的荣耀,那么当时代进入21世纪的第二个十年,用新加坡经济协会(SEE)副主席、新加坡新跃社科大学教授李国权的话来说,新加坡现在的“荣耀”是全球金融的主要“节点”或区块链行业发展的关…

单片机能运行操作系统吗?

先直接上答案:可以!但是操作系统不是刚需,上操作系统比较占用单片机的资源,比如占用比较多的FLASH和RAM,间接增加了硬件成本,哪怕成本增加1毛钱,对于上量的产品,分分钟是一个工程师的…

【ChatGPT】论文阅读神器 SciSpace 注册与测试

【ChatGPT】论文阅读神器 SciSpace 注册与测试1. 【SciSpace】网址与用户注册1.1 官网地址:[【SciSpace官网】https://typeset.io](https://typeset.io)1.2 官网注册2. 【SciSpace】实战解说2.1 导入论文2.2 论文分析2.3 中文分析2.4 论文分析进阶2.5 公式表格分析3…

没有关系的话,那就去建立关系吧

今天给大家分享一道链表的好题--链表的深度拷贝,学会这道题,你的链表就可以达到优秀的水平了。力扣 先来理解一下题目意思,即建立一个新的单向链表,里面每个结点的值与对应的原链表相同,并且random指针也要指向新链表中…

Maven聚合开发【实例详解---5555字】

目录 一、Maven聚合开发_继承关系 二、Maven聚合案例 1. 搭建dao模块 2. 搭建service模块 3. 搭建web模块 4. 运行项目 一、Maven聚合开发_继承关系 Maven中的继承是针对于父工程和子工程。父工程定义的依赖和插件子工程可以直接使用。注意父工程类型一定为POM类型工程…

vue的diff算法?

文章目录是什么比较方式原理分析Diff算法的步骤:首尾指针法比对顺序:是什么 diff 算法是一种通过同层的树节点进行比较的高效算法 其有两个特点: 比较只会在同层级进行, 不会跨层级比较 在diff比较的过程中,循环从两边向中间比较…

2023年网络安全趋势

数据安全越来越重要。 我国《数据安全法》提出“建立健全数据安全治理体系”,各地区部门均在探索和简历数据分类分级、重要数据识别与重点保护制度。 数据安全治理不仅是一系列技术应用或产品,更是包括组织构建、规范制定、技术支撑等要素共同完成数据…

【FPGA-Spirit_V2】小精灵V2开发板初使用

🎉欢迎来到FPGA专栏~小精灵V2开发板初使用 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒🍹 ✨博客主页:小夏与酒的博客 🎈该系列文章专栏:FPGA学习之旅 文章作者技术和水平有限,如果文中出现错误,希望大家…

Kaggle实战入门:泰坦尼克号生生还预测

Kaggle实战入门:泰坦尼克号生生还预测1. 加载数据2. 特征工程3. 模型训练4. 模型部署泰坦尼克号(Titanic),又称铁达尼号,是当时世界上体积最庞大、内部设施最豪华的客运轮船,有“永不沉没”的美誉&#xff…
最新文章