一般的表，如果需要查找某个关键字的记录，就得从表头开始，挨个地比较记录a[i]和key的值是否相等，如果相等就算成功找到了，返回i；假如是有序表来查找，可以通过a[i]和key来二分查找，直到找到相应的i；最终为了找到那个i，其实也就是相对的下标，再通过顺序存储的存储位置来计算，也就是第一个元素内存存储位置加上i-1个单元位置LOC(ai)=LOC(a1)+(i-1)*c，得到最后内存地址
由此可以，比较的成分十分多，是否能够避免呢，也就是，是否能通过某个函数f，使得
存储位置 = f（关键字）
这样就只通过查找关键字不需要比较就可以获得需要的记录的存储位置，也就是哈希表
哈希表在记录的存储位置和它的关键字之间建立了一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）；查找时，根据这个确定的对应关系找到给定值key的映射f（key），若集合中存在这个记录，必定在f（key）的位置上
这里对应关系f为哈希函数，按哈希将记录存储在一块连续的存储空间中，这块连续存储空间称为哈希表，关键字对应的记录存储位置为哈希地址
哈希表的查找
1：在存储时，通过哈希函数计算出记录的哈希地址，并按照此哈希地址存储该记录
2：当查找记录时，通过同样的哈希函数计算记录的哈希地址，按此哈希地址访问该记录
看上去很简单，在哪里存的就上哪里去找，由于用的同一个哈希函数，所以结果也是相同的；因此哈希既是一种存储方法，也是一种查找方法；但是它和线性表，树不同的是哈希的记录之间不存在什么逻辑关系，只与关键字相关，因此是面向查找的存储结构
哈希最适合查找和给定值相等的记录；对于查找，简化了比较过程，提高了效率，但是哈希补适合同样的关键字能对应很多记录的情况
哈希表的创建
这里主要写两个，取模和随机数
取模是最常见的构造哈希函数的方法，对于哈希表长为m的哈希函数公式为
f(key) = key mod p (p <= m)
这里不仅可以对关键字直接取模，还可以在折叠，平方取中后再取模；很显然这个方法关键在于选择合适的p，如果p选择的不好，会产生同义词，也就是不同的关键字映射了相同的f(key)
下表中，对于12个记录的关键字构造哈希表，用的方法为f(key) = key mod 12
下标 0 1 2 3 4 5 6 7 8 9 10 11 关键字 12 25 38 15 16 29 78 67 56 21 22 47
由于12=2*6=3*4，假如关键字为18（3*6），30（5*6），42（7*6）等数字，他们余数都是6，就会和关键字78对应的下表位置冲突
一般来说，假如哈希表表长为m，通常p为小于或者等于表长（最好是接近m）的最小质数或者补包含小于20质因子的合数
随机数方法，取关键字的随机函数值为它的哈希地址，也就是
f（key） = random（key）
这里的random是随机函数；当关键字的长度不等时，采用这个方法构造哈希函数是比较合适的
关键字无论是英文字符，中文字符还是字符串，各种各样的符号，都可以转换成某种数字来对待，比如ASCII码或者Unicode码，都可以用上面的方法
哈希表查找的实现，首先是需要定义一个哈希表的结构以及一些相关的常数，下面是一些伪代码，HashTable是哈希表结构，elem是动态数组
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct {
int *elem; //数据元素存储基址，动态分配数组
int count; //当前数据元素个数
}HashTable;
int m = 0; //哈希表表长
//初始化
Status InitHashTable(HashTable *H){
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m * sizeof(int));
for (i = 0; i < m; i++)
H->elem[i] = NULLKEY;
return OK;
}
//为了插入时计算地址，定义哈希函数，可以根据不同情况改变算法
int Hash(int key){
return key % m;
}
//插入
void InsertHash(HashTable *H, int key){
int addr = Hash(key); //哈希地址
while (H->elem[addr] != NULLKEY) //如果不为空，则冲突
addr = (addr + 1) % m;
H->elem[addr] = key; //直到有空位后插入关键字
}
//查找
Status SearchHash(HashTable H, int key, int *addr){
*addr = Hash(key);
while(H.elem[*addr] != key){
*addr = (*addr + 1) % m;
if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
return UNSUCCESS;
}
return SUCCESS;
}
