哈希表—什么是哈希表

冰冻非一日之寒

哈希表是一种数据结构～

基本概念

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。(关键字就是所要存储的数据，存储位置相当于数组的索引)

当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到

eg1. 将26个小写字母存储到数组  int [26] a。

a对应a[0]，b对应a[1]，c对应a[3]……以此类推。

哈希表—什么是哈希表

那么，数组 int [26] a 就是一个哈希表！

哈希函数

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？

关键字的ASCII值减去a的ASCII值！

哈希表—什么是哈希表

上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。

哈希冲突

假如，我们所要存储的数据其关键字是一个人的身份证号(18位数字)，这个时候我们该怎么计算关键字对应的索引呢？

比如一个人的身份证号是 411697199702076425，我们很难像例1那样直接让关键字与数字建立一一对应的关系，并且保证数字适合作为数组的索引。

在这种情况下，通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是哈希冲突

当索引相同时，我们该怎么存储数据呢？如何解决哈希冲突，是我们建哈希表的另一个关键问题。

空间换时间

哈希表充分体现了空间换时间这种经典的算法思想。

关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425

假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作

假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作

事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间

无限空间时，时间为O(1)

1的空间时，时间为O(n)

而哈希表就是在二者之间产生一个平衡，即空间和时间的平衡。

哈希表中的关键问题

1.哈希函数的设计

2.解决哈希冲突

3.哈希表实现时间和空间的平衡

后续会详细说明这三个关键问题～