C++数据结构哈希表详解

实现

散列函数

开散列方法

闭散列方法(开地址方法)

删除*

实现

哈希表，即散列表，可以快速地存储和查询记录。理想哈希表的存储和查询时间都是 O(1)。

本《资料》中哈希表分以下几部分：散列函数、存储和查找时的元素定位、存储、查找。删除操作因为不常用，所以只给出思想，不给出代码。

根据实际情况，可选择不同的散列方法。

以下代码假设哈希表不会溢出。

// N表示哈希表长度，是一个素数，M表示额外空间的大小，empty代表“没有元素”。
const int N=9997, M=10000, empty=-1;
int a[N];
void init() // 初始化哈希表
{
memset(a,empty,sizeof(a)); // 注意，只有empty等于0或-1时才可以这样做！
memset(bucket,empty,sizeof(bucket));
memset(first,0,sizeof(first));
}
inline int h(int); // 散列函数
int *locate(int, bool); // 用于存储和查找的定位函数，并返回对应位置。
// 如果用于存储，则第二个参数为true，否则为false①。
void save(int x) // 存储数据
{
int *p = locate(x, true);
if (p!=NULL) *p=x;
}
bool isexist(int x) // 查找数据
{
int *p = locate(x,false);
return (p!=NULL && *p==x);
}

散列函数

为了达到快速存储和查找的目的，就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 h。

这个关系 h 叫做哈希函数。

哈希表存取方便但存储时容易冲突：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。以下是几种常见的哈希函数的构造方法：

1. 取余数法：h(x) ＝ x％p（p≤N，且最好是素数）

2. 直接定址法：h(x)＝x 或 h(x)＝a*x＋b

3. 数字分析法：取关键字的若干数位（如中间两位数）组成哈希地址。

4. 平方取中法：关键字平方后取中间几位数组成哈希地址。

5. 折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。

6. 伪随机数法：事先产生一个随机数序列 r[]，然后令 h(x)＝r[x]。

设计哈希函数时，要注意

对关键码值的分布并不了解——希望选择的散列函数在关键码范围内能够产生一个大致平均的关键码值随机分布，同时避免明显的聚集可能性，如对关键码值的高位或低位敏感的散列函数。

对关键码值的分布有所了解——应该使用一个依赖于分布的散列函数，避免把一组相关的关键码值映射到散列表的同一个槽中。

开散列方法

哈希表中难免会发生冲突。使用开散列方法可以解决这个问题。常用操作方法是“拉链法”，即相同的地址的关键字值均链入对应的链表中。

如果散列函数很差，就容易形成长长的链表，从而影响查找的效率。

下面是用“拉链法”处理冲突时的定位函数：

int size=-1;
struct node {int v; node * next;} *first[N], mem[M];
#define NEW(p) p=&mem[++size]; p->next=NULL
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) return &a[p];
// 处理冲突
node *q = first[p];
if (ins)
if (q==NULL)
{
NEW(q);
first[p]=q;
return &q->v;
}
else
{
while (q->next!=NULL) q=q->next;
node *r; NEW(r);
q->next=r;
return &r->v;
}
else
while (q!=NULL)
{
if (q->v == x) return &q->v;
q=q->next;
}
return NULL;
}

闭散列方法(开地址方法)

处理冲突的另一种方法是为该关键字的记录找到另一个“空”的哈希地址。在处理中可能得到一个地址序列 g(i)（i＝1，2，…，k；0≤g(i)≤n－1)，即在处理冲突时若得到的另一个哈希地址 g(1)仍发生冲突，再

求下一地址 g(2)，若仍冲突，再求 g(3)……怎样得到 g(i)呢？

溢出桶法：设一个溢出桶，不管得到的哈希地址如何，一旦发生冲突，都填入溢出桶。

再哈希法：使用另外一种哈希函数来定位。

线性探查：g(i)＝(h(x)＋di) % N，其中 h(x)为哈希函数，N 为哈希表长，di 为增量序列。

1. 线性探测再散列：di＝1，2，3，…，m－1

2. 二次探测再散列：

3. 伪随机探测序列：事先产生一个随机数序列 random[]，令 di＝random[i]。

下面是用溢出桶处理冲突时的定位函数：

int bucket[M], top=-1; // 用于闭散列方法（溢出桶）
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) // 在查找模式下碰到了所需的元素
return &a[p];
else if (ins)
{
if (a[p]==empty) // 可以插入
return &a[p];
else // 处理冲突
return &bucket[++top];
}
else // 到溢出桶中寻找元素
for (int i=0; i<=top; i++)
if (bucket[i]==x) return &bucket[i];
return NULL;
}

下面是用线性探查处理冲突的定位函数，当然，它也可以用于再哈希法处理冲突

inline int g(int p, int i) {return (p+i)%N;} // 根据需要来设计
int * locate(int x, bool ins=false)
{
int p=h(x);
int p2, c=0;
if (a[p]==x && !ins)
return &a[p];
else if (ins)
{
do
{
p2 = g(p, c++);
} while (a[p2]!=empty);
return &a[p2];
} else {
do
{
p2 = g(p, c++);
} while (a[p2]!=x && a[p2]!=empty);
if (a[p2]==x) return &a[p2];
}
return NULL;
}

闭散列方法的优点是节省空间。不过，无论是溢出桶，还是线性探查，都会在寻址过程中浪费时间。线性

探查的探查序列如果太长，就会使一些其他元素被迫散列在其他位置，从而影响了其他元素的查找效率。

删除*

如果使用开散列方法，那么可以直接删除元素。然而，使用闭散列方法，是不可以直接删除元素的。假如

直接删除，很有可能会影响其他元素的查找。

在这种情况下，有两种删除方法：一种是交换法，另一种是标记法。

交换法：在删除某元素时，不要立刻把它清除。按照线性探查函数继续寻找，直到没有数值为止。将遇到

的最后一个数值与它交换。当然，交换之前还要进行类似的操作，可谓“牵一发而动全身”。

标记法：开一个标记数组 flag[]。如果第 i 个元素被删除了，就将 flag[i]设为 true。

1. 插入元素时，如果所在位置有标记，就把元素放到这里，并把标记清除。

2. 查找元素时，如果经过标记，就跳过去继续查找。

3. 为了哈希表的效率，应该定期清理表中的标记（或重新散列所有元素）。