HashMap(1)前传

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

序、慢慢来才是最快的方法。

背景

终于到HshMap了,Java集合中非常典型的散列表结构,并且具有面试八股文的称号。

在认识HashMap之前,我们先预热一下HashMap所用到的技术点。

1.简介

HashMap的底层结构是基于分离链表发解决散列冲突的动态散列表。

  • 在Java7中使用数组+链表,发生散列冲突的键值对会使用头插法添加到单链表中;
  • 在Java8中使用数组+链表+红黑树,发生散列冲突的键值对会用尾插发添加到单链表中。如果单链表的长度大于8时且散列表容量大于64,会将链表树转化为红黑树。在扩容再散列时,如果红黑树的长度低于6则会还原给链表。
  • HashMap的数组长度保证是2的整数次幂,默认数组容量是16,默认装载因子上限是0.75,扩容阈值是12(16*0.75)
  • 在创建HashMap对象时,并不会创建底层数组,这是一种懒初始化机制。直到第一次put操作时才会通过resize()扩容操作初始化数组。
  • HashMap的key和value都支持null,key为null的键值对会映射到数组下表为0的桶中。

2.数据结构

数据结构是计算机中存储、组织数据的方式。数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了响应操作的数据元素集合。

简单来说,数据结构是数据的组织、管理和存储格式,其使用目的是搞笑的使用和访问数据。

数据结构主要分为:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、散列表(也叫哈希表)(Hash)、堆(Heap)、图(Graph)。

数据结构又可以分为线性表(全名为线性存储结构。使用线性表存储数据的方式可以这样理解,即“把所有数据用一根线儿串起来,再存储到物理空间中”,包含一维数组、栈、队列、链表)和非线性表

数据结构的存储方式只有两种:数组(顺序存储)和链表(链式存储)

2.1数组(Array)

数组是可以在内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。数组在内存中是顺序存储的,因此可以很好的实现逻辑上的顺序表。

数组的优缺点

数组拥有非常高效的查询能力,给出下角标就能很快的查询到对应元素。从代码实现层面也能看出来数组的增删是很耗时,每一次都要做数据的移动。因此我们总结到数组是适合做改查操作、不适合做增删操作的。

2.2链表(Linked List)

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。

链表的优缺点

链表是写操作快,读操作慢,实际应用场景中,那些需要频繁增删数据的就适合用链表去实现。

PS:说到这里,我们就介绍完了数组和链表,其实️数据结构的存储方式只有两种:数组(顺序存储)和链表(链式存储)。

2.3栈(Stack)

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象资料类型,只允许在有序的线性资料集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。

栈的优缺点

优点:由于栈中存放数据的结构是后放进去的数据先取出来(后进先出),针对一些操作需要取最新数据时,选择栈作为数据结构是最合适的。

缺点:访问栈中的任意数据时,就需要从最新的数据开始取,效率较低。

2.4队列(Queue)

队列,又称为伫列(queue),计算机科学中的一种抽象资料型别,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。

队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

队列的优缺点

队列是一种比较特殊的线性结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。

进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列中最先插入的元素也将最先被删除,对应的最后插入的元素将最后被删除。

因此队列又称为“先进先出”(FIFO—first in first out)的线性表,与栈(FILO-first in last out)刚好相反。

2.5散列表(也叫哈希表)(Hash)

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

散列表是基于散列思想实现的 Map 数据结构,散列思想是散列表的核心特性,也就做哈希算法或 Hash 算法。散列算法是一种将 “任意长度的输入数据” 映射为 “固定长度的特征值” 的算法,输出的特征值就是散列值。

用一个表格总结散列算法的主要性质:

HashMap(1)前传,源码分析,HashMap

散列表无法避免的冲突问题

因为 Hash 算法会将非常大甚至无穷大的输入值域映射到 “固定长度的特征值”,所以 Hash 算法一定是压缩映射。例如,MD5 的输出散列值为 128 位,SHA256 的输出散列值为 256 位,这就存在 2 个不同的输入产生相同输出的可能性。这就是散列冲突或哈希冲突(Hash Collision)问题。

事实上,在散列表的设计中存在 2 次散列冲突:

  • 第 1 次 - hash 函数的散列冲突: 这是一般意义上的散列冲突;

  • 第 2 次 - 散列值取余转数组下标: 本质上,将散列值转数组下标也是一次 Hash 算法,也会存在散列冲突。同时,这也说明 HashMap 中同一个桶中节点的散列值不一定是相同的。

Java 中的字符串 "Aa" 与 "BB" 的就存在散列冲突。

String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  // 2112
System.out.println(str2.hashCode());  // 2112 散列冲突

由于我们无法避免散列冲突,所以只能保证散列表不会因为散列冲突而失去正确性。常用的散列冲突解决方法有 2 类:

  • 开放寻址法: 例如 ThreadLocalMap;
  • 分离链表法: 例如 HashMap。
解决哈希冲突的方法

1.开放寻址(Open Addressing)的核心思想是: 在出现散列冲突时,在数组上重新探测出一个空闲位置。 经典的探测方法有线性探测(Linear Probing)、平方探测(Quadratic Probing)和双散列探测(Double Hashing Probing)

2.分离链表法(Separate Chaining)的核心思想是: 在出现散列冲突时,将冲突的元素添加到同一个桶(Bucket / Slot)中,桶中的元素会组成一个链表,或者跳表、红黑树等动态数据结构。

影响散列表性能的因素

影响散列表性能的关键在于 “散列冲突的发生概率”,冲突概率越低,时间复杂度越接近于 O(1)。 那么,哪些因素会影响冲突概率呢?主要有 3 个:装载因子、冲突解决方法、散列函数。

哈希表的优缺点

优点:哈希表不仅速度快,编程实现也相对容易

缺点:哈希表也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据。

2.6树(Tree)

树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n> 0)个有限节点组成一个具有层次关系的集合。

2.7堆(Heap)

堆(英语:Heap)是计算机科学中的一种特别的完全二叉树。若是满足以下特性,即可称为堆:“给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于)C的值”。若母节点的值恒小于等于子节点的值,此堆称为最小堆(min heap);反之,若母节点的值恒大于等于子节点的值,此堆称为最大堆(max heap)。在堆中最顶端的那一个节点,称作根节点(root node),根节点本身没有母节点(parent node)。

堆的优缺点

优点:插入,删除快,对最大数据的项存取很快

缺点:对其他数据项存取很慢

2.8图(Graph)

图(英语:graph)是一种抽象数据类型,用于实现数学中图论的无向图和有向图的概念。

图的优缺点

优点:对现实世界建模

缺点:有些算法慢且复杂

参考:

数据结构与常用集合总结 - 掘金

数据结构与算法 #15 如何实现一个优秀的 HashTable 散列表? - 掘金文章来源地址https://www.toymoban.com/news/detail-726857.html

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

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

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

相关文章

  • HashMap底层源码解析及红黑树分析

    HashMap线程不安全,底层数组+链表+红黑树 面试重点是put方法,扩容 HashMap的put方法,首先通过key去生成一个hash值,第一次进来是null,此时初始化大小为16,i = (n - 1) hash计算下标值,第一次获取是null,直接放入一个Node节点,如果不是null,分成下面三种情况 1)如果发现hash和

    2024年02月02日
    浏览(48)
  • 一篇文章,轻松拿捏大厂必问的HashMap源码分析

    目录 一,JDK8之后HashMap的新特性 二,hashMap源码属性解读 (一),默认初始化容量数量:16 (二),最大数组容量:2^30 (三),默认负载因子:0.75f (四),触发树化条件1,链表阈值: (五),解树化的阈值:  (六),触发树化条件二,hash桶阈值(数组元素个数): 三

    2023年04月08日
    浏览(75)
  • [JDK8下的HashMap类应用及源码分析] 数据结构、哈希碰撞、链表变红黑树

    [Java基础] StringBuffer 和 StringBuilder 类应用及源码分析 [Java基础] 数组应用及源码分析 [Java基础] String,分析内存地址,源码 [JDK8环境下的HashMap类应用及源码分析] 第一篇 空构造函数初始化 [JDK8环境下的HashMap类应用及源码分析] 第二篇 看源码了解HashMap的扩容机制 [JDK8环境下的

    2024年02月10日
    浏览(42)
  • 【HashMap1.8源码】十分钟带你深入HashMap1.8源码逐行解析

    四个点核心点 初始化 PUT 扩容 GET Node结构 transient NodeK,V[] table; 初始化时为空的Node数组 Treenode结构 四个构造方法 initialCapacity:初始容量,默认是 tableSizeFor (initialCapacity),根据传参找一个大于该数的2次幂数,比如定义是10,则初始化是16 loadFactor:负载因子,this.loadFactor = DEF

    2024年02月15日
    浏览(54)
  • HashMap源码详解

    HashMap是Java语言中的一种集合类,它实现了Map接口,用于存储Key-Value对。它基于哈希表数据结构,通过计算Key的哈希值来快速定位Value的位置,从而实现高效的插入、删除和查找操作。下面我们对照着 JAVA1.8 中的HashMap源码来分析一下它的内部实现逻辑 在开始分析HashMap的实现逻

    2024年02月06日
    浏览(39)
  • HashMap源码解析

    成员变量定义了一些初始化相关和扩容相关的参数。 提供了四个构造方法,空参,设置容量,设置容量和负载因子,通过Map构造HashMap。除了最后一个,其他的都是只设置了容量大小和负载因子。 调用putVal,参数中第一个是计算key的hash值。 调用对象的hashCode方法,返回一个

    2024年02月08日
    浏览(39)
  • HashMap源码阅读(一)

    HashMap继承抽象类AbstractMap,AbstractMap抽象类实现了Map接口 一、HashMap中的静态常量 二、HashMap中的Node节点 Node节点是用于存储存储哈希表中的键值对的结构通过nent变量,将出现冲突的元素连成一个链表 三、HashMap中的成员变量 四、HashMap的构造函数 五、Map中的简单方法 1、将一

    2024年02月10日
    浏览(40)
  • 由浅入深了解HashMap源码

           由经典面试题引入,讲解一下HashMap的底层数据结构?这个面试题你当然可以只答,HashMap底层的数据结构是由(数组+链表+红黑树)实现的,但是显然面试官不太满意这个答案,毕竟这里有一个坑需要你去填,那就是在回答HashMap的底层数据结构时需要考虑JDK的版本,因

    2023年04月13日
    浏览(42)
  • 【Java】JDK1.8 HashMap源码,put源码详细讲解

       📝个人主页:哈__ 期待您的关注  在Java中,HashMap结构是被经常使用的,在面试当中也是经常会被问到的。这篇文章我给大家分享一下我对于HashMap结构源码的理解。 HashMap的存储与一般的数组不同,HashMap的每一个元素存储的并不是一个值,而是一个引用类型的Node结点,这

    2024年04月13日
    浏览(44)
  • 【HashMap】| 深度剥析Java SE 源码合集Ⅱ | 你会吗?

    HashMap 是 Map 接口的接口实现类,它采用哈希算法实现,是 Map 接口最常用的实现类。 由于底层采用了哈希表存储数据,所以要求键不能重复,如果发生重复,新的值会替换旧的值。 HashMap 在 查找、删除、修改方面都有非常高的效率 。 HashMap 底层实现采用了哈希表,既集合了

    2024年01月22日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包