HashTable

最近开始刷leetcode，第一题两数之和有两种解法，一个是暴力循环另一个就是哈希表实现。趁着刷leetcode就顺便将c++和数据结构学习一下，本文从c语言入手探究哈希表的底层实现。

HashTable是什么?

首先看一下维基百科对于哈希表的描述：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

在下方表述中会使用hash(哈希)来表达

在刷题数据结构的题目时简单的题目往往会用到链表，但是我们查找链表中的某一项时，需要将所有项进行对比。而哈希表是通过key-value直接访问成员的，表中的每一个成员都有一个对应的key值。这样就可以省略每一项之间的比较，通过key值直接查找到对应的value，从而省去大量的时间。无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

如何实现每一个成员只对应一个key值呢哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。^[1] 哈希表（Hash Table）原理及其实现参考资料