哈希表 什么是哈希表

为什么这么关注？

首先

哈希表、关联数组或字典数据结构如何在表中工作？

什么时候用哈希表存储项目比较合适？

哈希表中的“冲突”如何处理？

5分钟内:

假设我们想要存储一个用户列表，这样我们以后就可以通过他们的名字找到他们。

我们可以简单地将用户存储在一个数组中。当我们将来需要找人的时候，可以通过遍历所有的数据来找到目标用户。

当我们只有3个用户时，我们可以用简单的方法轻松找到他们。然而，如果我们有成千上万的用户，这个过程将会非常缓慢。因此，通过使用哈希表，可以更好地完成查询。

正是因为哈希表是作为键值对存储的，所以搜索数据的速度比在数组中循环要快得多。

创建哈希表

要使用哈希表，您需要为每个用户提供一个唯一的值，即key。该索引将用于存储该项目以备将来检索。

假设每个用户都有一个唯一的名称，并将其用作主键。例如，在实际应用中，ID被用作主键。

Hashtable的工作原理是将键值对存储在Buckets中。哈希表由多个桶组成，每个桶存储所有具有相同值的HashKey，如图所示:

举个简单的例子，我们将使用4个桶。

当用户被添加到哈希表中时，我们使用它的索引来确定它存储在哪个桶中。

当需要再次检索用户时，可以直接跳转到正确的桶找到目标，比依次搜索要快。

存储表

第一个用户“Ada”存储在表中。

首先，确定将它存储在哪个桶中。这意味着我们需要在关键字的位置存储一个字符串，如果我们能在将它代入函数后得到表中包含关键字的记录的地址。这样做的过程就是我们的哈希表，函数就是hash函数。

在这个例子中，我们将创建一个简单的散列函数。为用户名分配一个数字，其中包含每个字母；A=0，B=1，C=2等。最后，将所有的值加在一起，结果就是一个哈希值，也就是哈希值，也就是哈希地址所在的位置。

对于“Ada”，数字是3——因此我们可以将Ada存储在存储区3:

将来需要检索“Ada”时，可以对她的名字执行同样的哈希函数。这将告诉我们在桶3中寻找她，而不需要遍历数组。

然后存储下一个用户“Grace”:

“Grace”的哈希值是29，但是我们没有29个桶！

仅使用其哈希值来存储数组将意味着我们将需要大量的Bucket。相反，我们需要一种将哈希值转换为桶号的方法。

一种常见的实现方法是将哈希值除以桶的数量，然后将剩余部分用作桶号。

除以两个数得到的余数叫做模。“Grace”的哈希值是29，我们有4个桶。29除以4后的余数是1，因此“Grace”存储在编号为1的桶中。

这个操作可以写成29% 4 = 1，或者29 mod 4 = 1。

当我们以这种方式计算桶时，哈希表如下:

冲突

一个好的Hash函数不仅具有优越的性能，还能使存储在底层数组中的值分布更加均匀，减少冲突。

其实输入键映射到一个很小的空上，所以碰撞是不可避免的。可以做的是降低哈希冲突的概率。

然后存储“蒂姆:

现在，我们有两个用户要存储在桶3中:

有两种方法可以解决这个问题:

我们可以使用一种算法来连续选择新的桶，直到找到一个空的桶，然后将哈希地址存储在那里。每个存储桶中只有一个底层阵列的方法称为开放寻址。

或者，不是在每个桶中只存储一个散列地址，而是存储一组散列地址。当我们使用这种方法寻找冲突时，我们只需要将冲突的键值对放在同一个桶中。

以后需要取回数组的时候，还是可以直接跳到正确的桶。但是，这一次存储桶可能包含多个数组。在这种情况下，我们将依次检查桶中的每个数组，以找到我们想要的数组。

这称为公共溢出区，通常用于哈希表实现。

这就是为什么一个好的散列函数对性能至关重要的原因之一。

糟糕的散列函数不能均匀地分配项目，所以它们只能集中在几个可用的桶中。

在最坏的情况下，如果所有内容都在同一个桶中，则可以遍历每个项目来查找所需的内容。这就是为什么我们用哈希表来避免麻烦！