什么是哈希表
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。哈希表作为一种高效的数据结构，有着广泛的应用。如果哈希函数设计合理，理想情况下每次查询的时间花费仅仅为 O(h/r)，即和哈希表容量与剩余容量的比值成正比。只要哈希表容量达到实际使用量的大约 1.5 倍以上，查询花费的时间基本就可以认为恒为 O(1)。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”F()是这个例子中的哈希函数，存放首字母的表对应哈希表。关键字和哈希函数可以任意选择。在竞赛中的哈希函数一般是直接把关键字对一个素数取模（简单粗暴）。
与平衡二叉树的类比
Map是STL的一个关联容器，它提供一对一的数据处理能力（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）。它的内部实现是一个红黑树（红黑树是平衡二叉树的一种），平衡二叉树中的部所有的数据都是有序的，并且可以通过O(logn)的复杂度查找、插入或删除一个关键字。而在理想情况下，哈希表可以用O(1)的复杂度查找、插入一个关键字。
处理碰撞
处理碰撞的方法有很多，在竞赛中一般采用单独链表法：将哈希到同一个存储位置的所有元素保存在一个链表中。在实现中一般用一个数组来代替链表。
算法实现
我们通过山寨一个STL Map来加深对哈希表的理解。
map常用操作有两种：
typedef long long LL;
typedef LL KT;// Key的类型
typedef LL VT;// Value的类型
class Hash_Map {
private:
static const int SEED = 299;// 一个比实际容量稍大的素数
static const int MAXN = 30000;// 哈希表最大的元素个数
struct ELEM {// 定义链表的数据类型
KT key;// 元素的关键字
VT value;// 元素的值
int next;// 指向链表的下一个位置
}elems[MAXN];// 链表所使用的数组
int head[SEED], cur;// 表头与元素个数
int hash(KT key){// 哈希函数
return key % SEED;
}
public:
Hash_Map() {// 构造函数
clear();
}
void clear() {// 初始化哈希表
cur = 0;
memset(head,-1,sizeof(head));
}
void insert(KT key, VT value) {// 插入一个关键字
int h = hash(key);// 用哈希函数计算关键字在哈希表中的地址
for (int i=head[h]; i!=-1; i=elems[i].next) {// 遍历哈希值为h的链表中的所有元素
if (key==elems[i].key) {// 如果key已经存在
elems[i].value = value;// 覆盖旧的value
return;
}
}
// key不存在，则将其插入链表
elems[cur].value = value;
elems[cur].key = key;
elems[cur].next = head[h];
head[h] = cur++;
}
VT find(KT key) {
int h = hash(key);
for (int i=head[h]; i!=-1; i=elems[i].next) {
if (key==elems[i].key) {
return elems[i].value;
}
}
return 0;
}
VT& operator[](KT key){
int h = hash(key);// 用哈希函数计算关键字在哈希表中的地址
for (int i=head[h]; i!=-1; i=elems[i].next) {// 遍历哈希值为h的链表中的所有元素
if (key==elems[i].key) {// 如果key已经存在
return elems[i].value;
}
}
// key不存在，则将其插入链表
elems[cur].value = 0;
elems[cur].key = key;
elems[cur].next = head[h];
head[h] = cur++;
return elems[cur-1].value;
}
}hs;
