HashMap.md 我会带着你远行 2022-05-11 03:56 76阅读 0赞 哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,而HashMap的实现原理也常常出现在各类的面试题中,重要性可见一斑。 # 一、什么是哈希表 # 在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能 **数组**:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n) **线性链表**:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n) **二叉树**:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。 **哈希表**:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。 我们知道,数据结构的物理存储结构只有两种:**顺序存储结构**和**链式存储结构**(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,**哈希表的主干就是数组**。 比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。 **存储位置 = f(关键字)** 其中,这个函数f一般称为**哈希函数**,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作: !![在这里插入图片描述][70] 查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。 **哈希冲突** 然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的**哈希冲突**,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 **计算简单**和**散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表**的方式, # 二、HashMap实现原理 # HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。 HashMap的整体结构如下 : ![在这里插入图片描述][70 1] 简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。 存储位置的确定流程是这样的: ![在这里插入图片描述][70 2] 基本原理:先声明一个下标范围比较大的数组来存储元素。另外设计一个哈希函数(也叫做散列函数)来获得每一个元素的Key(关键字)的函数值(即数组下标,hash值)相对应,数组存储的元素是一个Entry类,这个类有三个数据域,key、value(键值对),next(指向下一个Entry)。 例如, 第一个键值对A进来。通过计算其key的hash得到的index=0。记做:Entry\[0\] = A。 第二个键值对B,通过计算其index也等于0, HashMap会将B.next =A,Entry\[0\] =B, 第三个键值对 C,index也等于0,那么C.next = B,Entry\[0\] = C;这样我们发现index=0的地方事实上存取了A,B,C三个键值对,它们通过next这个属性链接在一起。我们可以将这个地方称为桶。 对于不同的元素,可能计算出了相同的函数值,这样就产生了“冲突”,这就需要解决冲突,“直接定址”与“解决冲突”是哈希表的两大特点。 HashMap的工作原理以及存取方法过程 HashMap的工作原理 :HashMap是基于散列法(又称哈希法hashing)的原理,使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket(桶)位置来储存Entry对象。”HashMap是在bucket中储存键对象和值对象,作为Map.Entry。并不是仅仅只在bucket中存储值 import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map.Entry; public class HashMapTest { public static void main(String[] args) { HashMap<String, String> map = new HashMap<>(); map.put("zhang", "31");//存放键值对 System.out.println(map.containsKey("zhang"));//键中是否包含这个数据 System.out.println(map.get("zhang"));//通过键拿值 System.out.println(map.isEmpty());//判空 System.out.println(map.remove("zhang"));//从键值中删除 } } 参考链接: [HashMap实现原理及源码分析][HashMap] [Java中HashMap的用法][Java_HashMap] [HashMap原理的深入理解][HashMap 1] [70]: /images/20220511/f3b7bc1705b942c6a834b0d8a2adc913.png [70 1]: /images/20220511/82ed61ebebe3468385448ad29722a174.png [70 2]: /images/20220511/eb4a656bf34349ea9f577dd67347a310.png [HashMap]: https://www.cnblogs.com/chengxiao/p/6059914.html [Java_HashMap]: https://blog.csdn.net/wdays83892469/article/details/79615609 [HashMap 1]: https://www.jb51.net/article/158959.htm
还没有评论,来说两句吧...