首页 > 其他分享 >HashMap的长度是2的幂次方

HashMap的长度是2的幂次方

时间:2023-11-02 17:01:23浏览次数:53  
标签:HashMap length 数组 取余 次方 长度

为了能让HashMap存取高效,尽量减少碰撞,也就是要尽量把数据分配均匀。Hash值的范围值-2147483648到2147483647,前后加起来大概40亿的映射长度,只要哈希函数映射的比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数据的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“(n-1)&hash”。(n代表数组长度)。这也就解释了HashMap的长度为什么是2的幂次方。

这个算法应该如何设计呢?

采用%取余的操作来实现。但是,重点来了,取余%操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说hash%length==hash&(length-1)的前提是length是2的n次方),并且采用二进制位操作&,相当于%能够提高运算效率,这就解释了HashMap的长度为什么是2的幂次方。


标签:HashMap,length,数组,取余,次方,长度
From: https://blog.51cto.com/u_11315052/8153671

相关文章

  • 算法刷题记录-长度最小的子数组
    算法刷题记录-长度最小的子数组长度最小的子数组给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的连续子数组[numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。示例1:输......
  • 一元二次方程求根公式推导和运用
    一元二次方程:只有一个未知数,且未知数的最高次数为2一元二次方程的一般形式:<svgxmlns="http://www.w3.org/2000/svg"width="2.207ex"height="2.025ex"viewBox="0-883.9975.6894.9"xmlns:xlink="http://www.w3.org/1999/xlink"aria-hidden=&qu......
  • 请求筛选模块被配置为拒绝超过请求内容长度的请求。
    转自:https://blog.csdn.net/cplvfx/article/details/126608987一、打开站点根目录的“web.config ”二、找到“system.webServer”节点三、在“security”节点增加“requestFiltering”节点配置1<system.webServer>2<security>3<req......
  • 面试高频题:你如何知道HashMap正在进行扩容操作?
    亲爱的小伙伴们,大家好!我是小米,一个热爱技术分享的小编。今天,我们将一起来探讨一个程序员们在日常工作中常常遇到的问题——如何知道HashMap正在扩容。HashMap,作为Java中最常用的数据结构之一,经常在我们的代码中扮演着关键的角色。了解HashMap的工作原理,特别是它的扩容机制,可以帮助......
  • 如何用Java实现一个线程安全的HashMap?
    有以下几种方式可以实现线程安全的HashMap:使用ConcurrentHashMap类实现:ConcurrentHashMap是Java集合框架中的一个类,它是线程安全的HashMap实现。ConcurrentHashMap的实现方式是将一个大的Map拆分成多个小的Map片段,每个Map片段上都有自己的锁,这样多个线程在访问不同的Map片段时就可......
  • 无重复字符的最长子串(给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长
    importjava.util.*;publicclassSolution{/***代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可***@paramarrint整型一维数组thearray*@returnint整型*/publicintmaxLength(int[]arr){......
  • HashMap集合遍历随机性问题分析
    一、原因分析1.1HashMap对象的遍历HashMap的遍历是通过此类中字段table数组进行顺序遍历,原因如下所示:1#HashMap迭代遍历源码2publicfinalbooleanhasNext(){3returnnext!=null;4}56finalNode<K,V>nextNode(){7Node<K,V>[]t;......
  • 用HashMap创建jString,ArrayList的键值对用entrySet遍历
    用HashMap创建jString,ArrayList的键值对用entrySet遍历package随机点名器;importjava.util.*;publicclassTest1{publicstaticvoidmain(String[]args){HashMap<String,ArrayList<String>>m=newHashMap<>();ArrayList<String>......
  • day 2 数组 977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵 Ⅱ
    977.有序数组的平方题目链接:977.有序数组的平方视频教程文章教程思路最直观的解法:暴力解题,每个数先平方,然后再快速排序,时间复杂度为O(n+nlogn)规律:该数组本身是非递减顺序,在平方后其实依然有顺序,左右两边大中间小。双指针利用观察到的规律,可以利用双指针在数......
  • 数据库系列:前缀索引和索引长度的取舍
    数据库系列:MySQL慢查询分析和性能优化数据库系列:MySQL索引优化总结(综合版)数据库系列:高并发下的数据字段变更数据库系列:覆盖索引和规避回表数据库系列:数据库高可用及无损扩容数据库系列:使用高区分度索引列提升性能1背景有时候我们需要在字符类型的字段上建设索引,但是如果......