看动画，5分钟学会最经典的数据结构哈希表，C语言手写实现，不要错过呀

哈希表Hash table也称为散列表

它可以根据关键字的值直接进行查询与访问的数据结构。

我们通常通过映射函数将关键字直接对应到表中的某个位置，从而加快查找速度。

这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

数组A中有N个整数从中查找整数key,确定key是否在其中，

用最朴素的方法是通过循环将key和每个整数按顺序对比，如果相等返回1循环结束后返回0（但是这种方法的效率很低。

比如要查找1-10是否在A当中，则要调用find-key需要对扫描10次。每次都要比较n次。所以要查询的时间发杂度是大on，如果查询次数为n，那么整体的复杂度就是大on的平方。

如果通过哈希表我们可以将整体的效率优化到线性的大on。

哈希表的特例情况

加入数据的范围是0-99并且类型是整型，这种情况可以直接使用数组下标来记录元素是否出现。这个就是最简单的哈希思想。

具体来看

先设置一个长度是100的数组table.初始化所有的元素为0

然后调用create_hash创建哈希表。在函数中使用i遍历数组a中的全部n个元素，通过table 【i】加加，用table的下标记记录a[i出现的次数。

例如i等于0时，a[0]等于table [7加加

a[1]等于17table [17]

a[2]等于15table [5]加加

完成了遍历之后table就记录了a中的全部元素个数。从0到MAX_TABLE_LEN遍历table，如果说table [i]大于0打印i值出i现的次数table [i],这样我们就得到了a中全部元素出现的个数。

在查找哈希表中是否存在key值时，如果table[key]bushi 0fanhui 否则返回0，测试1到10调用find_key得到查找结果2 3 5 7 8 9对应的tabl值都不为0，所以这些数字都在数组a中出现了。

通过上面这种方法不仅可以用来查找，还可以用来排序。我们一起来想象一下，如果数组a中有n个元素。

非常大，不如达到100W，但a中数据的取值范围非常小，比如从0到99，那么通过0到99长度的table。

由于table[i]代表了数据I出现的次数。在排序时从0到MAX_TABLE_LEN循环i。再将table[i]个i添加到a中就可以了。

eg:使用table将a的每个元素个数统计后，从0到99遍历出现了2次2个2被添加a，然后是3.........，这样就完成了a的排序

当n远大于表长时，这种方法的复杂度就大On,优于一般的排序算啊n倍的logn

如果数组a中的数据范围不是0到99，而是int型的2的31次方。或者是浮点数，字符串，甚至是数组、对象......

如何处理？

要使用哈希函数，我们将待存储的数据转换为表长范围内额整数。然后再使用数组小标进行访问。对于整数数据可以直接取余表长。对应的哈希值。如果是字符串，需要专门的设计哈希函数。最简单的比如遍历字符串中的字符。将它们中的ASC2码相加得到整数。再取余表长得到哈希值。

e如果要将523插入到长度为100的table中。令523取余100得23在将table【23】加1.table的下表23就记录了这个523的数字。字符串ab的ASC2码分别是97 98 99，将它们相加得294取余100是94，那么table [94]就记录了ab是否出现。

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

eg:按照上面的方法，523和23会映射到table[23] ,abc和cba会映射到table[94]打印哈希表发现table [23]和table{94]等于2.

并且123 223 323 acb cab bc等等。都会发生同样的冲突问题。

当冲突发生时就导致查询时出现错误。

eg，如果数组a中包括3table[5]映射为1，当查询103时，也会返回1.

但其实a中并不包括103.

如何解决哈希表的冲突问题呢？

很多经典的方法。

eg线性探测，拉链法。