一、基本概念
散列技术：在记录的存储位置和它的关键字之间建立一个确定的相应关系f。使得每一个关键字key相应一个存储位置f(key)。
f：散列函数/哈希函数；
採用散列技术将记录存储在一块连续的存储空间中。这块连续存储空间称为散列表或哈希表。 关键字相应的记录存储位置称为散列地址。散列技术既是一种存储方法，也是一种查找方法。
散列技术适合求解问题是查找与给定值相等的记录。查找速度快。 散列技术不适合范围查找，不适合查找相同关键字的记录，不适合获取记录的排序，最值。冲突：关键字key1不等于key2。但f(key1)=f(key2)。
把key1和key2称为散列函数的同义词。
二、散列函数构造
两个原则：
- 计算简单
- 散列地址分布均匀
1. 直接定址发
f(key)=a x key+b(a、b为常数)
简单。均匀，不会冲突，可是事先知道关键字的分布情况，适合查找表小且连续。
2. 数字分析法
关键字位数多，比方手机号，可能前几位一样，仅仅是后几位不同，抽取关键字的一部分计算散列存储位置。
事先知道关键字分布且若干位分布均匀。
3. 平方取中法
不知道关键字分布，且位数不是非常大。1234，平方1522756。抽取中间227作为散列地址。
4. 折叠法
不知道关键字分布，位数多。
从左到右切割成位数相等的几部分，这几部分叠加求和，并按散列表表长，取后几位作为散列地址。5. 除留余数法
散列表长m
f(key)=key mod p(p<=m)
p选取不好，产生冲突。
通常p为<=m（最好接近m）的最小质数或者不包括小于20质因子的合数。6. 随机数法
关键字长度不等。
f(key)=random(key),random随机函数
当关键字为字符串，转化为某种数字来对待。比方ASCLL码或者Unicode码等。
三、散列冲突处理
1. 开放定址法
又叫线性探測法：一旦冲突，寻找下一个空的散列地址。
散列表大。
优化：二次探測法
双向寻找，防止后面没空。但前面有空。 添加平方，不让关键字聚集在某一块区域。 还有对位移量d随机函数计算。称之为随机探測法。
2. 再散列函数法
3. 链地址法
将全部关键字为同义词的记录存储在一个单链表（同义词字表）中。
散列表中仅仅存储全部同义词字表的头指针。 {12,67,56,16,25,37,22,29,15,47,48,34} mod 12
缺点：单链表查找遍历耗时。
4. 公共溢出区法
冲突关键字存储到溢出表中
散列计算后，先基本表比較。不等，到溢出表进行顺序查找。 四、散列表查找
1. 附加源代码
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */#define SUCCESS 1#define UNSUCCESS 0#define HASHSIZE 12 /* 定义散列表长为数组的长度 */#define NULLKEY -32768 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 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 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;}int main(){ int arr[HASHSIZE]={ 12,67,56,16,25,37,22,29,15,47,48,34}; int i,p,key,result; HashTable H; key=39; InitHashTable(&H); for(i=0;i \n"
,key); for(i=0;i<m;i++) { key=arr[i]; SearchHash(H,key,&p); printf("查找 %d 的地址为：%d \n",key,p); } return 0; } 2. 查找性能
假设无冲突。O(1)。
查找平均长度取决于：
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的装填因子 装填因子=填入表中的记录个数/散列表长度。（表示散列表的装满的程度） 当填入表中的记录越多，装填因子越大。产生冲突可能性越大。
通常将散列表的空间设置的比查找集合大，牺牲空间换时间。