首页 > 其他分享 >HashMap的数组长度为何必须是2的n次方

HashMap的数组长度为何必须是2的n次方

时间:2023-04-30 09:13:39浏览次数:44  
标签:hash HashMap 链表 length 数组 次方 长度

  • 扩容方便,数字位移计算方便效率高;
  • 计算元素下标使用的方式是key的hash & (数组length - 1),由于length2^n,转换成二进制后2^-1最低位就全部都是1,比如111,就相当于是数组长度的掩码,那么hash & 111就可以将数组的每一位都覆盖,加入数组长度不是2^n,那么length-1低位不全是1,比如101,那么hash & 101就会出现数组有的位置永远都不会有值。
  • 扩容的时候一条链表最多映射到两条链表上,计算效率高
  • 2^n长度设计hash算法比较容易实现散列比较均匀

标签:hash,HashMap,链表,length,数组,次方,长度
From: https://www.cnblogs.com/dreamroute/p/17364891.html

相关文章

  • 2023-04-29:一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。 给你一个整数
    2023-04-29:一个序列的宽度定义为该序列中最大元素和最小元素的差值。给你一个整数数组nums,返回nums的所有非空子序列的宽度之和由于答案可能非常大,请返回对109+7取余后的结果。子序列定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数组......
  • 2023-04-29:一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。 给你一个整数
    2023-04-29:一个序列的宽度定义为该序列中最大元素和最小元素的差值。给你一个整数数组nums,返回nums的所有非空子序列的宽度之和由于答案可能非常大,请返回对109+7取余后的结果。子序列定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数......
  • 长度最小的子数组--Python解法
    给定一个含有 n 个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组 [numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。defminSubArrayLen(self,s:int,nums:List[int])->int:......
  • 树状数组 好题整理
    树状数组好题整理[SDOI2009]HH的项链离线询问后,按右端点升序排序,考虑建立一个树状数组,只包含0/1,把含每种颜色的点中最靠右的位置打上1的标记,询问\([l,r]\)答案即为\(query_r-query_{l-1}\),可以证明,如果一个相同颜色的点的位置对答案有贡献,那么最靠右的位置也一定能......
  • react的类组件和函数组件 -- 状态 state
    //函数组件是无状态的既没有数据的类似vue组件中的data数据//类组件是有状态的组件是有数据的是双向绑定的数据是数据驱动视图的负责UI的视图更新(单个组件的私有数据组件之间的数据是独立的)importReactDomfrom"react-dom"import{Component}from"react......
  • 数组模拟实现数据结构
    数组模拟链表实现①单链表:邻接表(存储图和树)②双链表:优化某些问题单链表inte[N]存储val,intne[N]存储next//单链表模板inthead,e[N],ne[N],idx;//head表示头节点的下标,e[i]表示节点i的值,ne[i]表示节点i的指针是多少,idx存储当前已经用到了哪个点v......
  • 力扣---1493. 删掉一个元素以后全为 1 的最长子数组
    给你一个二进制数组 nums ,你需要从中删掉一个元素。请你在删掉元素的结果数组中,返回最长的且只包含1的非空子数组的长度。如果不存在这样的子数组,请返回0。 提示1:输入:nums=[1,1,0,1]输出:3解释:删掉位置2的数后,[1,1,1]包含3个1。示例2:输入:nums=[0,1,1,1,0......
  • 第三章-栈 队列和数组
    栈stack数据接口三要素逻辑,运算,存储只允许在一端进行数据插入和删除操作.LIFO规则,lastinfirstout先进后出联想到烤串.doge卡特兰数(catalan),n个不同元素进栈,出栈元素不同排列的个数为顺序栈链栈只在头结点插入和删除就是链栈队列FIFOfirstinfirsto......
  • 数组和字符串
    数组操作读取数组中的元素,是通过访问索引的方式来读取的,一般从0位置开始。对于数组,计算机在内存中为其申请一段连续的空间,且会记下索引为0处的内存地址。主要的四种操作为:读取,查找,插入和删除元素。1.寻找数组的中心索引:给定整数数组nums,计算数组的中心下标(其左侧所有元素相......
  • 023 指针数组和数组指针
     /*一:原理二:指针数组三:数组指针*/ 一:原理定义变量:intnum=1;1组合:符号+名称(1)符号:数据类型(2)名称:要操作的数据类型(3)符号为名称所服务的。2优先:(1)默认优先级(2)离符号近(从......