哈希表

哈希表就是一种以 键-值(key-indexed) 存储数据的结构
插入和删除接近常量时间级O(1)
将键映射成索引，这种映射函数就是哈希函数

避免哈希冲突

拉链法 (Separate chaining with linked lists)
直接的办法就是，将大小为M 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法

Paste_Image.png

线性探测法
基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突

Paste_Image.png

散表函数
（1）若函数为h(k)=k，就是直接寻址表

（2）除法散列法：h(k) = k mod m
（3）乘法散列法：h(k) = m * (k * A mod 1) (0<A<1)
（4）全域散列：从一组仔细设计的散列函数中随机地选择一个。（即使对同一个输入，每次也都不一样，平均性态较好）
3.冲突解决策略
（1）链接法
（2）开放寻址法
a.线性探测：h(k, i) = (h'(k) + i) mod m
b.二次探测：h(k, i) = (h'(k) + c1*i + c2 *i^2) mod m
c.双重散列：h(k, i) = (h1(k) + i * h2(k)) mod m
（3）完全散列：设计一个较小的二次散列表

int h(int k)  
{  
    return k % m;  
}  
int h2(int k)  
{  
    return 1 + k % (m-1);  
}  
//线性探测  
int Linear_Probing(int k, int i)  
{  
    return (h(k) + i) % m;  
}  
//二次探测  
int Quadratic_Probint(int k, int i)  
{  
    int c1 = 1, c2 = 3;  
    return (h(k) + c1 * i + c2 * i * i) % m;  
}  

链接
http://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html