HashMap的探究

简介: -

HashMap【重点】

常用方法与map一致

基于哈希表对Map接口的实现,允许空值传入,但是遍历顺序不确定

线程不安全,多个线程同时写入HashMap,可能导致数据的不一致

存储结构:

  • 1.7 数组 + 链表----链表就是解决 hash 值冲突的,使用的是头插法。
  • 1.8 数组 + (链表 | 红黑树)--hashmap 的初始容量是 16,加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍,当数组扩容大于 等于64,且链表长度大于阈值 8,链表就会转成红黑树,查询较快,在链表小于阈值 8 时,使用的是尾插法

基本属性

HashMap类中是node类,含hash,key,value,next

初始容量16,加载因子默认0.75,阈值也就是12,大于阈值就扩容到两倍,当数组大于等于64且链表大于阈值8,链表就会变成红黑树,红黑树变回链表的阈值是6

元素结构--Node

HashMap类中的元素是Node类,翻译过来就是节点,是定义在HashMap中的一个内部类

  • hash:key的哈希值
  • key:节点的key,类型和定义HashMap时的key相同
  • value:节点的value,类型和定义HashMap时的value相同
  • next:该节点的下一节点

HashMap 的索引--Node的存储位置

对16取余

扩容介绍

  • 1.7 数组 + 链表----链表就是解决 hash 值冲突的,使用的是头插法。
  • 1.8 数组 + (链表 | 红黑树)--hashmap 的初始容量是 16,加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍,当数组扩容大于 等于64,且链表长度大于阈值 8,链表就会转成红黑树,查询较快,在链表小于阈值 8 时,使用的是尾插法

树化----链表与红黑树的转换

链表--->红黑树是链表长度达到阈值是8,红黑树--->链表阈值为6。

链表长度设置为8和6的原因

基于泊松分布,因为经过计算,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6,用概率证明。因为8够用了,至于为什么转回来是6,因为如果hash碰撞次数在8附近徘徊,会一直发生链表和红黑树的互相转化,为了预防这种情况的发生,设置为6

重要常量--

  • table:存储元素的数组,总是2的n次幂
  • entrySet:存储具体元素的集
  • size------------------HashMap中实际存在的键值对数量
  • modCount----------记录HashMap内部结构发生变化的次数
  • threshold-----------阈值,表示能容纳的键值对的临界值,等于数组长度*负载因子
  • loadFactor----------负载因子,默认0.75
  • HashMap默认容量--16
  • DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16
  • MAXIMUM_CAPACITY : HashMap的最大支持容量,2^30
  • DEFAULT_LOAD_FACTOR:HashMap的默认负载因子
  • TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树
  • UNTREEIFY_THRESHOLD:Bucket中红黑树存储的Node小于该默认值,转化为链表
  • MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。)


/**

* 默认初始化容量16

    */

   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


   /**

    *  最大容量,如果其中一个带参数的构造函数隐式指定更高的值,则使用该最大容量。

    *  必须是2的幂次方

    */

   static final int MAXIMUM_CAPACITY = 1 << 30;


   /**

    * 默认负载因子,负责管理HashMap在何时开始扩容

    */

   static final float DEFAULT_LOAD_FACTOR = 0.75f;


   /**

    * 转为树的阈值

    */

   static final int TREEIFY_THRESHOLD = 8;


   /**

    * 取消树的值

    */

   static final int UNTREEIFY_THRESHOLD = 6;


   /**

    * 冲突严重时转为红黑树之前的最小阈值

    */

   static final int MIN_TREEIFY_CAPACITY = 64;

   

   

   /**

   *  存储数据的Node数组

   */

   transient Node<K,V>[] table;


   /**

    * Holds cached entrySet(). Note that AbstractMap fields are used

    * for keySet() and values().

    */

   transient Set<Map.Entry<K,V>> entrySet;


  /**

   *  大小

     */

   transient int size;


   /**

    * fail-fast.  (See ConcurrentModificationException).

    */

   transient int modCount;


   /**

    * 下一次应该扩容的大小 (capacity * load factor).

    * 如果尚未扩容,则该字段保存初始entry数组的容量,或用零表示

    */

   int threshold;


   /**

    * 负载因子

    */

   final float loadFactor;


注意!!长度扩大以后,Hash的规则也随之改变。

treeifyBin方法--扩容判断

final void treeifyBin(Node<K,V>[] tab, int hash) {

//n数组长度,index 当前下标,e当前节点

       int n, index; Node<K,V> e;

//判断数组是否为null,判断数组长度是否小于64,如果小于走扩容,不小于走链表转红黑树

       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

           resize(); //扩容

//数组长度减1和hash做与运算的当前下标index,取下标内元素,如果为null结束,不为null赋值给e

       else if ((e = tab[index = (n - 1) & hash]) != null) {

  //hd头节点 tl尾节点

           TreeNode<K,V> hd = null, tl = null;

           do {

  //replacementTreeNode 添加接点e 进TreeNode

               TreeNode<K,V> p = replacementTreeNode(e, null);

  //判断尾节点 为null 说明没有根节点

               if (tl == null)

    //首节点(根节点) 指向当前节点

                   hd = p;

               else {

    //当前树节点的 前一个节点指向 尾节点

                   p.prev = tl;

    //尾节点的 后一个节点指向 当前节点

                   tl.next = p;

               }

  //把当前节点设置为尾节点

               tl = p;

           } while ((e = e.next) != null); //判断当前节点的下 当前节点的下一个节点是否为null 不为null 遍历

  //目前为止 也只是把Node改为TreeNode 也就是单向链表改为双向链表

  //根节点判断是否为 null

           if ((tab[index] = hd) != null)

               hd.treeify(tab); //转红黑树

       }

   }

为什么不一开始就使用红黑树,还要有一个转换的过程

单个 TreeNode 需要占用的空间大约是普通 Node 的两倍,所以只有当包含足够多的 Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式,以便节省空间。

重新实现hash方法-----为什么HashMap重新实现hash方法,直接用hashcode不行么?

减少碰撞

当向 HashMap 中添加一个元素的时候,需要根据 key 的 hash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。我们知道Object的hashcode有32位,而HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标。hash % length实际就是取模,计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1),而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。这也是数组容量为何是 2 的 n 次幂。

小知识:

hash % length 等于 hash & ( length - 1)

hash % length

a=10,b=8,a%8=2

   

hash & ( length - 1)

(前提b为2的整数次幂)

a=1010,b=1000

b-1=0111(任何数&(b-1)得到的数不会大于b,也就相当于对b取余)

     a  1010 10

   b-1  0111  8

a&(b-1)  0010  2

tab[i = (n - 1) & hash])

为什么要进行二次 hash?

HashMap 的 put 流程

网上借来的图

目录
相关文章
|
9月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
6月前
|
前端开发 Java
什么是类加载器,类加载器有哪些?
主要有一下四种类加载器: 1. 启动类加载器(Bootstrap ClassLoader)用来加载java核心类库,无法被java程序直接引用。 2. 扩展类加载器(extensions class loader):它用来加载 Java 的扩展库。Java 虚拟机的实现会提 供一个扩展库目录。该类加载器在此目录里面查找并加载 Java 类。 3. 系统类加载器(system class loader):它根据 Java 应用的类路径(CLASSPATH)来加载 Java 类。一般来说,Java 应用的类都是由它来完成加载的。可以通过 ClassLoader.getSystemClassLoa
|
11月前
|
设计模式 消息中间件 监控
后端开发中的微服务架构:从概念到实践
后端开发中的微服务架构:从概念到实践
|
9月前
|
人工智能 安全 机器人
OpenAI重拾规则系统,用AI版机器人定律守护大模型安全
在人工智能领域,大语言模型(LLM)展现出强大的语言理解和生成能力,但也带来了安全性和可靠性挑战。OpenAI研究人员提出“规则基于奖励(RBR)”方法,通过明确规则引导LLM行为,确保其符合人类价值观和道德准则。实验显示,RBR方法在安全性与有用性之间取得了良好平衡,F1分数达97.1。然而,规则制定和维护复杂,且难以完全捕捉语言的多样性。论文:https://arxiv.org/pdf/2411.01111。
325 13
|
存储 人工智能 自然语言处理
手猫助手Agent技术探索总结(1)
手猫助手Agent技术探索总结
374 6
|
10月前
|
存储 负载均衡 监控
如何利用Go语言的高效性、并发支持、简洁性和跨平台性等优势,通过合理设计架构、实现负载均衡、构建容错机制、建立监控体系、优化数据存储及实施服务治理等步骤,打造稳定可靠的服务架构。
在数字化时代,构建高可靠性服务架构至关重要。本文探讨了如何利用Go语言的高效性、并发支持、简洁性和跨平台性等优势,通过合理设计架构、实现负载均衡、构建容错机制、建立监控体系、优化数据存储及实施服务治理等步骤,打造稳定可靠的服务架构。
219 1
|
JavaScript 前端开发 数据安全/隐私保护
混淆指定js文件
【9月更文挑战第26天】JavaScript 混淆旨在保护代码知识产权、减小文件体积和提高安全性。方法包括变量名和函数名混淆、代码压缩、控制流平坦化及字符串加密。常用工具如 UglifyJS 和 JScrambler 可实现这些功能。然而,混淆可能带来兼容性和调试困难等问题,需谨慎使用并确保法律合规。
195 5
|
SQL XML Java
乐观锁与悲观锁是什么?
本文详细分析了悲观锁和乐观锁的原理、区别、实现方式及应用场景。悲观锁假设冲突频繁,通过加锁保护数据一致性,适用于高并发冲突场景;乐观锁假设冲突较少,通过版本号或时间戳检测冲突,适用于读多写少场景。文章通过具体示例展示了两种锁机制的实现过程,并总结了其优缺点和适用场景,帮助读者根据实际需求选择合适的并发控制机制。
911 4
|
传感器 自动驾驶 安全
深入探讨自动驾驶感知技术:实现无人驾驶的关键
深入探讨自动驾驶感知技术:实现无人驾驶的关键
449 5
|
索引 Python Windows
下载完PyQt5,发现找不到designer.exe问题解决方案
这篇文章提供了几种解决在安装PyQt5后找不到`designer.exe`的检索方法,包括在PyCharm中搜索、使用Windows搜索栏以及利用Everything软件进行查找。