什么数据库使用哈希表来存储数据 数据结构哈希表概念

哈希表：即散列存储结构。

散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。

这样，不经过比较，一次存取就能得到所查元素的查找方法

优点：查找速度极快（O(1)）,查找效率与元素个数n无关

哈希表存储的是由键(key)和值(value)组成的数据。例如，我们将每个人的性别作为数据进行存储，键为人名，值为对应的性别。

为了和哈希表进行对比，我们先将这些数据存储在数组中

此处准备了6个箱子即长度为6的数组来存储数据，假设我们需要查询Ally的性别，由于不知道Ally的数据存储在哪个箱子里面，所以只能从头开始查询，这种操作叫作线性查找。

0号箱子中存储的键是Joe而不是Ally

1号箱子也不是Ally

同样2，3号箱子中也都不是Ally

查找到4号箱子的时候，发现其中数据的键为Ally，把键对应的值取出，我们就知道Ally的性别为女（F）了，当数据量越多，线性查找耗费的时间就越长，由此可见，由数据的查询较为耗时，所以此处并不合适试用数据来存储数据。

为了解决这个问题，我们使用哈希表可以解决这个问题，首先准备好数据，这次我们用5个箱子的数据来存储数据.

我们尝试把Joe存进去

使用哈希函数(Hash)计算Joed的键，也就是字符串“Joe“的哈希值。得到的结果为4928

将得到的哈希值除以数组的长度5，求的其余数，这样的求余运算叫作”mod“运算。此处mod运算的结果为3

因此，我们将Joe的数据存进数组的3号箱子中，重复前面的操作，将其它的数据也存进数组中。

Sue键的哈希值为7291,mod 5的结果为1，将Sue的数据存进1号箱中

Dne键的哈希值为1539,mod 5的结果为4，将Dne的数据存进4号箱中

Nell键的哈希值为6276,mod 5的结果为1，本应将其存进数组的1号箱中，但是此时1号箱中已经存储了Sue的数据。这种存储位置重复了的情况便叫“冲突”。

遇到这种情况，可以使用链表在已有数据后面继续存储新的数据。

Ally键的哈希值为9143,mod 5的结果为3.本应将其存储在数组的3号箱中，已经有了Joe的数据，所以使用链表，在其后面存储Ally的数据。

Bob键的哈希值为5278，mod 5的结果为3.本应将其存储数组3号箱，但3号箱中已经有了Joe和Ally的数据，所以使用链表，存在Ally的后面继续存储Bob的数据。

像这样存储所有数据，哈希表也就制作完成了。

接下来，我们来讲解数据查询方法。假设我们要查询Dan的性别。

为了知道Dan存储在哪个箱子里，首先需要算出Dan的哈希值，然后对其进行mod运算。最后得到的结果为4，于是我们知道了它存储在4号箱中。

查看4号箱可以知道，其中的数据的键与Dan一致，于是取出对应的值。由此我们知道了Dan的性别为男（M）

那么，想要查询Ally的性别时该怎么做呢？为了找到它的位置，先要算出Ally键的哈希值，再对其进行mod运算，最终得到结果为3。然而3号箱中的数据键是Joe而不是Ally。此时需要对Joe所在的链表中进行线性查找。

于是我们找到了键为Ally的数据，取出其对应的值，便知道了Ally性别为女(F)。

在哈希表中，我们可以利用哈希函数快速访问到数组的目标。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据为多少，我们都能够灵活应对。如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也就会更高。反过来，如果数组的空间太大就会出现很多空的箱子，造成内存的浪费，因此，给数组设定合适的空间非常的重要。

补充说明：

在存储数据的过程中，如果发生冲突，可以利用链表在已有的数据后面插入新的数据来解决冲突，这种方法称为“链地址法”。

除了链地址法以为，还有几种解决冲突的方法，其中，应用比较广泛的是“开发地址法”。这种方法是指冲突发生时，立刻计算出一个后补地址（在数组上的位置）并将数据存进去。如果还有冲突，进行计算下一个后补地址，知道有空地址为止。可以通过多次哈希函数或者线性探测法等方法计算后补地址。

推荐文章：

数据结构：链表《概念》数据结构：链表《单链表》数据结构：链表《双链表》数据结构：哈希表《概念》数据结构：哈希表,