精华内容
下载资源
问答
  • Hashmap的取余,(数组长度 - 1) & hash = hash % 数组的长度?
    2022-01-24 19:12:40

    前言

    最近在回顾HashMap的时候,发现自己之前没有注意到的一点,是关于计算出hash值后,把这个key放在那个数组索引中。源码中是 (数组长度 - 1) & hash,这个操作等同于 hash % 数组的长度。


    一、(数组长度 - 1) & hash,这个操作等同于 hash % 数组的长度?

    源码位置在putVal方法的第629行:(n - 1) & hash
    即为:(数组的长度 - 1) & hash(计算出的hash值)
    根据传参可知道:hash为int类型的整数。

    假设:数组长度:16 - 1 = 15,hash:57
    二进制:1111、111001
    在这里插入图片描述
    那现在进行取余运算:57 % 16 = 9
    即为 (length -1)& hash = length % hash
    那么为啥呢?

    二进制逢2进1,一个数右移一位 = 这个数 / 2^1。右移n位 = / 2^n。那么正好,数组的长度是2的倍数,也就是说,一个数取余 = 右移^次,移出的数字就是商。换成10进制就是:

    123 % 10 = 3 相当于 123 右移一位,余3
    123 % 100 = 23 相当于 123 右移两位,余23

    即为:一个n进制的数字 % n进制的y倍数 = 这个数右移y位,y位即为余数。换成 8进制就是:

    【10进制】156 % 8 = 4
        对应
    【8进制】 234 % 10 = 右移一位 = 4


    【10进制】156 % 16 = 28
        对应
    【8进制】 234 % 20 = 右移两位 = 34 = 对应10进制 = 28

    那么现在已经知道取余即为取出(2^n)n个末尾的数,咋直接拿到末尾的数呢,例如二进制的特性 ,2^n - 1 = 最大的余数,利用 & 运算,1 & 1才能 = 1,其他全都为 0,一个数 & 全是 1111…(n个1)的数字,正好拿出这个数 对 2^n的余数。

    总结

    以上结论全是个人已正整数猜想的,如有错误,请及时留言

    更多相关内容
  • hashMap数组长度为什么要求是2的整数次幂 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得...

    hashMap的数组长度为什么要求是2的整数次幂

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。(n代表数组长度)。
    这个算法应该如何设计呢?
    我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采
    用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。
    下面这张图很好的解释了找到对应数组下标的过程。
    拿16举例,16-1=15,15的二进制为1111,15&hash的得到哈希值的低四位,这个第四位刚好对应着16长度的0-15下标,而且实现了散列。

    在这里插入图片描述

    hashMap的加载因子为什么是0.75

    加载因子*数组长度就是hashMap扩容的阈值。例如hashMap默认数组长度为16,当put值时,如果当前数组位置补位空且已占用的数组长度达到12,那么hashMap就会进行扩容。
    如果加载因子为1,即当数组所有位置都有元素时进行扩容,这样虽然减少了空间开销,提高了空间利用率,但是哈希冲突肯定会变多,势必造成链表的堆积,增加查询时间。
    如果加载因子为0.5,虽然可以减少查询时间成本,但是空间利用率很低,同时提高了扩容次数,增加了性能开销。
    所以0.75这个值是对空间利用率和时间利用率的折中。

    hashMap为什么当链表长度为8时转为红黑树

    在这里插入图片描述

    这是hashMap源码中的一段注释,从这段注释中我们可以得到想要的答案。

         *Ignoring variance, the expected
         * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
         * factorial(k))
    

    这段源码意思是:忽略方差,列表大小k的预期出现次数 列表大小k的预期出现次数 遵循(exp(-0.5) * pow(0.5, k) / * factorial(k))。而这个就是泊松分布。
    在这里插入图片描述

    泊松分布中λ的值注释中也给出。

     Ideally, under random hashCodes, the frequency of
         * nodes in bins follows a Poisson distribution
         * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
         * parameter of about 0.5 on average for the default resizing
         * threshold of 0.75, although with a large variance because of
         * resizing granularity
    
    

    在理想的随机hashCodes下,容器中节点的频率遵循泊松分布,对于0.75的默认调整阈值,泊松分布的概率质量函数中参数λ(事件发生的平均次数)的值约为0.5,尽管λ的值会因为load factor值的调整而产生较大变化。

    在按照泊松分布公式来看,链表达到长度为8的概率为0.00000006,概率非常的小,那hashMap为什么要选取概率最小的时候将链表转换为红黑树。

    Because TreeNodes are about twice the size of regular nodes, we
         * use them only when bins contain enough nodes to warrant use
         * (see TREEIFY_THRESHOLD)
    

    注释也解释了,TreeNode虽然改善了链表增删改查的性能,但是其节点大小是链表节点的两倍。
    虽然引入TreeNode但是不会轻易转变为TreeNode(如果存在大量转换那么资源代价比较大),根据泊松分布来看当k=8,转变是小概率事件,性价比是值得的。

    展开全文
  • jdk1.8中的hashmap作了很多改进:红黑树的引入,链表尾插,以及底层数组长度保持2的次幂。本文专注于分析2次幂设定的原因,且听我慢慢道来…… 与“取余”等价的算法 众所周知,hashmap是数组链表结构:hash算法用于...

    jdk1.8中的hashmap作了很多改进:红黑树的引入,链表尾插,以及底层数组长度保持2的次幂。本文专注于分析2次幂设定的原因,且听我慢慢道来……

    与“取余”等价的算法

    众所周知,hashmap是数组链表结构:hash算法用于将key散列,经计算分散到数组槽中;而两个key算出了同样的值,即产生hash冲突时,就需要将槽中的单个节点升级成链表。由于get时需要对链表其进行遍历,链表越长检索效率越差。那么,计算出的key值落点越平均,hash冲突的可能性越小

    key值落点的计算方式为,key的hash值数组长度取余操作,记作key.hascode % array.length。从数学角度考虑,保持array.length为质数会使得计算结果更均衡,hashTable就是这么做的(数组初始值11)。但 hashmap 中 array.length 偏偏选择了2的次幂,是个合数……何故?完全出于性能考虑!
    先给出结论——当 array.ength长度是2的次幂时,key.hashcode % array.length等于key.hashcode & (array.length - 1)。下面重点看下这个结论是怎么得出来的。

    举个例子:
    假如 array.length = 2^4 = 16,二进制10000。这个数减去1的结果是1111,也就是array.length -1 = 1111。
    (下面这段中的数字都是二进制)
    再假设一个key的值为10011011001(很随意写的一个数),与1111做 & 操作,得到的结果是1001(高位部分1001101都舍去了)。而1001必然是一个小于10000的数,对于一个小于10000的数而言,1001 % 10000得到的就是1001自己。
    那么刚刚舍弃的高位部分1001101 0000(后面补上了四个0000)就一定能被10000整除吗?答案是肯定的:因为10011010000可以拆成10000000000+10000000+1000000+10000,这几个数都能通过10000的n次左移得到,也就相当于这几个数都能被10000整除。那他们的和,也就是10011010000,一定也可以被10000整除。
    因此,最终结论就是:10011011001 & ( 10000 - 1 ) = 10011011001 & 1111 = 1001 = 10011011001 % 10000

    放张简图再唠叨一遍以示总结,加深下印象:
    clipboard.png

    再强调一次:当 array.ength长度是2的次幂时,key.hashcode % array.length等于key.hashcode & (array.length - 1)

    好,如果你读懂了例子部分,相信你已经基本明白这个结论是站得住脚的(虽然不是纯数学型的讲解)。那么hashmap的作者Doug Lea大神,为什么如此执着于用&操作替换%操作呢?
    因为对于二进制生物计算机来说,& 的效率要高于 %!(与、或、非都可看作二进制基本操作,同或、异或次之,+ - * ÷ % 等都基于前面的)

    扩容时方便定位

    这还不算完,好处不止这一处。
    当hashmap需要扩容,重新计算链表元素的hashcode,以进行元素的重新定位时,依然能从“ 数组2次幂 ”的这个设定中借力!

    hashmap数组扩容时,新数组length = 原数组length * 2,沿用前面的例子(array.length = 2^4 = 16,二进制10000),array.length 乘以 2 ,即二进制左移一位,由 10000 变成 100000。此时需要重新计算数组槽中的元素位置,如果槽中是链表,链表中每个元素都需要重新计算位置(这里不考虑红黑树)。

    计算的公式不变,key.hashcode & (array.length - 1),由于数组的翻倍(10000->100000),导致 array.length - 1 发生了改变(1111->11111)。此时,扩容前原本被舍弃的高位部分的最后1位,也将参与计算。
    clipboard.png

    在扩容这个历史的拐点,这一位就显得很特别:如果这个位置是0,余数计算的结果将保持不变,意味着扩容后此元素还在这个槽中(槽编号没发生改变);如果这个位置是1,余数计算结果就变成了原槽索引 + 原array.length
    也就是说,hashmap扩容的元素迁移过程中,由于数组大小是2次幂的巧妙设定,使得只要检查 “ 特殊位 ” 就能确定该元素的最终定位。

    给出一个较完整的扩容示意图进行说明:
    clipboard.png

    • 扩容前

    红绿黄三个元素,由各自的hashcode取余后都淤积在数组槽13,组成链表形式

    • 扩容后

    红、绿二星所表示的元素的hashcode“ 特殊位 ”为0,取余依然定位在槽13;而黄星表示的元素,hashcode“ 特殊位 ”为1,取余后结果 = 原槽索引 + 原数组大小 = 13 + 16 = 29。(这个结果也和图中黄星的hashcode二进制低位值11101一致)

    总结

    对hashmap而言,数组长度始终保持2次幂有两点好处:

    1. 能利用 & 操作代替 % 操作,提升性能
    2. 数组扩容时,仅仅关注 “特殊位” 就可以重新定位元素

    性能,性能,还是性能……

    展开全文
  • 不指定的话默认初始容量是16,如果传入一个值用来指定初始容量,并不是直接使用这个值来定义数组长度,而是用大于等于这个值的最小2的幂次方来作为初始容量,之所以要采用2的幂次方来作为HashMap底层数组的长度,...

    HashMap的底层是由数组加链表及红黑树实现的,其中链表是为了解决哈希冲突而引入的,并且在JDK1.8之后,引入了红黑树结构,在链表长度大于一定的阈值之后,采用红黑树的结构代替链表结构,加快搜索速度,其结构如下图所示。
    在这里插入图片描述
    并且我们知道,HashMap是可以指定初始容量的,不指定的话默认初始容量是16,如果传入一个值用来指定初始容量,并不是直接使用这个值来定义数组长度,而是用大于等于这个值的最小2的幂次方来作为初始容量,之所以要采用2的幂次方来作为HashMap底层数组的长度,是因为在对数据的key值进行哈希函数运算得到的哈希值范围很大,无法直接作为数据存放位置的数组下标,因此需要对得到的哈希值作进一步处理,一般来说是对数组长度进行取模运算,在数组长度为2的幂次方的时候,用哈希值与数组长度-1的值做逻辑与运算就相当于对数组长度取余,逻辑与运算因为运算符优先级的关系会比直接的取余运算效率更高,这就是HashMap底层数组长度一般为2的幂次方的原因。
    多提一句,在HashMap的源码中,采用的是tablesSizeFor函数来获取大于等于指定初始容量值的最小2的幂次方的,源码如下:
    在这里插入图片描述
    本质上就是通过移位来获取的,感兴趣的可以花时间了解一下具体过程。

    展开全文
  • 我有一个<...我愿意使用java流操作获取具有最大大小的Set.这是我的例子:public class Example {public static void main( String[] args ) {Map> adj = new HashMap<>();Set set1 = Stream.o...
  • Java HashMap计算初始数组大小过程

    千次阅读 2020-06-29 17:24:01
    HashMap实际上是数组加链表的数据结构。在JDK1.8后又引入了红黑树。今天抽空研究了一下HashMap的源码,感觉还是非常值得学习的,它里面的一些算法思想真是让人佩服。本文就来结合源码学习一下HashMap是如何计算数组...
  • 如何在Java中获取json数组长度

    千次阅读 2021-03-22 17:08:32
    我正在处理一个需求,其中我需要获取json以下的长度,而我需要获取整个json中的filters对象的长度附加json以供参考。{"employeeId": "41825","userId": "tawright","sourceSystem": "Visibility","loginId": ...
  • HashMap

    2020-09-04 00:46:06
    HashMapHashMap1. 特点2.存储过程3.HashMap集合类的成员4.扩容5.遍历HashMap HashMap 1. 特点 存取无序 ...(比如当hashmap满足数组长度大于64,有部分key的链表小于8,那么它也是采用的链表的形式,
  • HashMap数组下标计算

    千次阅读 2020-08-21 13:58:01
    HashMap之原理初始化loadFactorcapacitythreshold数组下标计算 前提: HashMap是有数组+链表组成的,其中使用的算法有:hash(java8...capacity并非HashMap的属性,指的是HashMap数组的大小,即table.length threshold
  • 为什么HashMap长度一定是2的次幂?

    千次阅读 多人点赞 2021-04-30 09:48:04
    HashMap是面试过程中最常问的知识点之一 今天用最通俗易懂的大白话来讲一讲:为什么HashMap的长度一定是2的次幂?...最后得出一个数,如果数组长度是15的话,这个数是一个0-15之间的一个数,这个数就是得出的数组
  • java如何增加数组长度

    千次阅读 2021-02-12 21:39:49
    遇到一个面试题:在不使用list的add方法的情况下,动态的添加元素(大概是这个样子);...我首先想到的就是数组,但java中的数组是定长的,无法动态增加长度。如果要扩充数组,那就只能通过重新定义数...
  • Hashmap是基于数组和链表(高级版本采用红黑树)组合使用实现的,通过key查找value第一步是通过key的hashcode和2的数组长度-1的幂做与操作。来获取到数组的位置。 源码如下: for (HashMapEntry<K, V> e = ...
  • hashmap如何得到数组下标

    千次阅读 2020-08-30 17:32:45
    1、如何得到数组的下标 > hash 此方法用计算元素的hash值的。简单分析: 如果 key是一个空, 此时他的 hash 为 0 如果不是空值 拿到它的 hashCode 赋给 H 并且 与自身的高16位相与计算 static final int ...
  • HashMap如何定位桶数组的位置
  • import java.util.*; public class Main{ ... //记录数组中每个数字出现的次数 Scanner in=new Scanner(System.in); int[] nums = new int[1005]; HashMap<Integer,Integer> map=new HashMap<Integer, In
  • 关于HashMap基本的大家都知道,但是为什么数组长度必须是2的指数次幂,为什么HashMap的加载因子要设置为0.75,为什么链表长度大于等于8时转成了红黑树? HashMap添加元素分析 当添加元素时,会通过哈希值和数组...
  • HashMap的扩容机制---resize()HashMap底层逻辑当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放...
  • JDK1.8 HashMap的默认长度与扩容分析

    千次阅读 2020-04-23 18:09:01
    HashMap在jdk1.8的时候使用的是数组+链表+红黑树的结构,也叫哈希桶,在jdk1.8之前是用没有红黑树的概念。接下来我们来看看HashMap为什么要用到链表,而jdk1.8开始要使用红黑树,和HashMap是怎样进行扩容的。 1、...
  • 前言在对问题采取hash数组的方法解决的时候,我们往往需要获取问题共性的数组长度,比如说26个字母为26长度,那么如果这个关键词(26个字母中的任意一个)不固定长度(26)呢?我们可以采取集合的方式——不固定长度的...
  • HashMap基本介绍

    2021-01-27 14:56:44
    1.HashMap简介(本文是按照JDK1.8进行解析)HashMap位于JDK自带jar包rt.jar的java.util目录下。 HashMap是一个散列表,存储的内容是键值对映射。HashMap继承于AbstractMap,实现了Map、Cloneable、Serializable接口 ...
  • HashMap如何计算数组下标

    千次阅读 2020-06-19 19:51:07
    HashMap如何计算数组下标 首先我们看看String的hashCode是如何计算的(出自JDK1.8.0 211 java.lang.String 1452行—1476行) /** * Returns a hash code for this string. The hash code for a * {@code String} ...
  • 自定义HashMap

    2018-04-27 15:06:56
    1.使用LinkedList实现HashMap LinkList是链表数组实现的,这里为了方便直接使用的基于LinkedList的双向链表数组2.自定义HashMap的功能函数1)添加元素public void put(Key key,Value value)2)根据键获取值public ...
  • hashmap扩容时怎么保证get(key,value) 中 hashcode与数组长度取模与之前一致
  • 剑指offerJZ28:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。...
  • HashMap深入分析

    2021-04-17 08:12:23
    如果说String是我们用得最多的数据类型,那么HashMap绝对算得上是用得最多的数据结构了。...HashMap的底层核心数据结构HashMap底层核心数据结构是数组数组里的数据类型是HashMap.Node,既然是数组那么就有...
  • HashMap扩容机制】

    2021-11-28 20:57:42
    HashMap数组长度恒定为2的n次方,也就是说只会为16,32,64,128这种数。即便你给的初始值是13,最后数组长度也会变成16,它会取与你传入的数最近的一个2的n次方的数。 扩容之后元素的位置是否改变,完全取决于...
  • 数组、链表、hashmap

    2020-08-24 23:45:15
    数组 数组存储数据的方式是在内存中开辟一块连续的...而且因为真实物理地址的连续性,数组一旦初始化完成,其长度就是固定的,所以当数组中元素的存储密度较小时,即数组比较空时,数组对空间的利用率较低。且数组
  • HashMap面试题一

    2021-03-22 10:06:42
    HashMap面试题汇总 hashmap - JDK7 JDK8 数据结构 数组+链表 数组+链表/红黑树 链表插入 头插法 尾插法 key==null table[0] - Iterator去删除元素 modCount 实现 fail-fast - resize 头插法,链表...
  • HashMap常见面试题解析

    2021-01-14 14:10:07
    通过获取key对象的hashcode计算出该对象的哈希值,通过改哈希值与数组长度减去1进行位与运算(n-1 & hash),得到buckets 的位置,当发生hash冲突时,如果value值一样,则会替换旧的key的value,value不一样则新建...
  • 在新建一个HashMap时,会初始化一个数组,在JDK1.8之前初始化的数组初始容量为16,但在JDK1.8及之后,它实现了一个懒加载功能,就是在第一次put数据时才会初始化容量,初始容量仍然是16,在添加数据时,添加数据的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 74,611
精华内容 29,844
关键字:

获取hashmap的数组长度