java中的散列表是什么
这篇文章将为大家详细讲解有关java中的散列表,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
创新互联建站是一家专注于成都做网站、成都网站建设与策划设计,疏勒网站建设哪家好?创新互联建站做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:疏勒等地区。疏勒做网站价格咨询:18980820575
什么是散列表
散列表,也叫作哈希表(Hash Table),是一种提供键(Key)和值(Value)的映射关系的数据结构,只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1)。
散列表的工作原理
散列表在本质上是一个数组。我们知道数组可以根据下标来进行随机访问,如a[0], a[1], a[2], a[3], a[4],通过这样来访问,因此其查询效率非常高。而在散列表中,当我们给出一个key的时候,也能立即查询到对应的value。这时我们就需要一个“中转站”,通过某种方式,把Key和数组下标进行转换,而这个中转站就是哈希函数。
不同的语言中,哈希函数的实现方式是不同的。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对象映射到与之冲突的数组位置时,只需要插入到对应的链表中即可。
2.读操作
读操作与写操作对应 ,只需特别处理冲突情况即可。
具体的思路为:通过哈希函数,将待查找的Key值转化为数组下标,然后检查数组中该位置的Key值是否为我们要找的Key,若是,则找到,可以返回该Entry的Value值;否则,沿着链表继续往下查找,看有没有对应的Key值。
例如,我们要查找Key为002936所对应的value时,先将Key转化为数组下标,得到下标为2,检查该元素,发现该元素的Key为002947,不是我们要查询的Key,那么继续沿着链表往下查找。
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中的散列表是什么
文章路径:http://myzitong.com/article/jpcosg.html