散列表

散列表的基本概念

假设某应用要用到一个动态集合，其中每个元素都有一个属于[0..p]的关键字，此处p是一个不太大的数，且没有两个元素具有相同的关键字，则可以用一个数组[p+1]存储该动态集合，并且使用关键字作为数组下标进行直接寻址。这一直接寻址思想在前面的非比较排序中就有所应用。然而，当p很大并且实际要存储的动态集合大小n<<p时，这样一个数组将浪费大部分空间。

散列表(Hash table)，使用具有m个槽位的数组来存储大小为n的动态集合。α=n/m被定义为散列表的装载因子。在散列表中，具有关键字k的元素的下标为h(k)，即利用散列函数h，根据关键字k计算出槽的位置。散列函数h将关键字域[0..p]映射到散列表[0..m-1]的槽位上，这里，m可以远小于p，从而缩小了需要处理的下标范围，并相应地降低了空间开销。散列表带来的问题是：两个关键字可能映射到同一个槽上，这种情形称为碰撞。因此，散列函数h应当将每个关键字等可能地散列到m个槽位的任何一个中去，并与其它关键字已被散列到哪一个槽位中无关，从而避免或者至少最小化碰撞。

---

散列函数

多数散列函数都假定关键字域为自然数集。如果所给关键字不是自然数，则必须有一种方法将它们解释为自然数。这里，介绍几种主要的散列函数：

（1）平方取中法
　具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
　【例】将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)
　若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。
相应的散列函数用C实现很简单：
int Hash(int key){ //假设key是4位整数
key*=key； key/=100； //先求平方值，后去掉末尾的两位数
return key％1000； //取中间三位数作为散列地址返回
}

（2）除余法
　该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m
　该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
　【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
　【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。

（3）相乘取整法
　该方法包括两个步骤：首先用关键字key乘上某个常数A(0<A<1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：

　该方法最大的优点是选取m不再像除余法那样关键。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取

　该函数的C代码为：
int Hash(int key){
double d=key *A； //不妨设A和m已有定义
return (int)(m*(d-(int)d))；//(int)表示强制转换后面的表达式为整数
}

（4）随机数法
　选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)，其中random为伪随机函数，但要保证函数值是在0到m-1之间。

---

解决碰撞的方法

解决碰撞的方法主要有两种：链接法和开放寻址法。

l链接法(chaining)：把散列到同一槽中的所有元素都存放在一个链表中。每个槽中有一个指针，指向由所有散列到该槽的元素构成的链表的头。如果不存在这样的元素，则指针为空。如果链接法使用的是双向链表，那么删除操作的最坏情况运行时间与插入操作相同，都为O(1)，而平均情况下一次成功的查找需要Θ(1+α)时间。

l开放寻址法(open addressing)：所有的元素都存放在散列表中。因此，适用于动态集合大小n不大于散列表大小的情况，即装载因子不超过1。否则，可能发生散列表溢出。在开放寻址中，当要插入一个元素时，可以连续地探查散列表的各项，直到找到一个空槽来放置待插入的关键字。探查的顺序不一定是0, 1, …, m-1，而是要依赖于待插入的关键字k。于是，将探查号作为散列函数的第二个输入参数。为了使所有的槽位都能够被探查到，探查序列<h(k,0), h(k,1), …, h(k,m-1)>必须是<0, 1, …, m-1>的一个排列。有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查，以及双重探查。

l线性探查(linear probing)：使用的散列函数如下

h(k,i) = (h’(k) + i) mod m, i=0, 1, …, m-1

h’为一个普通的散列函数，见前面的介绍。线性探查存在一个称为一次群集的问题，即随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。但是，线性探查的优点在于，对m的取值没有特殊的要求。

l二次探查(quadratic probing)：使用的散列函数如下

h(k,i) = (h’(k) +c₁ i + c₂ i²) mod m, i=0, 1, …, m-1

为了能够充分利用散列表，c₁、c₂和m的值要受到限制。一种好的选择是，m为2的某个幂次(m=2^p)，c₁=c₂=1/2。二次探查，不会顺序地探查每一个槽位，解决了一次群集问题。但是，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的，这一性质导致一种程度较轻的群集现象，称为二次群集。

l双重散列(double hashing)：使用的散列函数如下

h(k,i) = (h₁(k) + i h₂(k)) mod m, i=0, 1, …, m-1

为能查找整个散列表，值h₂(k)要与表的大小m互质。确保这一条件成立的一种方法是取m为2的幂，并设计一个总能产生奇数的h₂。另一种方法是取m为质数，并设计一个总是产生较m小的正整数的h₂。例如，可以取m为质数，h₂(k)=1+(k mod m’)，m’=m-1。

---

完全散列

如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O(1)的话，则称其为完全散列(perfect hashing)。通常利用一种两级的散列方案，每一级上都采用全域散列。为了确保在第二级上不出现碰撞，需要让第二级散列表S_j的大小m_j为散列到槽j中的关键字数n_j的平方。如果利用从某一全域散列函数类中随机选出的散列函数h，来将n个关键字存储到一个大小为m=n的散列表中，并将每个二次散列表的大小置为m_j=n_j² (j=0, 1, …, m-1)，则在一个完全散列方案中，存储所有二次散列表所需的存储总量的期望值小于2n。

---

附：链接法实现的散列表

#include <stdio.h>

#include <stdlib.h>

#include "chain_hash.h"

#define HASH_CONSTANT 0.6180339

typedef struct node

{

int key;

struct node *prev;

struct node *next;

}chain_hash_node;

chain_hash_node *new_chain_hash_table(int hash_table_size)

{

int i;

chain_hash_node *chain_hash_table;

chain_hash_table = malloc(sizeof(chain_hash_node)*hash_table_size);

for(i=0; i<hash_table_size; i++)

{

chain_hash_table[i].key = 0;

chain_hash_table[i].prev = NULL;

chain_hash_table[i].next = NULL;

}

return chain_hash_table;

}

void free_chain_hash_table(chain_hash_node *chain_hash_table, int hash_table_size)

{

int i;

chain_hash_node *node;

for(i=0; i<hash_table_size; i++)

{

while(chain_hash_table[i].next != NULL)

{

node = chain_hash_table[i].next;

chain_hash_delete(chain_hash_table[i].next);

free(node);

node = NULL;

}

}

free(chain_hash_table);

chain_hash_table = NULL;

}

void chain_hash_delete(chain_hash_node *node)

{

node->prev->next = node->next;

if(node->next != NULL)

node->next->prev = node->prev;

}

int chain_hash_func(int hash_table_size, int value)

{

return (hash_table_size * ((value*HASH_CONSTANT)-(int)(value*HASH_CONSTANT)));

}

void chain_hash_insert(chain_hash_node *chain_hash_table,int hash_table_size, int value)

{

int index;

chain_hash_node *node;

index = chain_hash_func(hash_table_size, value);

node = malloc(sizeof(chain_hash_node));

node->key = value;

node->prev = &chain_hash_table[index];

if(chain_hash_table[index].next != NULL)

chain_hash_table[index].next->prev = node;

node->next = chain_hash_table[index].next;

chain_hash_table[index].next = node;

}

chain_hash_node *chain_hash_search(chain_hash_node *chain_hash_table,int hash_table_size, int value)

{

int index;

chain_hash_node *node;

index = chain_hash_func(hash_table_size, value);

node = chain_hash_table[index].next;

while(node != NULL)

{

if(node->key == value)

return node;

node = node->next;

}

return NULL;

}

void chain_hash_print(chain_hash_node *chain_hash_table,int hash_table_size)

{

int i;

chain_hash_node *node;

printf("/nchain_hash_table:");

for(i=0; i<hash_table_size; i++)

{

printf("/nslot %d: ", i);

node = &chain_hash_table[i];

while(node != NULL)

{

printf("%d ", node->key);

node = node->next;

}

}

printf("/n/n");

}