什么是散列表

散列表,也叫作哈希表(Hash Table),是一种提供键(Key)和值(Value)的映射关系的数据结构,只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1)。

e419b45d76fbab9af429bb1a2369216.png

在线学习视频推荐:java视频

散列表的工作原理

散列表在本质上是一个数组。我们知道数组可以根据下标来进行随机访问,如a[0], a[1], a[2], a[3], a[4],通过这样来访问,因此其查询效率非常高。而在散列表中,当我们给出一个key的时候,也能立即查询到对应的value。这时我们就需要一个“中转站”,通过某种方式,把Key和数组下标进行转换,而这个中转站就是哈希函数。

839e0a0e425812541792c58e9cf363d.png

不同的语言中,哈希函数的实现方式是不同的。Java中使用的是HashMap

在Java及大多数的面向对象的语言中,每个对象都有属于自己的hashcode,用以区分不同的对象,而这个hashcode是一个整形变量。此时我们就需要将这个整形变量转化成数组的下标,最简单的转化方式是对数组长度进行取模。

公式如下:

index = HashCode(key) % Array.length

举个例子:

给出一个长度为8的数组,我们要查找key为"001121"所对应的Vaule,而"001121"的hashcode为1420036703,那么就可通过下面的计算先得到数组下标:

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7

散列表的读写操作

1.写操作

写操作就是在散列表中插入新的键值对(jdk中叫做Entry)。

具体的做法是:通过哈希函数将key值转化为数组下标,然后在数组的该位置处插入Entry(注意是Entry键值对Key+Value,而不仅仅是Value)。可想而知,不同的key值可能会转化为相同的下标,那么此时就成为哈希冲突。

解决哈希冲突常用的方法是开放寻址法和链表法。

开放寻址法的基本思路是:当发生哈希冲突时,就把Entry放到下一个数组中为空的位置,也就是逐个往后移动。

链表法(应用在Java的HashMap集合类中)的基本思想是:数组中的每个元素不仅是一个Entry对象,同时也是一个链表的头节点。每个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry对象映射到与之冲突的数组位置时,只需要插入到对应的链表中即可。

4fda9070d54bd388af9487b0fbf72bb.png

2.读操作

读操作与写操作对应 ,只需特别处理冲突情况即可。

具体的思路为:通过哈希函数,将待查找的Key值转化为数组下标,然后检查数组中该位置的Key值是否为我们要找的Key,若是,则找到,可以返回该Entry的Value值;否则,沿着链表继续往下查找,看有没有对应的Key值。

例如,我们要查找Key为002936所对应的value时,先将Key转化为数组下标,得到下标为2,检查该元素,发现该元素的Key为002947,不是我们要查询的Key,那么继续沿着链表往下查找。

69e8c5ecdab3b0f094a8c85a0e56d45.png

3.扩容

我们知道数组扩容,是当数组中的元素个数达到数组的最大长度时需要对数组扩容,那么散列表什么时候扩容呢?

当经过多次元素插入,散列表达到一定的饱和度时,发生哈希冲突的概率会变大,此时大量的元素拥挤在相同的数组下标位置,这对后序的插入和查询操作的性能产生很大的影响,此时就需要对散列表扩容。

影响散列表扩容的因素为:

Capacity,即HashMap的当前长度

LoadFactor,即HashMap的负载因子,默认值为0.75

扩容需要满足的条件:

HashMap.Size >= Capacity X LoadFactor

简单解释为:当哈希表中的条目数超出了当前容量与其加载因子的乘积时,并且要存放的位置已经有元素了(哈希碰撞),这两个条件满足时,需要进项扩容,会将容量扩大为原来的两倍。加载因子默认值0.75,是在空间和时间上的一个折中,加载因子过高(发生冲突可多存放在链表),虽然减少了空间成本,但也增加了查询成本。

扩容的步骤:

扩容不是简单地把散列表的长度扩大,而是经历了下面两个步骤:

1.扩容,创建一个新的Entry空数组,长度时原数组的2倍;

2.重新Hash,遍历原Entry数组,所有的Entry重新Hash到新数组中。

经过扩容,原本拥挤的散列表重新变得稀疏,原有的Entry也重新得到了尽可能均匀的分配。需要注意的是,关于HashMap的实现,JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时,为了提高插入和查找的效率,HashMap会把Entry的链表转化为红黑树这种数据结构。

相关文章教程推荐:java语言入门

以上就是java中关于散列表的详细介绍的详细内容,更多请关注自学java网其它相关文章!

声明:有的资源均来自网络转载,版权归原作者所有,如有侵犯到您的权益 请联系邮箱:our333@126.com我们将配合处理!

原文地址:java中关于散列表的详细介绍发布于2021-11-26 11:11:25