HashMap的数据结构(超详细版)

这篇具有很好参考价值的文章主要介绍了HashMap的数据结构(超详细版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


影响HashMap性能的两个重要参数以及HashMap的几个重要成员变量

1.初始容量

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

初始容量用来规定哈希表数组的长度,默认值为16,因为16是2的整数次幂的原因,再小数据量下的情况下,能减少哈希冲突,提高性能。在大存储容量数据的时候,也尽量将数组长度定义为2的幂次方,这样能更好的与索引计算公式i=(n-1)&hash配合使用,从而提升性能。

2.加载因子

final float loadFactor;

用来表示HashMap集合中元素的填满程度,默认为0.75f。越大则表示允许填满的元素就多,集合的空间利用率就越高,但是冲突的机会增加。反之,越小则冲突的机会就会越少,但是空间很多就浪费。

所以在设置初始容量时,应优先考虑到初始容量及其他加载因子,预估设置初始容量,最大程度的减少rehash重建内部数据结构的次数,极大的减少了扩容操作。

  • 底层数组
transient Node<K,V>[] table;

保存KV键值对的数组,每个KV键值对都被封装成一个Node对象。

  • 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;//1073741824

HashMap的最大容量值,扩容时如果超出,则不扩容。

  • 扩容阈值
int threshold

用于判断数组是否需要扩,扩容阈值threshold=数组容量×加载因子。

  • KV键值对数量
int size

HashMap底层存储机制概述

jdk1.8以前HashMap内部数据结构使用数组+链表进行存储。(了解即可)
jdk1.8以后HashMap内部数据结构使用数组+链表+红黑树进行存储。

//数组
transient Node<K,V>[] table;
//链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//哈希值
        final K key;//键
        V value;//值
        Node<K,V> next;//下一个元素
}

数组类型为Node[],每个Node都保存了某个KV键值对元素的key、value、hash、next等值。由于next的存在,所以每个Node对象都是一个单向链表中的组成节点。

当新添加一个KV键值对元素时,通过该元素的key的hash值,计算该元素在数组中应该保存的下标位置。如果该下标位置如果已经存在其它Node对象,则采用链地址法处理,即将新添加的KV键值对元素将以链表形式存储。将新元素封装成一个新的Node对象,插入到该下标位置的链表尾部(尾插法)。当链表的长度超过8并且数组长度大于64时,为了避免查找搜索性能下降,该链表会转换一个红黑树
(附带大佬做的好图一张,仅供参考理解)
hashmap结构,数据结构,哈希算法,散列表


HashMap的初始化与扩容方式

1.初始化

HashMap的构造方法进行了重载,具有无参、有参等多种构造方式。
无参构造:默认定义加载因子为0.75

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

指定容量的有参构造:传入所需的最小容量值,依旧使用默认加载因子。

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

指定容量和加载因子的有参构造方法:指定容量值与加载因子。

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

2.扩容方式

HashMap底层采用数组+链表+红黑树,扩容过程中需要按照数组容量加载因子来进行判断。

HashMap的扩容方法是resize()方法,发生下列几种情况时,会发生扩容:文章来源地址https://www.toymoban.com/news/detail-838962.html

// 添加新元素 
final V putVal(int hash, K key, V value){
 //... 
 // 判断当前集合中的元素数量,是否超过阈值threshol
  if (++size > threshold)
            resize();
 }
 //...
  1. 当我们第一次添加KV键值对时,如果数组此时为空,则会默认扩容为16。
  2. 加入元素时,如果链表长度大于阈值(默认为8)并且数组长度小于6,就会产生数组扩容。
  3. 添加元素后,当HashMap中的元素个数超过【数组大小×加载因子】时,原数组扩容2倍。例如:加载因子的默认值为0.75,数组容量默认为16,当HashMap中的元素个数超过16×0.75=12时,数组容量扩容16×2=32。
  4. HashMap加入新元素时,如果链表长度大于8时,会尝试将当前链表转换为红黑树。在转换红黑树之前,会判断数组长度,如果小于64,会产生数组扩容。如果数组长度大于64,才会将链表转换为红黑树。
 final void treeifyBin(Node<K,V>[] tab, int hash) {
	 //...
 	//如果数组长度n小于64或者数组长度为空,		
 	if (tab == null || (n = tab.length) < 	MIN_TREEIFY_CAPACITY)
            resize();//数组扩容
  	//
  	 else if ((e = tab[index = (n - 1) & hash]) != null) {
  	 		//遍历链表节点,转换为红黑树
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

总结

  • HashMap的数据结构采用数组+链表+红黑树。
  • HashMap的按照key的hash值计算数组中的存储位置下标,计算方式:(n-1)&hash。
  • 如果在该下标位置已经存在元素,代表产生哈希冲突,则采用链地址法处理,以单向链表的形式,将新元素存储在链表的尾部(尾插法)。
  • 当链表中Node节点的数量大于8并且数组的长度大于64时,链表会转换成一个红黑树,有利于查找搜索。
  • HashMap的默认容量为16,加载因子为0.75f,当集合元素个数超过扩容阈值【容量×加载因子】时,HashMap会将底层数组容量按照2倍进行扩容。

到了这里,关于HashMap的数据结构(超详细版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [JAVA数据结构]HashMap

    目录 1.HashMap 1.1Map的常用方法 1.2HashMap的使用案例 基于哈希表的实现的Map接口。 Map底层结构 HashMap 底层结构 哈希桶 插入/删除/查找时间复杂度 O(1) 是否有序 无序 线程安全 不安全 插入/删除/查找区别 通过哈希函数计算哈希地址 比较与覆写 自定义类型需要覆写equals和 hashCod

    2024年02月12日
    浏览(61)
  • 数据结构---HashMap和HashSet

    HashMap和HashSet都是存储在哈希桶之中,我们可以先了解一些哈希桶是什么。 像这样,一个数组数组的每个节点带着一个链表,数据就存放在链表结点当中。哈希桶插入/删除/查找节点的时间复杂度是O(1) map代表存入一个key值,一个val值。map可多次存储,当第二次插入时,会更新

    2024年02月06日
    浏览(35)
  • 【Java 数据结构】HashMap和HashSet

    目录 1、认识 HashMap 和 HashSet 2、哈希表 2.1 什么是哈希表 2.2 哈希冲突 2.2.1 概念 2.2.2 设计合理哈希函数 - 避免冲突 2.2.3 调节负载因子 - 避免冲突 2.2.4 Java中解决哈希冲突 - 开散列/哈希桶 3、HashMap 的部分源码解读 3.1 HashMap 的构造方法 3.2 HashMap 是如何插入元素的? 3.3 哈希表

    2024年02月01日
    浏览(43)
  • 【java数据结构】HashMap和HashSet

    目录 一.认识哈希表: 1.1什么是哈希表? 1.2哈希表的表示:  1.3常见哈希函数:  二.认识HashMap和HashSet: 2.1关于Map.Entry的说明:, 2.2Map常用方法说明: 2.3HashMap的使用案例: 2.4Set常见方法说明:  2.5HashSet使用案例: 源码: 之前的学习中,如果我们要查找一个元素,肯定是要经

    2024年03月14日
    浏览(82)
  • java八股文面试[数据结构]——HashMap扩容优化

         知识来源: 【2023年面试】HashMap在扩容上做了哪些优化_哔哩哔哩_bilibili  

    2024年02月11日
    浏览(39)
  • Java-数据结构(二)-Map:HashMap、TreeMap、LinkedHashMap

        Map是Java中常用的数据结构,它提供了一种键值对的存储方式,可以根据键来快速访问值。在本篇文章中,我将学习Java中的Map数据结构     问题是最好的老师,我将从至少以下几个方面阐述,什么是map、使用Map有什么好处、Map的底层原理、map中的key和value分别是

    2024年02月06日
    浏览(37)
  • 源码分析——HashMap(JDK1.8)源码+底层数据结构分析

    HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。 JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈

    2024年02月13日
    浏览(41)
  • Rust 笔记:Rust 语言中哈希结构(哈希映射,HashMap)、集合(哈希集,HashSet)及其使用

    Rust 笔记 Rust 语言中映射(HashMap)与集合(HashSet)及其用法 作者 : 李俊才 (jcLee95):https://blog.csdn.net/qq_28550263?spm=1001.2101.3001.5343 邮箱 : 291148484@163.com 本文地址 :https://blog.csdn.net/qq_28550263/article/details/130876735 【介绍】:本文介绍 Rust 中哈希结构相关概念及其使用。在 R

    2024年02月09日
    浏览(50)
  • 【JavaSE专栏53】Java集合类HashMap解析,基于哈希表的键值对存储结构

    作者主页 :Designer 小郑 作者简介 :3年JAVA全栈开发经验,专注JAVA技术、系统定制、远程指导,致力于企业数字化转型,CSDN学院、蓝桥云课认证讲师。 主打方向 :Vue、SpringBoot、微信小程序 本文讲解了 Java 中集合类 HashMap 的语法、使用说明和应用场景,并给出了样例代码。

    2024年02月15日
    浏览(38)
  • HashMap如何解决哈希冲突

    Hash算法就是把任意长度的输入通过 散列算法 编程固定长度的输出。这个输出结果就是一个 散列值 。 Hash表又称为“ 散列表 ”,它是通过key直接访问到内存存储位置的数据结构。在具体的实现上,我们通过Hash函数把key映射到表中的某个位置,来获取这个位置的数据,从而去

    2023年04月26日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包