java中关于散列表的详细介绍

java中关于散列表的详细介绍

什么是散列表

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

在线学习视频推荐：java视频教程

散列表的工作原理

散列表在本质上是一个数组。我们知道数组可以根据下标来进行随机访问，如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入门教程