大家好，今天要讲的内容是，哈希表，Hash Table。

先来看一个简单的问题：

已知数组a，其中保存了n个整数。

我们要从数组a中，查找整数key，确定key是否存在数组a中。

最朴素的方法是：

使用循环将key和a中的每个整数，按顺序比较。

如果相等，直接返回1。

循环结束后，返回0。

这种方法虽然简单直接，但是效率很低。

如果数组a中有大量元素，并且需要多次查找时，那么这种方法的效率将无法容忍。

例如，在数组a中保存了7、、5等数字：

如果循环查找1、2、3等等到，这个数字，是否在数组a中，

那么就需要调用次find_key函数，进行查找。

对于每次调用find_key函数，都要比较n次：

因此查询的时间复杂度是大O (n)。

如果查询次数也为n，那么整体的复杂度就是大O(n^2)。

实际上，我们希望设计一种算法，使每次查找的复杂度为常数级，大O(1)。

这样，查找效率与待查找表中的元素数量就是无关的。

那么这种方法，就是今天要介绍的，哈希表，hash table。

1.创建哈希表

先来看一个哈希表的特例情况：

假设待处理数据的范围是0到。

此时可以直接使用一个a[]数组，

用它的下标来记录0到之间的这个元素，

是否出现，出现了多少次。

例如，数字5出现了1次，那么a[5]就等于1。

9出现了3次，a[9]=3。这是最简单的哈希思想。

样例代码如下，在使用哈希表之前，需要先创建哈希表：

在main函数中，设置一个长度是的数组table。

初始化其中的元素为0，作为哈希表的表体。

然后使用函数，create_hash，创建哈希表。

在create_hash函数中：

使用i，遍历数组a中的全部n个元素。

通过table[a[i]]++，利用table数组的下标，记录数字a[i]，出现的次数。

例如：

i=0时，a[0]=7，table[7]++；

i=1时，a[1]=，table[]++；

i=2时，a[2]=5，table[5]++；

这样就记录了7、、5，这三个数字，各出现了一次。

完成哈希表的建立后，遍历table数组，得到每个数据出现的次数：

如果table[i]大于0，那么打印i值出现的次数table[i]。

例如，2出现了2次，3出现了1次，5出现了2次等等。

2.从哈希表中查找元素

从哈希表中查找某个key值是否存在，非常的简单：

直接返回table[key]!=0的结果就可以了。

也就是，如果table[key]不是0，那么返回1，否则返回0。

在main函数中：

我们使用函数find_key，查找1到是否出现在数组a中。

这里给出了，对应的运行结果。

3.哈希函数

如果数组a中的数据范围不是0到：

而是int型，从-2^到2^，

或者a是浮点数、字符串，

甚至是数组、对象等等更复杂的元素，应该怎样处理呢？

这时就需要使用哈希函数：

将数据转换为表长范围内的整数，

将这个整数作为数组下标，访问哈希表。

对于整数型数据，可以直接将它取余表长，得到对应的数组下标。

例如，如果要将插入到长度为的table中：

令取余等于，再将table[]加1。

table的下标，就记录了这个数字。

如果数据是字符串，则需要专门的设计哈希函数：

最简单的比如遍历字符串中的字符，

将它们的ASC2码相加得到整数，再取余表长得到哈希值。

例如，字符串abc中的a、b、c三个字符：

ASC2码分别是，、、，将它们相加得，取余是，

那么table[]，就记录了字符串abc是否出现。

4.哈希冲突

哈希函数可能将不同的数据，映射到同一个数组下标上，这时就发生了冲突。

例如，按照刚才的方法，和会同时映射到table[]。

abc和cba会同时映射到table[]。

当冲突发生时，就会导致查询出现错误：

例如，此时我们查询、、，或者abc、cba、acb等等，

都会返回真，但并不能确定具体是哪个数据真的出现了。

关于哈希表冲突的解决，有很多经典的方法。

例如线性探测法、拉链法等等，都可以解决这一问题。

实际上，解决哈希表的冲突，是哈希表算法设计中，最为重要的部分。

后面会给大家介绍相关的内容。

那么到这里，哈希表，Hash Table就讲完了，感谢大家的观看，我们下节课再会。