[数据结构] 散列表（哈希表）

散列表（哈希表）

比较难理解的官方定义：散列表/哈希表（Hash table），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

举个例子，我们在查找中文字典时。假设我们要查找“翁weng”，我们根据weng找到了对应的页码233，这个过程就是根据关键码值映射得到了表中的位置。然后我们在字典这个散列表中，根据我们刚才得到的位置 233页，直接访问了“翁weng”。

再举一个更详细一些的例子。我们现在的班级有二十三名学生。我们创建一个26*4长度的大数组scores[104]，来存放每个学生的数学成绩。我们创建一个散列函数 关键码值=学生的姓名每个字首字母在字母表的序号的和。林小白，L+X+B = 12 +20 +2 = 34。林小白数学考了99分，scores[34] = 99。这是成绩的记录过程。查询的时候，散列函数 f(林小白)= 12 + 20 + 2 = 34 ,那么他的分数就是scores[34]。

当然你马上会发现问题。

问题①大数组用这个映射函数，而且只有二十三个学生，数组很多位置都没用到；

我们需要找到好的映射方法，或者增加一些步骤来解决上面的问题。

首先可以考虑原始数据的优化，比如编号10001，10002......10200，很显然直接取三位尾数来使用是个很好的方法。

然后我们需要使用一些比较好的映射函数，使得到的关键码值能够分布均匀。

问题②林小白和李小贝的成绩会被放在同一个位置，这叫做哈希冲突。

但是，这些优化仍然不能解决哈希冲突的发生。我们需要一些额外的步骤和方法。

哈希冲突的解决

比如链地址法，我们仍然有一个数组，但是数组中的元素是一个指向链表头部的指针。每一个链表中存放的就是所有使用映射函数之后，得到同一个关键码值的数据。

图-链地址法

未完。