数据结构-哈希表（C语言）
哈希表的概念
哈希表就是：
“将记录的存储位置与它的关键字之间建立一个对应关系，使每个关键字和一个唯一的存储位置对
应。”
哈希表又称：“散列法”、“杂凑法”、“关键字：地址法”。
哈希表思想
基本思想是在关键字和存储位置之间建立一个哈希函数hash，使每一个存储位置和关键字对应。
通常关键字的集合很大，因此经过哈希函数的变换后，可能会将不同的关键字映射到同一个地址
上。这种现象称作：“冲突”，具有相同函数值的关键字称作：“同义词”。
哈希表属性
哈希函数的值域是可以使用的地址空间，称作基本区域。
基本区域的长度是哈希表的长度。
同义词可以存放在基本区域中未占用的单元，也可以放在另外开辟的地方。（溢出区）
哈希函数的构造
哈希函数的构造一般有下面几种方法：
1.直接定址法
hash(key) = key或hash(key) = a * key + b
直接定址法的构造有点像Python里面的字典。
优点:不会产生冲突
缺点:空间效率不高
2.取余法
hash(key) = key % p
p < m，m是哈希表长。
优点：计算简单，适用范围大
缺点：需要选择一个合适的p，p的选择很困难
一般来说，p是不大于m的最大素数：
3.平方取中法
先计算关键字的平方，然后取平方后数的中间几位作为地址。
key = 2587
key ** 2 = 6692569
若取三位，则hash(2587) = 925。