【HashMap篇】HashMap实现原理|put方法|扩容机制|寻址算法|1.7情况下的多线程死循环问题

目录

 一、二叉树、红黑树、散列表简单介绍

1.二叉树

(1)什么是二叉树

(2)什么是二叉搜索树

2.红黑树

(1)什么是红黑树

3.散列表

(1)什么是散列表

(2)散列冲突

(3)散列冲突-链表法(拉链)

二、HashMap实现原理

🔥1.说一下HashMap的实现原理?

2.HashMap的jdk1.7和jdk1.8有什么区别

🔥三、HashMap的put方法具体流程

1.添加数据流程图

2. 具体流程

🔥 四、HashMap的扩容机制

1.扩容流程

2. 具体流程

🔥  五、hashMap的寻址算法

1.hashMap的寻址算法

2.为何HashMap的数组长度一定是2的次幂?

六、hashmap在1.7情况下的多线程死循环问题


 一、二叉树、红黑树、散列表简单介绍

1.二叉树

(1)什么是二叉树

● 每个节点最多有两个“叉”,分别是左子节点和右子节点

● 不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点

● 二叉树每个节点的左子树和右子树也分别满足二叉树的定义

(2)什么是二叉搜索树

● 二叉搜索树(Binary Search Tree,BST)又名二叉查找树,有序二叉树

● 在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值而右子树节点的值都大于这个节点的值

● 没有键值相等的节点

● 通常情况下二叉树搜索的时间复杂度为O(logn),但是当二叉搜索树退化成链表了,时间复杂度就为O(n)


2.红黑树

(1)什么是红黑树

● 红黑树(Red Black Tree):也是一种自平衡的二叉搜索树(BST)

● 所有的红黑规则都是希望红黑树能够保证平衡

● 红黑树的时间复杂度:查找、添加、删除都是O(logn)


3.散列表

(1)什么是散列表

● 散列表(Hash Table)又名哈希表/Hash表

● 根据键(Key)直接访问在内存存储位置值(Value)的数据结构

● 由数组演化而来的,利用了数组支持按照下标进行随机访问数据

(2)散列冲突

● 散列冲突又称哈希冲突,哈希碰撞

● 指多个key映射到同一个数组下标位置

(3)散列冲突-链表法(拉链)

● 数组的每个下标位置称之为桶(bucket)或者槽(slot)

● 每个桶(槽)会对应一条链表

● hash冲突后的元素都放到相同槽位对应的链表中或红黑树中


二、HashMap实现原理

🔥1.说一下HashMap的实现原理?

● 底层使用hash表数据结构,即数组+(链表|红黑树)

● 添加数据时,计算key的值确定元素在数组中的下标

         • key相同则替换

         • 不同则存入链表或红黑树(当链表的长度>=8 & 数组长度>=64 转化为红黑树)

● 获取数据通过key的hash计算数组下标获取元素

2.HashMap的jdk1.7和jdk1.8有什么区别

● JDK1.8之前采用的拉链法,数组+链表

● JDK1.8之后采用数组+链表+红黑树,链表的长度>=8且数组长度>=64 则从链表转化为红黑树


🔥三、HashMap的put方法具体流程

1.添加数据流程图

2. 具体流程

(1)判断table==null ,否则执行resize()扩容(初始化)

(2)根据键值对key计算hash值得到数组索引

(3)判断table[i]==null,成立直接添加节点

(4)不成立:

        <1>判断table[i]的首个元素是否和key一样,如果相同直接覆盖value

        <2>不相同情况一:判断table[i]是否为红黑树,如果是,直接在树中插入键值对

        <3>不相同情况二:不是红黑树,那么就是链表尾部插入,插入后看链表的长度>=8 & 数组长度>=64 ,满足就转化为红黑树

(5)插入成功后,判断size 是否> 最大容量(即数组长度 * 0.75),超过就扩容


🔥 四、HashMap的扩容机制

1.扩容流程

2. 具体流程

● 添加元素/初始化的时候需要调用resize()方法进行扩容,第一次添加数据初始化数组的长度为16,后面达到扩容阈值再扩容(数组长度 * 0.75)

● 每次扩容都是扩容之前的两倍

● 扩容后需要把老数组移到新数组中

        • 没有hash冲突的节点,直接使用 e.hash & (newCap -1)计算新数组的索引位置

        • 如果是红黑树,直接添加

        • 如果是链表,则需要遍历链表,可能需要拆分链表,判断(e.hash & oldCap)== 0,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上


🔥  五、hashMap的寻址算法

1.hashMap的寻址算法

● 计算对象的 hashCode()

● 再进行调用 hash()方法进行二次哈希,hashcode值右移16位再异或运算,让哈希分布更为均匀

● 最后(capacity-1)& hash 得到索引

2.为何HashMap的数组长度一定是2的次幂?

● 计算索引时效率更高:如果是2的n次幂可以使用位与运算代替取模

● 扩容时重新计算索引效率更高:hash & oldCap ==0的元素留在原来位置 ,否则新位置=旧位置+ oldCap


六、hashmap在1.7情况下的多线程死循环问题

● 在jdk1.7的hashmap中在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环

● 比如说,现在有两个线程

线程一:读取到当前的hashmap数据,数据中一个链表,在准备扩容时,线程二介入

线程二:也读取hashmap,直接进行扩容。因为是头插法,链表的顺序会进行颠倒过来。比如原来的顺序是AB,扩容后的顺序是BA,线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表,再将B插入到链头,由于另外一个线程的原因,B的next指向了A,所以B->A->B,形成循环

● 当然,JDK 8 将扩容算法做了调整,不再将元素加入链表头(而是保持与扩容前一样的顺序),尾插法,就避免了jdk7中死循环的问题

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/920766.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI 大模型重塑软件开发的未来

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

idea 配置 leetcode插件 代码模版

开启自定义模版 codeFileName&#xff1a; $!velocityTool.camelCaseName(${question.titleSlug})Code Template&#xff1a; ${question.content} package leetcode.editor.cn; /*** ${question.title}* author lww* since $!velocityTool.date()*/ public class $!velocit…

微软Microsoft有许多耳熟能详的软件?

微软有许多耳熟能详的软件&#xff0c;以下是一些比较有代表性的&#xff1a; 一、软件类 操作系统&#xff1a; Windows 系列&#xff1a;这是微软最为著名且广泛使用的操作系统&#xff0c;如 Windows 10、Windows 11 等。它为全球绝大多数个人电脑提供了操作平台&#xff0c…

Confluence|Confluence报错:连接MySQL数据库失败

报错信息&#xff1a;Problem connecting to your database 解决方案&#xff1a; 增加一个mysql驱动jar包到容器内部 docker cp ./mysql-connector-java-8.0.19.jar confluence:/opt/atlassian/confluence/confluence/WEB-INF/lib/ 作者&#xff1a;Kkoo 链接&#xff1a;ht…

扣子(Coze):构建智能助手并嵌入个人网站的新选择

首发地址&#xff08;欢迎大家访问&#xff09;&#xff1a;扣子&#xff08;Coze&#xff09;&#xff1a;构建智能助手并嵌入个人网站的新选择 1. 前言 之前写了一篇关于使用 MaxKB 搭建个人知识库并集成到个人网站的博客&#xff1b; 整个技术路线我觉得还是很好的&#x…

LeetCode - #139 单词拆分

文章目录 前言摘要1. 描述2. 示例3. 答案题解动态规划的思路代码实现代码解析1. **将 wordDict 转换为 Set**2. **初始化 DP 数组**3. **状态转移方程**4. **返回结果** **测试用例**示例 1:示例 2:示例 3: 时间复杂度空间复杂度总结关于我们 前言 本题由于没有合适答案为以往遗…

SpringCloud篇(服务保护 - Sentinel)

目录 一、雪崩问题及解决方案 1. 雪崩问题 2. 解决方案 方案一&#xff1a;超时处理 方案二&#xff1a;仓壁模式 方案三&#xff1a;断路器模式 方案四&#xff1a;限流 3. 总结 二、服务保护技术对比 三、Sentinel介绍与安装 1. 初识Sentinel 2. Sentinel 优势 3…

MACOS开发、使用常见问题汇总

MACOS常见问题 本文记录使用macos遇到的常见问题&#xff0c;后面会持续更新&#xff0c;觉得有用的可以收藏一下。 打不开xxx.app&#xff0c;因为它来自身份不明的开发者解决方法(开启任何来源) 打开终端&#xff08;Terminal&#xff09;程序 拷贝sudo spctl --master-di…

网络安全之国际主流网络安全架构模型

目前&#xff0c;国际主流的网络安全架构模型主要有&#xff1a; ● 信息技术咨询公司Gartner的ASA&#xff08;Adaptive Security Architecture自适应安全架构&#xff09; ● 美国政府资助的非营利研究机构MITRE的ATT&CK&#xff08;Adversarial Tactics Techniques &…

Linux下 GDB调试器的使用

文章目录 1. 可执行程序的Debug版和Release版区别一、编译选项与目的二、性能与体积三、功能与特性四、查看可执行文件 2. GDB 相关命令GDB常用命令 1. 可执行程序的Debug版和Release版区别 一、编译选项与目的 Debug版&#xff1a; 编译选项&#xff1a;通常使用包含调试信息…

RN开发搬砖经验之—Layout Inspector看不到 DecorView

最近我发现自己已经很久没有使用Layout Inspector这个工具了。今天&#xff0c;为了深入分析React Native&#xff08;RN&#xff09;框架中的一个UI问题&#xff0c;我需要查看RN组件对应的Android原生组件视图层级&#xff08;View tree&#xff09;的实际情况。因此&#xf…

go-zero(三) 数据库操作

go-zero 数据库操作 在本篇文章中&#xff0c;我们将实现一个用户注册和登录的服务。我们将为此构建一个简单而高效的 API&#xff0c;包括请求参数和响应参数的定义。 一、Mysql连接 1. 创建数据库和表 在 MySQL 中创建名为 test_zero的数据库&#xff0c;并创建user 表 …

23种设计模式-模板方法(Template Method)设计模式

文章目录 一.什么是模板方法模式&#xff1f;二.模板方法模式的特点三.模板方法模式的结构四.模板方法模式的应用场景五.模板方法模式的优缺点六.模板方法模式的C实现七.模板方法模式的JAVA实现八.代码解析九.总结 类图&#xff1a; 模板方法设计模式类图 一.什么是模板方法模…

uniapp实现开发遇到过的问题(持续更新中....)

1. 在ios模拟器上会出现底部留白的情况 解决方案&#xff1a; 在manifest.json文件&#xff0c;找到开源码视图配置&#xff0c;添加如下&#xff1a; "app-plus" : {"safearea":{"bottom":{"offset" : "none" // 底部安…

Python Matplotlib 安装指南:使用 Miniconda 实现跨 Linux、macOS 和 Windows 平台安装

Python Matplotlib 安装指南&#xff1a;使用 Miniconda 实现跨 Linux、macOS 和 Windows 平台安装 Matplotlib是Python最常用的数据可视化工具之一&#xff0c;结合Miniconda可以轻松管理安装和依赖项。在这篇文章中&#xff0c;我们将详细介绍如何使用Miniconda在Linux、mac…

【element-tiptap】Tiptap编辑器核心概念----结构篇

core-concepts 前言&#xff1a;这篇文章来介绍一下 Tiptap 编辑器的一些核心概念 &#xff08;一&#xff09;结构 1、 Schemas 定义文档组成方式。一个文档就是标题、段落以及其他的节点组成的一棵树。 每一个 ProseMirror 的文档都有一个与之相关联的 schema&#xff0c;…

window的wsl(Ubuntu)安装kafka步骤

环境&#xff1a;Win11 WSL(Linux子系统Ubuntu) apache-zookeeper-3.9.3-bin kafka_2.12-3.8.1 思路&#xff1a;apache上分别下载zookeeper和kafka&#xff0c;在wsl环境安装。在kafka上创建消息的topic&#xff0c;发送消息&#xff0c;接受消息&#xff0c;验证是否安…

Notepad++--在开头快速添加行号

原文网址&#xff1a;Notepad--在开头快速添加行号_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Notepad怎样在开头快速添加行号。 需求 原文件 想要的效果 方法 1.添加点号 Alt鼠标左键&#xff0c;从首行选中首列下拉&#xff0c;选中需要添加序号的所有行的首列&#xff…

机器学习基础06_梯度下降

目录 一、为什么使用梯度下降 二、什么是梯度下降 三、为什么要用梯度下降 四、怎么进行梯度下降 1、微分 1.单变量的微分 2.多变量的微分 2、梯度 3、步骤 (1)学习率α (2)梯度(导数)前的负号 4、实例实现 五、sklearn梯度下降 一、为什么使用梯度下降 前面利用正…

《Vue零基础入门教程》第二课:搭建开发环境

往期内容&#xff1a; 《Vue零基础入门教程》第一课&#xff1a;Vue简介 1 搭建开发环境 Vue环境分为两种 不使用构建工具使用构建丁具 首先&#xff0c;我们会介绍 不使用构建工具 的环境,在组件化章节中介绍 使用构建工具 的方式 1) 初始化 使用如下指令初始化 npm i…