HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或） 6. HashMap 为什么使用 & 与运算代替模运算？ 7....前言 HashMap 高度依赖的 hashcode 和 hash 算法，虽然在很多书里面，都说这是数学家应该去研究的事情，但我想，程序员也应该了解他是怎么实现的。为什么这么做？...所谓素数：质数又称素数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。...HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或） 好了，知道了 hashCode 的生成原理了，我们要看看今天的主角，hash 算法。...到这里，我们提了一个关键的问题： HashMap 的容量为什么建议是 2的幂次方？正好可以和上面的话题接上。 我们说，hash 算法的目的是为了让hash值均匀的分布在桶中（数组），那么，如何做到呢？
为什么右移 16 位，为什么要使用 ^ 位异或） HashMap 为什么使用 & 与运算代替模运算？...类的 hashCode 方法注释已经说明了 ），我知道，HashMap 之所以速度快，因为他使用的是散列表，根据 key 的 hashcode 值生成数组下标（通过内存地址直接查找，没有任何判断），时间复杂度完美情况下可以达到...HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或） 好了，知道了 hashCode 的生成原理了，我们要看看今天的主角，hash 算法。...使用数组长度减一 与运算 hash 值。这行代码就是为什么要让前面的 hash 方法移位并异或。...并且得到的结果取决于 hash 值。因为 hash 值是1，那么最终的结果也是1 ，hash 值是0，最终的结果也是0。 7. HashMap 的容量为什么建议是 2的幂次方？
主要用途 hashcode是Object中的函数，所有类都拥有的一个函数，主要返回每个对象的hash值，主要用于哈希表中，如HashMap、HashTable、HashSet。...Java中HashCode的实现： 在Java中Object.class中有hashCode方法，方法是native 方法，实现就是在JVM中实现的，也就是说他是使用C语言实现的。...实现方式：OpenJDK8 默认hashCode的计算方法是通过和当前线程有关的一个随机数+三个确定值，运用Marsaglia’s xorshift scheme随机数算法得到的一个随机数。...* 因为该表使用2的幂次掩码，所以*仅在当前掩码上方的位中发生变化的*哈希集将**总是发生冲突。 （众所周知的示例是Float键集*在小表中保存连续的整数。）...由于许多常见的哈希集*已经合理地分布了（因此不能从*扩展*中受益），并且由于我们使用树来处理bin中的大量*冲突集，因此我们仅以*最便宜&的方式对一些移位后的位进行XOR运算，减少系统损失，以及*合并最高位的影响
API 和底层实现类以及他们的属性，性能以及使用场景，如何选择随机算法等等，并对 Java 的随机数对于 Java 的一些未来特性的适用进行展望 这是第一篇。...这是一个简单的优化， 实际的优化要比这个复杂多。 初始化这个黑盒的时候，一般采用一个 SEED 进行初始化，这个 SEED 的来源可能多种多样，这个我们先按下不表，先来看一些这个黑盒中的一些算法。...即根据当前 Seed 乘以一个系数 A，然后加上一个偏移 B，最后按照 C 进行取余（限制整体在一定范围内，这样才能选择出合适的 A 和 B，为什么要这么做后面会说），得出随机数，然后这个随机数作为下次随机的种子...异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的每个 bit 进行整体移位。...Java 17 之前一般如何生成随机数以及对应的随机算法 首先放出算法与实现类的对应关系： 使用 JDK 的 API 1.使用 java.util.Random 和基于它的 API： Random random
二狗：threshold 除了用于存放扩容阈值还有其他作用吗？ 囧辉：在我们新建 HashMap 对象时， threshold 还会被用来存初始化时的容量。...二狗：你说 HashMap 的默认初始容量是 16，为什么是16而不是其他的？ 囧辉：（这是什么煞笔问题）我认为是16的原因主要是：16是2的N次方，并且是一个较合理的大小。...囧辉：负载因子默认值是0.75。 二狗：为什么是0.75而不是其他的？ 囧辉：（又问这种憨逼问题）这个也是在时间和空间上权衡的结果。...囧辉：拿到 key 的 hashCode，并将 hashCode 的高16位和 hashCode 进行异或（XOR）运算，得到最终的 hash 值。...2）计算 table 初始容量的方式发生了改变，老的方式是从1开始不断向左进行移位运算，直到找到大于等于入参容量的值；新的方式则是通过“5个移位+或等于运算”来计算。
HashMap的扩容，又被很多人叫rehash、重哈希，我本人是很反对这个叫法的，事实上HashMap扩容的时候，Node中存储的Key的hash值并没有发生变化，只是Node的位置发生了变化。...的初始化其实是resize方法实现的。...因为这里我是以JDK1.8源码作为样本分析的，如果我没记错的话，JDK1.7中还存在rehash方法，但是JDK1.8中已经改名叫resize方法了，那我们就不管JDK1.7中是如何实现扩容，直接上JDK1.8...= 5 key4 00110101 00001101 = 21 到这应该能明白，resize方法里的lo列表和hi列表是什么意思了，其实就是看key高一位的哈希值是1还是0，来决定是放到哪个队列里。...移位后的HashMap如下图： 这里HashMap非常精妙的实现了扩容，没有重新计算对象的哈希值，甚至连下标的重新计算也只需要进行一位相与的计算（hash高位 & newCap-1 )。
地方 , 都可以使用 " 公有继承 " 的 派生类 ( 子类 ) 对象 替代 , 该 派生类 ( 子类 ) 得到了 除 构造函数 和 析构函数 之外的 所有 成员变量 和 成员方法 ; 功能完整性 :..." 公有继承 " 的 派生类 ( 子类 ) 本质上 具有 基类 ( 父类 ) 的 完整功能 , 使用 基类 可以解决的问题 , 使用 公有继承派生类 都能解决 ; 特别注意 : " 保护继承 " 和..." 私有继承 " 的 派生类 , 是 不具有 基类 的 完整功能的 , 因为 最终继承 后的派生类 , 无法在 类外部调用 父类的 公有成员 和 保护成员 ; 2、类型兼容性原则应用场景 " 类型兼容性原则..." 应用场景 : 直接使用 : 使用 子类对象 作为 父类对象 使用 ; 赋值 : 将 子类对象 赋值给 父类对象 ; 初始化 : 使用 子类对象 为 父类对象 初始化 ; 指针 : 父类指针 指向...); } 2、使用 子类对象 为 父类对象 进行初始化 定义父类对象 , 可以直接使用 子类对象 进行初始化操作 ; // II.
1.2.插入键值对： 当调用put(key,value)时，经历以下步骤： ①计算key的哈希值（详见我的之前一篇写HashMap底层哈希值计算的文章），然后将哈希值与数组长度-1进行按位与运算，得到应该存储的数组下标索引...1.4.Hash算法: 1.8版本直接用对应OBject类的hash值计算方法。避免hash碰撞的运算即为简单的：向右移位，并进行异或。hash值用final修饰，一旦确定不再更改。...3.JDK1.8中一些其他细节 3.1.加载因子：在进行扩容时，会进行阈值的判断，这个阈值大小是通过当前的数组的容量和一个加载因子进行确定的。...java源码中关于为什么树化的解释： 由于TreeNodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们（参见 TREEIFY_THRESHOLD 值）。...3.5.为什么把链表转化为红黑树的阈值是8,而不是6、7或者不是20呢？ 这个问题其实和3.3.差不多，但3.3只回答了一部分。 即为什么不是6，是综合了性能和时间效率。 那为什么不是7？
下面将对照HashMap源码来分析的其原理和实现。...HashMap容器的创建，采用了延迟初始化，创建容器时，只是指定了负载系数（loadFactor）和扩展阈值（threshold），真正创建容器，是在put第一个元素的时候；而HashMap的容量被指定为...，根移位之前的数做一次按位或操作； 最后就会得到都是1的数，这个数再加1，还是2的整数平方倍，也就是比指定数大的最小2的整数平方倍 两个问题： 为什么每次1、2、4、8、16移动？...而容器容量为2的整数平方倍，再减一的话，转化成二进制除最高位左面的位上是0，其他所有位都是1，这样做与运算得到的结果，必然落在length内，而且效率要比取模运算快。...key值相等的元素；删除操作包含查找操作，所以链表的时间复杂度是O(n) 红黑树：稍后分析 红黑树 为什么要将链表进行树化操作呢？
二 初始化与懒加载 初始化的时候只会设置默认的负载因子，并不会进行其他初始化的操作，在首次使用的时候才会进行初始化。...而在实现中，JDK并没有直接使用Object的native方法返回的hashCode作为最终的哈希值，而是进行了二次加工。...以下分别为HashMap与ConcurrentHashMap计算hash值的方法，核心的计算逻辑相同，都是使用key对应的hashCode与其hashCode右移16位的结果进行异或操作。...整个过程是找到cap对应二进制中最高位的1，然后每次以2倍的步长（依次移位1、2、4、8、16）复制最高位1到后面的所有低位，把最高位1后面的所有位全部置为1，最后进行+1，即完成了进位。...正在被其他线程锁定，那当前线程也没必要再等待了，直接尝试使用baseCount进行累加。
HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。...n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。...HashMap是基于数组+链表和红黑树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参数确定。 那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。...20.HashMap 内部节点是有序的吗？ HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。...（ HashSet 的源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。...但是问题依旧存在，initialMaxSize的作用是什么？，我们能够知道的是maxSize是一个用于控制容量大小的值。...，但是我觉得还是没啥用，可是是我太菜了吧，这个方法没有其他调用它的方法，是一个我们直接在使用过程中使用的，可能和数据多次使用的一个保存之类的问题相关联把，场景的话也就类似Glide的图片缓存加载把。...做一个猜想好了，既然是使用了put()才会造成双向链表中数据的变换，那我们就应该是需要进入对LinkedHashMap.put()方法中进行查询。...当然有兴趣探索的读者们，我需要提一个醒，就是这次的调用不可以直接进行对put()进行查询，那样只会调用到一个接口函数，或者是抽象类函数，最适合的方法还是使用我们的断点来进行探索查询。
看第14-16行代码，这里做了一个移位运算，保证了初始容量一定为2的幂，假如你传的是5，那么最终的初始容量为8。源码中的位运算随处可见啊=。=! ...加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点，可以想想为什么）。...HashMap所有集合类视图所返回迭代器都是快速失败的(fail-fast)，在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改...至于为什么通过迭代器自身的remove或add方法就不会出现这个问题，可以参考我之前的文章List比较好玩的操作中第三个和第四个示例。 ...HashMap是线程不安全的实现，而HashTable是线程安全的实现，关于线程安全与不安全可以参考我之前的文章Java线程(一)：线程安全与不安全，所谓线程不安全，就是在多线程情况下直接使用HashMap
一、概述 本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中，底层基于散列算法实现。...HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。...另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。 在本篇文章中，我将会对 HashMap 中常用方法、重要属性及相关方法进行分析。...需要说明的是，HashMap 源码中可分析的点很多，本文很难一一覆盖，请见谅。 二、原理 上一节说到 HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。...通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。这也就是为什么 HashMap 不直接使用键对象原始 hash 的原因了。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。...，但是我觉得还是没啥用，可是是我太菜了吧，这个方法没有其他调用它的方法，是一个我们直接在使用过程中使用的，可能和数据多次使用的一个保存之类的问题相关联把，场景的话也就类似Glide的图片缓存加载把。...也就是最近使用的数据应该调换到最后开始的位置，他到底是在哪里进行处理的呢？...做一个猜想好了，既然是使用了put()才会造成双向链表中数据的变换，那我们就应该是需要进入对LinkedHashMap.put()方法中进行查询。...当然有兴趣探索的读者们，我需要提一个醒，就是这次的调用不可以直接进行对put()进行查询，那样只会调用到一个接口函数，或者是抽象类函数，最适合的方法还是使用我们的断点来进行探索查询。
一、概述 本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中，底层基于散列算法实现。...另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。 在本篇文章中，我将会对 HashMap 中常用方法、重要属性及相关方法进行分析。...需要说明的是，HashMap 源码中可分析的点很多，本文很难一一覆盖，请见谅。 二、原理 上一节说到 HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。...HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下： ? 对于拉链式的散列算法，其数据结构是由数组和链表（或树形结构）组成。...通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。这也就是为什么 HashMap 不直接使用键对象原始 hash 的原因了。
HashMap取值非常快”等等。这个时候说明他已经很熟练使用HashMap的工具了。 问：“你知道HashMap 在put和get的时候是怎么工作的吗？”...6、HashMap中的Hash计算和碰撞问题 HashMap的hash计算时先计算hashCode(),然后进行二次hash。...大体意思是说选择31是因为它是一个奇素数，如果它做乘法溢出的时候，信息会丢失，而且当和2做乘法的时候相当于移位，在使用它的时候优点还是不清楚，但是它已经成为了传统的选择，31的一个很好的特性就是做乘法的时候可以被移位和减法代替的时候有更好的性能体现...例如31i相当于是i左移5位减去i，即31i == (i<<5)-i。现代的虚拟内存系统都使用这种自动优化。 现在进入正题，HashMap为什么还要做二次hash呢?...HashMap是否在内部或被其它线程修改，如果modCount和expectedModCount值不一样，证明有其他线程在修改HashMap的结构，会抛出异常。
集合相关类和接口都在java.util中，主要分为3种：List（列表）、Map（映射）、Set(集)。...HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。...HashMap是基于数组+链表和红黑树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参数确定。 那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。...27.HashMap 内部节点是有序的吗？ HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。...（ HashSet 的源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap
HashMap 是 Map 基于哈希散列算法的实现，其在 JDK1.7 中采用了数组+链表的数据结构。在 JDK1.8 中为了提高查询效率，采用了数组+链表+红黑树的数据结构。...没错，HashMap 在创建的时候并不会进行数据的初始化，而是在真正插入的时候才进行初始化操作。这一部分的代码在 resize （扩容）方法中，我们后续会讲到。...HashMap 的扩容机制与其他变长集合的套路不太一样，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。...这是因为扩容后，参与模运算的位数由4位变为了5位。由于两个 27 和 35 两个节点第5位的值是不一样，所以两个 hash 算出的结果也不一样。...3.1.3.1 就是判断如果是 e.hash & oldCap = 0（即原 hash 值某一位位0，那么其位置就不变），那么就放在 loTail 为首的链表中，这个链表存的是扩容后放置在原来桶位置的节点
在日常开发工作中，HashMap是使用频率相当高的一个工具，同时「HashMap」的底层实现和原理，也成了面试题中的常客。最近又翻看了一下源码，做个记录。(本文都是基于jdk1.8的源码) 1....❝在object类中，hashcode()方法是本地方法，返回的是对象的地址值，而object类中的equals()方法比较的也是两个对象的地址值，如果equals()相等，说明两个对象地址值也相等，当然...２、「位运算Hash」这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。...作为不可变类天生是线程安全的。 6. HashMap中hash函数是怎么实现的？为什么不直接将key作为哈希值而是与高16位做异或运算？还有哪些hash函数的实现方式？...7. hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
云直播
实时音视频
