哈希表基本原理

哈希表原理

1.引言

百度百科是这样说的：

哈希表(Hashtable)又称为散列表,是根据关键码值（key-value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

那哈希表具体的原理又是什么？

首先，我们可以比较一下各个结构的查找速度：

1. 在无序数组中按照内容查找，效率低下，需要使用for循环去一个一个地比较，时间复杂度是O(n)
2. 在有序数组中按照内容查找，我们可以使用折半查找，效率就有所提升，时间复杂度为O(log2^n)
3. 在二叉平衡树中按照内容查找，它的查找原理和折半查找类似，时间复杂度也是O(log2^n)
4. 在数组中按照索引去查询，不进行内容的比较，可以根据【指定索引的元素位置=数据的起始位置 每个元素的大小*索引】来进行计算，这种方式效率最高，时间复杂度为O(1)

从上面的“查找效率”来看，我们思考一下，能否在按照内容查找的时候，也可以不进行比较，而是通过计算得到地址，从而实现查找效率的最大化呢？ 答案是肯定的，我们可以使用哈希表来实现效率最大化！

2.哈希表的结构及其特点

从上边的分析，我们可以得出哈希表的特点就是：效率非常快！

哈希表的结构也是多样的，但是目前最流行还是 ：顺序表 链表 的结构。顾名思义，它是由顺序表和链表组成的，主结构是顺序表，从每一个顺序表的节点可以单独引出一个链表，也可以成为是“拉链”。

结构如下：【每一个顺序表的节点也可以称为桶，顺序表的索引也可以被称为桶的索引】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TNbunrDM-1646628259451)(E:\java笔记\笔记\哈希表结构.png)]

3.哈希表添加数据

哈希表是如何添加数据的？只需三步！

1. 计算哈希码 --> 调用hashCode()

2. 计算在哈希表中的存储位置 --> y=k(x)=x%n 【其中，y就是计算得出的位置，k(x)表示哈希码和位置之间的关系，n是顺序表的大小】

3. 将值(value)存入哈希表中

   存数据也分为三种情况：

   第一种是一次就添加成功了；【这种情况是：计算出要添加到的存储位置在顺序表中还是空的，所以直接就添加进去了】

   第二种就是多次添加，最后成功了；【这种情况是：计算出要添加到的存储位置在顺序表中已经存储数据了了，这时候就存在了哈系冲突（碰撞），再经过equals()逐一比较后，确定与这个位置其他数据不存在重复，就可以进行“拉链”，这时添加成功】

   第三种就是添加失败。【这种情况是：经过第二种情况时，在比较的过程中，发现与其他某个数据重复了，就会添加失败】

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mT6XhHMQ-1646628259453)(E:\java笔记\笔记\哈希表添加数据.png)]

由此，我们可以推断出：

哈希表添加数据快，是数据唯一的，并且添加的顺序是无序的。

哈希表数据的查询也和添加的步骤是一样的，先计算哈希码，再计算存储位置，然后再去查询是否有该数据。故它的查询速度也是很快的。

4.hashCode和equals的作用

在哈希表中，hashCode和equals尤为重要，那它们具体作用是什么呢？

• hashCode() : 用来计算哈希码，返回值是整数，可以根据哈希码计算出数据在哈希表中的存储位置。整数的hashCode就是本身，其他数据类型可以查看其源码。

• equals() : 添加时出现哈希冲突（碰撞），需要通过equals方法进行比较，判断是否相同；在查询过程中，也需要equals进行比较，判断与所查询的值是否相同。

注意： 我们在需要使用哈希码的地方，除了基本的、已经定义好hashCode()的类,其他的自定义的类一定要重写hashCode()和equals方法，避免计算出现不必要的问题。

例如：

问题：HashSet、LinkedHashSet集合都有数据唯一性的特点，为什么分别放入String类型的数据和自定义Student类型的数据后，结果不同，String的遍历后没有重复数据，但是Student的还有重复数据？

分析： 任意对象放入HashSet、LinkedHashSet等底层有哈希表的集合中，必须要进行对hashCode()和equals方法进行重写，String类已经重写过这两个方法了，自定义的Student类却还没有进行方法的重写，所以在将String类型的数据放入后进行遍历，结果都是唯一的，Student的却有重复的。

5.哈希冲突（碰撞）

5.1 装填因子

概述： 装填因子就是哈希表的长度和表中的记录数的比例

如果哈希表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果哈希表的空间小了，又会导致哈系冲突的增大。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定哈希表的大小，还有一种情况是可能事先不知道最终存储的记录个数，则需要动态维护哈希表的容量，此时就得更新哈希地址，浪费时间。

装填因子=表中记录数/哈希表长度

由上面的公式可以得出结论：装填因子越小，表明表中还有很多的空单元，发生冲突的可能性越小；反之，发生冲突的可能性就越大，在查找的过程中就越费时间。相关文件表明，在装填因子等于0.5左右时，哈希表的性能最优。因此，一般情况下，装填因子的大小为0.5.

5.2 哈希函数

哈希函数是在计算存储位置的时候使用的。

分类：

1. 直接定址法 -> 直接定址法就是以数据元素关键字k本身或它的线性函数作为它的哈希地址
2. 平方取中法 -> 先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。
3. 折叠法 -> 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）
4. 除留取余法 -> 取关键字被某个不大于散列表 表长m的数p除后所得的余数为散列地址（例：y=x%8 y是计算后的存储位置，x是哈希码值，8是数组的长度，除数只要不大于数组的长度即可）

5.3 处理冲突的方法

1. 链地址法 -> 在哈希表每一个单元中设置链表，某个数据项对的关键字还是像通常一样映射到哈希表的单元中，而数据项本身插入到单元的链表中。简而言之，就是出现冲突，在后面进行“拉链”
2. 开放地址法 -> 当冲突发生的时候,通过查找数组的一个空位,并将数值填充进去,而不再是使用哈希函数得到的数组下标,就叫做开放地址法
3. 再散列法 -> 第一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法。
4. 建立一个公共溢出区 -> 就是将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

因此，减少哈希冲突可以从以上三个方面进行考虑。

这篇好文章是转载于：学新通技术网