散列Hash

First Post:

Last Update:

注：学习过程参照《数据结构与算法分析——C语言描述》，虽然我个人是用C++实现，但代码大致上与书中一致。如果您发现了某些错误，欢迎指正。

[toc]

一种映射方式。给定一个关键字，将它映射到一张表上对应的单元格。这里展示一种Hash函数：

1
2
3
4
5
6
7
unsigned int Hash(const char* key, int TableSize)
{
unsigned int HashVal = 0;
while (*key != '\0')
HashVal = (HashVal << 5) + *key++;
return HashVal % TableSize;
}

因为常见的关键字都是字符串，所以这样写。但在下面的笔记中，我将关键字规定为整型，以提高笔记的简明性，所以这里将会用另外一种Hash函数：

1
2
3
4
5
unsigned int Hash(int key, int TableSize)
{
unsigned int HashVal = 0;
HashVal = key % TableSize;
}

按照流程，其实本该从建立哈希表开始，但很快就会遇到一些问题，所以我打算和在一起记录。不妨先假设我们已经建好了一张散列表。

问题是非常显而易见的，既然是一种映射函数，那必然会出现碰撞(两个不同的关键字具有相同的散列值)。比如现在所用的这个函数，假设表尺寸TableSize是11，那么关键字“11”“110”就会有同样的散列值了。

因为一个单元格只能储存一个关键字，那么就要对多出来的那一个做些处理了，下面将会详细说明三种方法(总共有四种)。

分离链接：

举一个比较形象的例子吧。

    假设散列表是一个平面，他有X轴和Y轴，两个轴的坐标都必须是整数(整数只是为了好理解一些罢了)。

    比方说（1，1）。现在有两个关键字都被映射到了这个点上，那如何解决？为它增加一个Z轴。

    那么关键字便能够这样储存：（1，1，key1）和（1，1，key2）

    就像是在这个点下面挂上了两个关键字一样。它没有缓解碰撞的出现，但是容许了碰撞的出现。因为即便hash值相同，关键字也同样能够被顺利储存下来。

    在C++中，这种结构是实现方法便是链表。所谓的Z轴就相当于在每一个节点下面挂上一条链表。

    必要的声明：（因为各种声明有些绕，所以加了些许方便理解的注释和一些没必要的名词。）

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Listnode;//表节点
typedef struct Listnode* Position;//指向表节点的“位置指针”
struct HashTbl;//哈希表
typedef struct HashTbl* HashTable;//指向哈希表的“表指针”
typedef Position List;//“位置指针”也将作为“列表指针” 
struct Listnode {
int info;//关键字
Position Next;//指向下一个表节点的“位置指针”
};
struct HashTbl {
int TableSize;//表尺寸
List* TheLists;//指向“位置指针”的“列表指针”
}

建立表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HashTable InitializeTable(int TableSize)
{
HashTable H;
H = new HashTbl;
 //H->TableSize = NextPrime(TableSize);这个函数的作用是取比该值大的下一个素数，但这样简化了一下，所以才有下面的要求
H->TableSize = TableSize;//这要求Tablesize是大于表大小的素数
H->TheLists = new List[TableSize];
 for (int i = 0; i < TableSize; i++)
{
H->TheLists[i] = new Listnode;
H->TheLists[i]->Next = NULL;
}
return H;
}

流程说明：

    该函数将会返回一个“表指针”，这个指针指向我们刚刚建立的哈希表。

    首先，新建一个表指针，并为其开辟一个哈希表空间。现在这个表指针H已经指向了刚开辟的空间。

    将我们输入的“表尺寸”作为这张新表的尺寸，并根据这个尺寸，在表中开辟一个数组，这个数组的元素是“列表指针”。现在，新表中的列表指针TheLists成为了刚开辟好的数组的第一个元素——一个新的列表指针。注意，这个数组的大小会和设定好的“表尺寸一样大”。

    接下来为每一个“表指针”开辟一个新节点，并将节点的Next指针指向NULL。

    现在，TheLists中的每一个列表指针指向新节点。并且，节点中的关键字都还没有初始化。

Find函数：该表将会返回找到的关键字的“位置指针”

1
2
3
4
5
6
7
8
9
Position Find(HashTable H,int Key)
{
Position P;
List L;L = H->TheLists[Hash(Key, H->TableSize)];
P = L->Next;
while (P != NULL && P->info != Key)//strcmp  strcpy
P = P->Next;
return P;
}

流程说明：

    新建一个“位置指针”P和“列表指针”L

    让“列表指针”临时成为关键字本该出现的那一列。（我总觉得这种说辞有些不太简洁。）

    Hash（Key，H->TableSize）其实就是将关键字进行映射，假设结果被映射到了5，那么“列表指针”将临时成为数组中的第六个。

    “位置指针”临时成为L->Next

    之所以是临时，目的是不改变哈希表本来的结构，所以引入临时变量来操作数据。

    接下来开始遍历这一列上的每一个节点，直到找到了相同的关键字或者已经枚举尽了。

    注：因为关键字不一定都是整数，像是字符串之类的关键字，则必须用strcmp和strcpy这样的函数来比较。

插入函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Insert(int Key,HashTable H)
{
Position tmpPos, Newcell;
List L;
 tmpPos = Find(H, Key);
if (tmpPos == NULL)
{
Newcell = new Listnode;
L = H->TheLists[Hash(Key, H->TableSize)];
Newcell->Next = L->Next;
Newcell->info = Key;
L->Next = Newcell;
}
}

流程说明：

    输入关键字和哈希表地址。

    首先，新建一个“临时位置指针”tmpPos和Newcell，以及一个“列表指针”L。

    查找这张表中是否已经存在这个关键字了，如果存在就直接跳过，否则才进行添加。

    假设本不存在这个关键字。

    为Newcell新建一个节点。

    让L指针临时成为指向相应坐标的位置指针。

    那么现在L将指向某个节点，比方说TheLists[5]。

    令Newcell节点中的Next指针成为L指针指向的节点的Next指针。

    关键字赋予。

    将L指向的节点中Next指针指向这个新节点。

    （这个新节点将被挂在最靠近“轴”的那一侧。）

最后是删除函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Deletenode(int Key, HashTable H)
{
Position tmpPos,tmpP2;
List L;tmpPos = Find(H,Key);
L = H->TheLists[Hash(Key, H->TableSize)];
if (tmpPos != NULL&&L->info!=Key)
{
tmpP2 = tmpPos->Next;
while(L->Next!=NULL)
{
if (L->Next->info == Key)
{
L->Next = tmpP2;
delete tmpPos;
}
else
L = L->Next;
}
}
else if (L->info = Key)
{
int K;
L->info = K;
}
}

书上并没有给出删除数据的函数，所以这个函数是我自己现写的，不太确定是否完全正确。

但思路很简单，就是找到关键字那一排，然后把节点删掉，然后再把链表重新拼起来。如果关键字存在头节点，那就只替换掉关键字就行。

（所以最好是不要往头节点放东西，将表制成头节点不包含数据的样式最佳。就连书上也是这样推荐的）

开放定址：

    先贴出完全的代码，再进行逐步分析：(以下代码为平方探测)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;
//----------------------------//
struct HashTbl;
typedef struct HashTbl* HashTable;
struct HashEntry;
typedef unsigned int Index;
typedef Index Position;
typedef struct HashEntry Cell;
enum KindOfEntry {Legitimate,Empty,Deleted};
#define MinTableSize 2
struct HashEntry
{
int Key;
enum KindOfEntry Info;
};
struct HashTbl
{
int TableSize;
Cell* TheCells;
};
Position Find(int key, HashTable H);
void Insert(int key, HashTable H);
HashTable InitializeTable(int TableSize);
Index Hash(const char* key, int TableSize);
//----------------------------//
HashTable InitializeTable(int TableSize)
{
HashTable H;
if (TableSize < MinTableSize)

return NULL;

else
{
H = new HashTbl;
H->TableSize = TableSize;
H->TheCells = new HashEntry[H->TableSize];
for (int i = 0; i < H->TableSize; i++)

H->TheCells[i].Info = Empty;
return H;
}
}

Position Find(int key, HashTable H)
{
Position CurrentPos;
int CollisionNum;
CollisionNum = 0;
CurrentPos = Hash(key, H->TableSize);
while (H->TheCells[CurrentPos].Info != Empty && H->TheCells[CurrentPos].Key != key)
{
CollisionNum++;
CurrentPos += 2 * CollisionNum - 1;
if (CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
}
return CurrentPos;
}

void Insert(int key,HashTable H)
{
Position Pos;
Pos = Find(key, H);
if (H->TheCells[Pos].Info != Legitimate)
{
H->TheCells[Pos].Info = Legitimate;
H->TheCells[Pos].Key = key;
}
}

    继上一篇链接法之后，这次遇到了开放寻址。原理也并不复杂。其实就是当发生了碰撞(不同的关键字却拥有一样的哈希值)时，为后到的关键字再找另外一个地方存放。当然，这个存放也不能是瞎存放，它是有一定规则的，常见的有两种，分别是“线性”和“平方”。

线性探测：

当发生碰撞的时候，就往下一个单元格去存放(如果还碰撞就继续往下，碰到底了就绕回表头继续往下)。是相对朴素的一种方法，只要表还没装满，那就一定能给关键字找到合适的位置。当然，这也同时很不效率，因为它必须一个个去匹配判断，一次次去绕，怎么想都不是很效率，所以还有另外一种“平方”。

平方探测：

    因为上一种不太效率，所以平方探测可能更平常一些。简单来说，当发送了碰撞，就去找当前单元格下的  i^2 格，以此类推（其中，i是一个从1开始的常数，每次判断都会+1。所以偏移量是按照1，4，9，16的顺序来增加的）。

    注：还有另外一种平方探测，和上面的相近，只是变成了  (-1)^i(i)^2 而已，并且 常量i 是每两回合+1（-1，+1，-4，+4像这样）。

    这种方式能很好的防止过多次数的匹配，因为插入数据的单元都很分散，但也同样有些毛病。比方说，必须要保证哈希表足够大。试想一下，这种匹配方式，是不是有可能导致某个数据来回匹配无数次都没办法放进空的单元格里？解决这种方式就需要让哈希表足够大。显然，这可能会浪费不少空间，但速度无疑提升了。

//——————————————-//

首先是创建表函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
HashTable InitializeTable(int TableSize)
{
HashTable H;
if (TableSize < MinTableSize)

return NULL;

else
{
H = new HashTbl;
H->TableSize = TableSize;
H->TheCells = new HashEntry[H->TableSize];
for (int i = 0; i < H->TableSize; i++)
H->TheCells[i].Info = Empty;
return H;
}
}

    并不复杂，连代码都没几行。

    首先，建立一个“表指针H”，然后根据输入的“表尺寸TableSize”建表。

    ①先为H开辟一个“表空间”

    ②尺寸赋予

    ③为该空间中的“表单元指针”开辟出一个数组，以存放每个表单元的数据（我自己偶尔会绕进去，所以姑且打个注释吧。指针在定义的时候就存在了，而开辟指针空间实际上是为指针所指向的结构体开辟一块空间，这一操作只是让这些被声明好的指针有地方能指，而不是把指针放进去……（我自己也觉得这样特地去说好像有点蠢……））

    ④将这个每个“表单元”初始化为Empty

    ⑤返回这个表的地址

    //—————————————————–//

查找关键字函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Position Find(int key, HashTable H)
{
Position CurrentPos;
int CollisionNum;
CollisionNum = 0;
CurrentPos = Hash(key, H->TableSize);
while (H->TheCells[CurrentPos].Info != Empty && H->TheCells[CurrentPos].Key != key)
{
CollisionNum++;
CurrentPos += 2 * CollisionNum - 1;
if (CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
}
return CurrentPos;
}

    很有意思的函数，我最初并没有看懂为什么CurrentPos是那样计算的，但从结论来说，作者说的对。

    ①声明位置指针CurrentPos

    ②定义碰撞次数CollisionNum=0

    ③得出其本该对应的哈希值

    ④遍历表。如果“该单元状态非空，且关键字不相同”，碰撞次数增加，CurrentPos指针偏移一个 CollisionNum^2（并判断是否超出了表的范围，若超出就把它来回来）

    最妙的就是偏移量计算了。它避免了一些看似需要的乘法和除法。书上还特别叮嘱，不要改变While的判断条件的先后顺序（这是很有必要，也很有趣的方法。当你发现该单元格内数据为Empty，则直接返回这个地址了，而不是返回NULL。这会为下一个Insert函数提供很多便利。并且，也是非常有必要的是，对于没有初始化的单元格内的Key，它无疑是有一个确确实实的值的，这样做能省下一点时间。）

F(i)=F(i-1)+2i-1 这是书中给出的算法，在计算机中并不难实现。

    //———————————————————–//

插入函数：

1
2
3
4
5
6
7
8
9
10
void Insert(int key,HashTable H)
{
Position Pos;
Pos = Find(key, H);
if (H->TheCells[Pos].Info != Legitimate)
{
H->TheCells[Pos].Info = Legitimate;
H->TheCells[Pos].Key = key;
}
}

    ①声明，并找出该关键字对应的Pos位置

    ②如果这个关键字已经存在了，就什么都不做；如果不存在，那就往里面放新的关键字。

    不妨假设现在的表中是不存在Deleted状态的单元格。那么Find函数只会返回Legitimate或者Empty。

    返回Legitimate状态的条件，只有一种：①单元格不为空，关键字相同。此时，Find函数会马上返回Legitimate

    返回Empty状态的条件，也只有一种：①单元格为空，直接返回。

    这样的说明分明是没必要的，但我写出来才理顺了。

    删除函数并没有写，我觉得那没太大必要，就做些简单的说明吧。

    本例中，“删除”操作并不是指把数据真的删除，只是把单元格状态标记为Deleted罢了。数据仍然会被保存。

    如果真的想写，和上面的Insert差不多。直接用Find找出来，判断是否为Empty就行了。

双散列与再散列：

双散列：

    原理很朴素。既然第一个哈希值会发生冲突，那再来一个哈希值不就好了？

    比如，现在有两个哈希函数，分别记作Hash1(X)与Hash2(X)，其中，X为关键字。

    假如现在我们得到的第一个哈希值Hash1所对应的位置已经有先来的人了，位子已经被占了，那这个X肯定没办法放进去了；那么，便再计算这个X的Hash2，发现第二个位子还是空的，于是我们把Hash2放进去。这就是原理，但论谁都应该会有一些疑问，写在下面。

对双散列的思考：

    很明显，这种策略并不能从根本上解决问题，甚至也都没办法从基础上解决问题。因为表仍然是那一张，只不过每个关键字现在能够拥有两个哈希值了，但这对每一个关键字来说都是一样的。或许一个好的哈希函数能够在这种情况下尽可能的填补缺陷(比方说，第一个哈希函数算出来的值大多数占据了表的一半，而另外一个哈希函数则占据另外一半，那这种对半开的函数就非常棒了。当然，这只是一种愿望，实际中不一定真的存在这种巧合)，但情况仍然相对糟糕。

    那比方说三散列呢？四散列？看起来好像都是可行的策略，但要设计出这种方案着实困难。对于哈希函数的设计既复杂也浪费，而且往往还不能得到期望的结果。

    当然，实际情况其实也并没有那么糟糕。放到实际情况中去考量的话，这种策略预期的探测次数几乎和随机冲突解决方法的情形是相同的。

    吸引人吗？是的，吸引人。但我也不是很懂就是了。

再散列：

    同样不难，比起下一个可扩散列来讲，这要随和的多了。

    原理也很简单。当表不够大了，就把表扩大一倍不就行了（这个一倍也是有原因的，具体情况适当了解即可）？

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
HashTable ReHash(HashTable H)
{
int OldSize;
OldSize = H->TableSize;
Cell* OldCells;
OldCells = H->TheCells;
H = InitializeTable(2 * OldSize);
for (int i = 0; i < OldSize; i++)
{
if (OldCells[i].Info == Legitimate)
Insert(OldCells[i].Key, H);
}
delete[] OldCells;
return H;
}

    很好理解的，书上给的代码相当易懂，就不解释了。

≡