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

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

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

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

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

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

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

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

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

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

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

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

1号箱子也不是Ally

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

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

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

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

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

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

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

我们尝试把Joe存进去

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

补充说明:

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

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

推荐文章:

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