数据结构一直都是软件工程师必备技能之一，也是难点之一。数据结构其实是数据存储结构，它采用不同的存储方式和逻辑思路，实现各种数据和数据之间的关联，并且加上对应的算法，来解决问题。哈希表(散列表)是数据结构中一种散列存储方式，优点在于关键值key可以通过指定的算法直接得到数据的存储位置hash(key)，这样一来不需要轮询，时间复杂度大大的降低。从而，哈希表满足了对数据操作高效率的要求。但是，哈希表也不是全能的，它的使用有一定的局限性。下面我们来介绍一下哈希表的设计和实现。

哈希表的设计

哈希表主要是确认关键值key和关键值存储位置hash(key)之间的具体关联算法。并且保证少的哈希冲突(多个不同数据通过算法得到存储位置相同，这时就是哈希冲突)产生。常见的哈希表的设置方法如下：

（1）直接定址法：直接的构造哈希表的方法，存储位置是通过线性函数得到的：

hash(key) = a * key + b {a、b为常数}

特点：这样得到的 hash(key) 和 key之间一一对应，一般不会产生冲突;

空间：这的哈希表要求地址空间大小与key集合大小相同;

应用：一般用于有序的key集合，例如各种编号。

（2）数字分析法： 分析已有数据的特点，选择尽量冲突少的数字来构造哈希表。

特点：数据是多位组成，数据和数据之间有相同的也有不同的，根据数据中每位的分布特点，选取若干位作为哈希表地址。

空间：根据选择的位的个数而定;

应用：数据位数多，且都相似， 例如生日，日期等等。

（3）除留余数法：n个数据,选取一个接近于n的质数p，这时哈希地址公式：

hash(key) = key % p 除法后得到的余数就是数据存储位置

特点：余数的取值范围 0 到 p-1 内，这样存储数据空间大小是固定的 p 个;

空间：p个存储空间;

应用： 数据值较大，数据个数较少。

(4)乘余取整法：先让关键值key乘上一个常数A(0 <1),提取乘积的小数部分。然后再用整数n乘以这个值，对结果向下取整，这个结果就是存储位置。<>

公式：hash(key) = (int)((((float)key*A) - (int)(key*A))*n)

应用：数据是小数，并且相差很少。

(5)平方取中法：一般哈希地址位置数据2的某次幂，例如：哈希地址总数为 m = 2^r。哈希地址hash(key) = 2^key 值中间的r位。

(6)折叠法：数据信息很长，可以将数据从左到有分成几个部分，每部分位数应与hash(key)存储位置的位数相同，将每部分都叠加求和，这个和就是hash(key)存储位置。

应用：例如：图书馆中图书的标准编号。

(7)随机数法：获取一个随机数，作为存储位置，公式：hash(key) = random(key);

应用：key关键字长度不等时使用。

哈希表的实现

这里我们以第三种方式除留余数法举例。

例子：已知存在以下数据 ： 23 , 26 ， 29 ，30，34 ，40

利用哈希表存储上面数据，并写出查找方法。

第一步：确认hash(key)和key之间的关联公式

数据有6个，先选取一个质数p = 7 或 11或 13

为尽量减少哈希冲突，当选择p=7时：余数2 5 1 2 6 5有冲突

当选择p=11时：余数1 4 7 8 1 6有冲突

当选择p=13时：余数10 0 3 4 8 1无冲突

所以公式：hash(key) = key % 13;

实现代码：
#include<stdio.h>
typedef int data_t;
#define M 13
int emptyHash(data_t *p)  // 判断哈希地址中是否空闲
{
         return *p == 0 ? 1:0;
}
int setHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(emptyHash(&hp[i]))      // 判读指定位置是否空闲
                   hp[i] = key;                  // 存储到哈希表中
         else 
return 0;       // 失败
         return 1;           // 成功
}
int getHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(hp[i] != key)    
         {
                   printf("数据没有存储到哈希表中\n");
                   return 0;
         }
         else
                   printf("数据在哈希表中,位置%d --> %d\n",i, hp[i]);
         return 1;
}
int main()
{
         data_t hash[13] = {0};          // 定义一个哈希表（数组）存储数据空间
         setHash(hash,23);
         setHash(hash,26);
         setHash(hash,29);           // 哈希表中存入数据
         setHash(hash,30);
         setHash(hash,34);
         setHash(hash,40);
         getHash(hash,34);           // 查找哈希表
         getHash(hash,32);                    
         return 0;
}