序、慢慢来才是最快的方法。
背景
终于到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 算法。散列算法是一种将 “任意长度的输入数据” 映射为 “固定长度的特征值” 的算法,输出的特征值就是散列值。
用一个表格总结散列算法的主要性质:
散列表无法避免的冲突问题
因为 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)是一种抽象数据类型,用于实现数学中图论的无向图和有向图的概念。
图的优缺点
优点:对现实世界建模
缺点:有些算法慢且复杂
参考:
数据结构与常用集合总结 - 掘金文章来源:https://www.toymoban.com/news/detail-726857.html
数据结构与算法 #15 如何实现一个优秀的 HashTable 散列表? - 掘金文章来源地址https://www.toymoban.com/news/detail-726857.html
到了这里,关于HashMap(1)前传的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!