HashMap在Go与Java的底层实现与区别

在Java中

在Java中hash表的底层数据结构与扩容等已经是面试集合类问题中几乎必问的点了。网上有对源码的解析已经非常详细了我们这里还是说说其底层实现。

基础架构

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {private static final long serialVersionUID = 362498820763181265L;// 默认的初始容量是16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;// 当桶(bucket)上的结点数大于等于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8;// 当桶(bucket)上的结点数小于等于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;// 桶中结构转化为红黑树对应的table的最小容量static final int MIN_TREEIFY_CAPACITY = 64;// 存储元素的数组,总是2的幂次倍transient Node<k,v>[] table;// 一个包含了映射中所有键值对的集合视图transient Set<map.entry<k,v>> entrySet;// 存放元素的个数,注意这个不等于数组的长度。transient int size;// 每次扩容和更改map结构的计数器transient int modCount;// 阈值(容量*负载因子) 当实际大小超过阈值时,会进行扩容int threshold;// 负载因子final float loadFactor;
}

本文所有Java代码均来自JavaGuide(HashMap 源码分析 | JavaGuide),这里主要就是定义一些必要的常量,被用于哈希表的创建参数,扩容参数等待。

然后就是hash表中的Node节点的数据结构,我们的k-v键值对就存储在一个Node类里面。在jdk1.7前其实与redis中的字典Dictionary数据结构中的hash表十分类似,即采用线性搜索和拉链法。在jdk1.8 及以后版本1中,添加了树化,即当节点数大于8就会将当前节点转化为红黑树,这样做的目的主要是为了增加搜索效率,红黑树的时间复杂度为O(log n)如果没有树化链表查询的时间复杂度为O(n) 。接下来就看看JavaGuide中给出的节点类:

链表节点:

// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {final int hash;// 哈希值,存放元素到hashmap中时用来与其他元素hash值比较final K key;//键V value;//值// 指向下一个节点Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }// 重写hashCode()方法public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}// 重写 equals() 方法public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}
}

树节点:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // 父TreeNode<K,V> left;    // 左TreeNode<K,V> right;   // 右TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;           // 判断颜色TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}// 返回根节点final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}

resize()

然后我们来重点讲一讲resize()扩容这个方法。

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 超过最大值就不再扩充了,就只好随你碰撞去吧if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 没超过最大值,就扩充为原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in threshold// 创建对象时初始化容量大小放在threshold中,此时只需要将其作为新的数组容量newCap = oldThr;else {// signifies using defaults 无参构造函数创建的对象在这里计算容量和阈值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {// 创建时指定了初始化容量或者负载因子,在这里进行阈值初始化,// 或者扩容前的旧容量小于16,在这里计算新的resize上限float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {// 把每个bucket都移动到新的buckets中for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 只有一个节点,直接计算元素新的位置即可newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 将红黑树拆分成2棵子树,如果子树节点数小于等于 UNTREEIFY_THRESHOLD(默认为 6),则将子树转换为链表。// 如果子树节点数大于 UNTREEIFY_THRESHOLD,则保持子树的树结构。((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else {Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 原索引if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到bucket里if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引+oldCap放到bucket里if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

在Java的hashmap中,在jdk1.8以后是通过负载因子的判断来选择是否进行resize()方法默认负载因子是0.75。如果存储数据与当前容量之比为0.75就会进行扩容。同时当我们存储数据过多时,无论我们的hash算法做了什么样的优化,一定还是会有hash冲突的存在,所以为了解决冲突,我们使用拉链法。在插入数据时,我们采用的方式是将已存在hashmap中的键值对的值与插入的值进行比较,如果二者相等就进行覆盖,如果二者不相等就使用尾加法加载链表尾部(在redis5中,使用的是equals()进行比较,因为redis存储的所有值都是String字符串。)。我们将一个拉链称之为一个哈希桶。但是我们试想如果一个桶的节点过于多了,那么我们查找时遍历起来是很花费时间的,在hashtable中使用的是线性搜索法加拉链法来解决这个问题的,但是如果我们一直盲目使用线性搜索法的话,(我们暂且将线性搜索法占据的hash表数组槽位与hash表当前容量的比值称为线性搜索负载因子)当线性搜索负载因子过大时,我们的hash表的查找效率会受到极大的影响。所有在jdk1.8后的树化则很好解决了这个问题,即当拉链上的节点树大于8时,会先对数组容量进行判断,如果小于64先扩容(hashmap扩容都为2倍扩容),否则进行拉链法。(为什么先扩容呢?因为hashmap的hash函数计算与容量有关所以扩容后会得到新的hash值,避免了hash冲突,相较于红黑树的遍历,我们肯定更优先考虑的是这种做法)

在Golang中

基础架构

type hmap struct {count intflags uint8B uint8noverflow uint16hash0 uint32buckets unsafe.Pointeroldbuckets unsafe.Pointernevacuate uintptrextra *mapextra
}type mapextra struct {overflow *[]*bmapoldoverflow *[]*bmapnextOverflow *bmap
}
  • count 表示当前hash表中的元素。

  • B 表示当前hash表持有的 buckets (即桶数组)数量,由于hash表中桶数量都为2的倍数,所以该字段会存储对数。(这里和redis的hash表一样,在redis的rehash过程中,需要先创建一个2倍旧数组长度的新数组,然后进行hash桶迁移)。

  • oldbuckets是哈希表在扩容时用于保存之前buckets的字段,它的大小是当前buckets的一半。

在go的hashmap中,我们使用溢出桶来降低扩容频率,本质上就是预先分配几个数组空间用于存储超出容量的k-v

扩容方法

  • 开放寻址法

    • 其实就是线性搜索法。简而言之就是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表,当我们向当前哈希表写入新数据时,如果发生了冲突,就会将键值对写入下一个索引不为空的位置。开放寻址法中对性能影响最大的是装载因子,它是数组中元素数量与数组大小的比值。随着装 载因子的增加,线性探测的平均用时会逐渐增加,这会影响哈希表的读写性能。当装载率超过70% 之后,哈希表的性能就会急剧下降,而一旦装载率达到100%,整个哈希表就会完全失效,这时查找 和插入任意元素的时间复杂度都是O(n),我们需要遍历数组中的全部元素,所以在实现哈希表时一 定要关注装载因子的变化。

  • 拉链法

    • 和jdk 1.7 一样,就不做过多解释。

在go中的k-v添加我们需要注意的是当插入的k-v小于25时会以如下方式插入:

hash := make(map[string]int, 3)
hash["1"] = 1
hash["2"] = 2
hash["3"] = 3

如若大于25个,就会分别创建两个数组,分别存储k 和 v,然后以遍历形式插入。

言归正传,在go的hashmap中扩容条件为:装在因子超过6.5 || 哈希表使用太多溢出桶。

同时由于在go的hashmap的扩容不是原子性的所以需要判断以避免二次扩容(这和redis也一样,增删改查需要判断当前数据库的hash表是否在进行rehash)。

扩容数据结构

说了这么多,接下来我们就来重点介绍go的hashmap扩容的数据结构变化。runtime. evacuate会将一个旧桶中的数据分流到两个新桶,所以它会创建两个用于保存分配 上下文的runtime.evacDst结构体,这两个结构体分别指向了一个新桶。

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))newbit := h.noldbuckets()if !evacuated(b) {var xy [2]evacDstx := &xy[0]x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))x.k = add(unsafe.Pointer(x.b), dataOffset)x. v = add(x.k, bucketCnt*uintptr(t.keysize))y := &xy[1Jy. b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))y.k = add(unsafe.Pointer(y.b), dataOffset)y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}

go中的hashamp扩容分为等量扩容和翻倍扩容,如果是前者就只初始化一个桶,如果是翻倍扩容,就会初始化两个桶。会把一个链表数据分到新表两个位置,将8个节点分流到两个桶中(这里获取桶位置采用取模或者位运算来得到数据存储的桶位置),然后将k的指针指向两个桶位置。

在数据查询时,会先判断是否在进行分流,如果在进行,就先会从旧桶中读取数据。相较于Java的hashmap它不会一次性将所有的元素重新哈希,而是在每次插入元素时,都会将一部分元素移动到新的桶中。这样可以避免一次性的大量计算,但可能会导致一段时间内的查询效率稍低。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

通过LabVIEW提升生产设备自动化水平

现代制造业对生产设备的自动化水平提出了越来越高的要求。使用LabVIEW这一强大的图形化编程环境&#xff0c;可以显著提升生产设备的自动化程度&#xff0c;改善生产效率和产品质量。本文将详细分析如何通过LabVIEW改善生产设备的自动化水平&#xff0c;并提供具体的实施策略与…

[数据集][图像分类]骨关节炎严重程度分类数据集14038张4分类

数据集类型&#xff1a;图像分类用&#xff0c;不可用于目标检测无标注文件 数据集格式&#xff1a;仅仅包含jpg图片&#xff0c;每个类别文件夹下面存放着对应图片 图片数量(jpg文件个数)&#xff1a;14038 分类类别数&#xff1a;4 类别名称:[“grade0”,“grade2”,“grade3…

如何定义“智慧校园”这个概念

在信息爆炸的时代&#xff0c;教育面临着前所未有的挑战&#xff1a;如何让每个学生在海量知识中找到属于自己的路径&#xff1f;如何让教师的智慧与科技的力量相得益彰&#xff1f;如何让校园成为培养创新思维的摇篮&#xff1f;智慧校园&#xff0c;这一概念的提出&#xff0…

基于 Redis 实现分布式锁的全过程

前言 这一篇文章拖了有点久&#xff0c;虽然在项目中使用分布式锁的频率比较高&#xff0c;但整理成文章发布出来还是花了一点时间。在一些移动端、用户量大的互联网项目中&#xff0c;经常会使用到 Redis 分布式锁作为控制访问高并发的工具。 一、关于分布式锁 总结&#x…

计算机图形学入门05:投影变换

1.投影变换 上一章已经介绍了投影变换&#xff0c;就是将三维图像投影到二维平面上&#xff0c;而投影变换又分为正交投影(Orthographic Projection)和透视投影(Perspective Projection)。如下图&#xff1a; 正交投影 没有近大远小的现象&#xff0c;无论图形与视点距离是远是…

机器学习学习

机器学习类型(按学习方式分):监督学习、半监督学习、无监督学习、强化学习; 通过已知标签训练集训练模型,使用模型及逆行预测、测试; 向量表示法,其中每一维对应一个特征(feature)或者称为属性,记为[x1,x2,...,xn] 特征值、特征、标签,共同完成训练集的数据填充,最…

设计模式基础知识点(七大原则、UML类图)

Java设计模式&#xff08;设计模式七大原则、UML类图&#xff09; 设计模式的目的设计模式七大原则单一职能原则&#xff08;SingleResponsibility&#xff09;接口隔离原则&#xff08;InterfaceSegreation&#xff09;依赖倒转原则&#xff08;DependenceInversion&#xff0…

Python 关于字符串格式化

在Python中&#xff0c;字符串格式化有以下几种方法&#xff1a; 1.可以使用字符串的str.center(width), str.ljust(width), 和 str.rjust(width)方法来实现字符串的居中、左对齐和右对齐操作。 居中对齐&#xff1a; text "Python" centered_text text.center(10…

pytest-sugar插件:对自动化测试用例加入进度条

摘要 在自动化测试过程中&#xff0c;测试进度的可视化对于开发者和测试工程师来说非常重要。本文将介绍如何使用pytest-sugar插件来为pytest测试用例添加进度条&#xff0c;从而提升测试的可读性和用户体验。 1. 引言 自动化测试是软件开发过程中不可或缺的一部分&#xff…

Django Celery技术详解

文章目录 简介安装和配置创建并调度任务启动Celery Worker在视图中调用异步任务拓展功能 简介 Django Celery 是一个为Django应用程序提供异步任务处理能力的强大工具。它通过与消息代理&#xff08;如RabbitMQ、Redis&#xff09;集成&#xff0c;可以轻松地处理需要长时间运…

Windows11 wsl2编译Android14 使用ASfP Debug windows上启动的模拟器

wsl2的安装和配置 安装&#xff1a; 直接百度搜索最新的wsl2安装教程即可&#xff0c;官网&#xff1a;https://learn.microsoft.com/zh-cn/windows/wsl/install 1. 启用适用于 Linux 的 Windows 子系统(以管理员身份打开 PowerShell 并运行) Enable-WindowsOptionalFeature…

C++ | Leetcode C++题解之第125题验证回文串

题目&#xff1a; 题解&#xff1a; class Solution { public:bool isPalindrome(string s) {int n s.size();int left 0, right n - 1;while (left < right) {while (left < right && !isalnum(s[left])) {left;}while (left < right && !isalnu…

fyne apptab布局

fyne apptab布局 AppTabs 容器允许用户在不同的内容面板之间切换。标签要么只是文本&#xff0c;要么是文本和一个图标。建议不要混合一些有图标的标签和一些没有图标的标签。 package mainimport ("fyne.io/fyne/v2/app""fyne.io/fyne/v2/container"//&…

全国产飞腾模块麒麟信安操作系统安全漏洞

1、背景介绍 目前在全国产飞腾模块上部署了麒麟信安操作系统&#xff0c;经第三方机构检测存在以下漏洞 操作系统版本为 内核版本为 openssh版本为 2、openssh CBC模式漏洞解决 首先查看ssh加密信息 nmap --script "ssh2*" 127.0.0.1 | grep -i cbc 可以通过修改/…

Python | Leetcode Python题解之第125题验证回文串

题目&#xff1a; 题解&#xff1a; class Solution:def isPalindrome(self, s: str) -> bool:n len(s)left, right 0, n - 1while left < right:while left < right and not s[left].isalnum():left 1while left < right and not s[right].isalnum():right - …

【linux】运维-基础知识-认知hahoop周边

1. HDFS HDFS&#xff08;Hadoop Distributed File System&#xff09;–Hadoop分布式文件存储系统 源自于Google的GFS论文&#xff0c;HDFS是GFS的克隆版 HDFS是Hadoop中数据存储和管理的基础 他是一个高容错的系统&#xff0c;能够自动解决硬件故障&#xff0c;eg&#xff1a…

进程与线程(四)

进程与线程&#xff08;四&#xff09; 基于System V IPC对象的进程间通信机制SystemV IPC引入查看Linux系统中IPC工具的方式查看所有IPC工具命令&#xff1a;ipcs 查看指定的IPC工具key值获取方法&#xff1a;ftok()函数 消息队列消息队列的特征&#xff1a;消息队列的操作打开…

Jmeter实战教程入门讲解

前言 通过前面对Jmeter元件的讲解&#xff0c;大家应该都知道常用元件的作用和使用了。编写Jmeter脚本前我们需要知道Jmeter元件的执行顺序&#xff0c;可以看看我这篇性能测试学习之路&#xff08;三&#xff09;—初识Jmeter来了解下。下面我将以工作中的一个简单的实例带大…

使用ssh连接ubuntu

一、下载连接工具 常见的连接工具右fianlshell、xshell等等。在本文章中使用的finalshell&#xff0c;工具可以去官网上下载&#xff0c;官网下载。 二、Ubuntu中配置shh 1、使用下面指令更新软件包&#xff08;常用于下载安装或更新软件时使用&#xff0c;更新到最新的安装…

正邦科技(day1)

1&#xff1a;充电桩工作了两个半小时&#xff0c;已用电量13度电&#xff08;一般的话是一个小时7度电&#xff09; 2&#xff1a;火线&#xff08;红色&#xff0c;棕色&#xff09;&#xff0c;零线&#xff08;蓝色&#xff09; 3&#xff1a;充电桩工作了两个半小时&#…