Hash Table 散列表（待完善）

Posted on | In , | |
Words count in article: 3.9k | Reading time ≈ 16

散列表

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

散列函数

散列函数，顾名思义，它是一个函数。如果把它定义成 hash(key) ，其中 key 表示元素的键值，则 hash(key) 的值表示经过散列函数计算得到的散列值。

散列函数的特点：

  1. 确定性
    如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。

  2. 散列碰撞（collision）
    散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。

  3. 不可逆性
    一个哈希值对应无数个明文，理论上你并不知道哪个是。

  4. 混淆特性
    输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

常见的散列函数

  1. MD5
    MD5 即 Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有 MD5 实现。

将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5 的前身有 MD2 、MD3 和 MD4 。

MD5 是输入不定长度信息，输出固定长度 128-bits 的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个 128-bits 散列。

基本方式为，求余、取余、调整长度、与链接变量进行循环运算，得出结果。

MD5 计算广泛应用于错误检查。在一些 BitTorrent 下载中，软件通过计算 MD5 来检验下载到的碎片的完整性。

  1. SHA-1
    SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

SHA-1 曾经在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5的后继者。

散列冲突

理想中的一个散列函数，希望达到

如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

这种效果，然而在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的，即使是 MD5 或者 由美国国家安全局设计的 SHA-1 算法也无法实现。

事实上，再好的散列函数都无法避免散列冲突。

为什么呢？

这涉及到数学中比较好理解的一个原理：抽屉原理。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。

对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。

那应该如何解决散列冲突问题呢？

常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

开放寻址法

定义：将散列函数扩展定义成探查序列，即每个关键字有一个探查序列h(k,0)、h(k,1)、…、h(k,m-1)，这个探查序列一定是0….m-1的一个排列（一定要包含散列表全部的下标，不然可能会发生虽然散列表没满，但是元素不能插入的情况），如果给定一个关键字k，首先会看h(k,0)是否为空，如果为空，则插入；如果不为空，则看h(k,1)是否为空，以此类推。

开放寻址法是一种解决碰撞的方法，对于开放寻址冲突解决方法，比较经典的有线性探测方法（Linear Probing）、二次探测（Quadratic probing）和 双重散列（Double hashing）等方法。

1.gif)

线性探测法一个很大的弊端就是当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。

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
//开放地址法散列表
#define MAXTABLESIZE 100000 // 允许开辟的最大散列表长度
typedef int ElementType; //关键词类型用整数
typedef int Index; //散列地址类型
typedef Index Position; //数据所在位置与散列地址是同一类型
//散列单元状态类型， 分别对应： 有合法元素、空单元、有已删除元素
typedef enum {Legitimate, Empty, Deleted} EntryType;

typedef struct HashEntry Cell; // 散列表单元类型
struct  HashEntry
{
	ElementType Data;//存放元素
	EntryType Info; //单元状态
};

typedef struct TblNode *HashTable; //散列表类型
struct  TblNode //散列表结点定义
{
	int TableSize; //表的最大长度
	Cell *Cells; //存放散列单元数据的数组
};

int NextPrime(int N)
{//返回大于N且不超过MAXTABLESIZE的最小素数
	int i, p = (N%2)? N+2 : N+1; //从大于N的下一个奇数开始

	while( p <= MAXTABLESIZE)
	{
		for(i =(int)sqrt(p); i>2; i--)
		{
			if(!(p%i)) break;// p不是素数
		}
		if(i == 2) break;//for正常结束， 说明p是素数
		else p+=2; //否则试探下一个奇数
	}
	return p;
}


HashTable CreateTable( int TableSize)
{
	HashTable H;
	int i;

	H = (HashTable)malloc(sizeof(struct TblNode));
	//保证散列表最大长度是素数
	H->TableSize = NextPrime(TableSize);
	//声明单元数组
	H->Cells = (Cell*)malloc(H->TableSize*sizeof(Cell));
	//初始化单元状态为“空单元”
	for(i = 0; i<H->TableSize; i++)
	{
		H->Cells[i].Info = Empty;
	}
	return H;
}

二次探测方法

二次探测是二次方探测法的简称。顾名思义，使用二次探测进行探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列为 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。

1

以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。

按照二次探测方法的操作，有冲突就先 + 1^2，8 这个位置有值，冲突；变为 - 1^2，6 这个位置有值，还是有冲突；于是 - 2^2， 3 这个位置是空闲的，插入。

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
//平方探测法的查找与插入：
Position Find( HashTable H, ElementType Key )
{
    Position CurrentPos, NewPos;
    int CNum = 0; /* 记录冲突次数 */
 
    NewPos = CurrentPos = Hash( Key, H->TableSize ); /* 初始散列位置 */
    /* 当该位置的单元非空，并且不是要找的元素时，发生冲突 */
    while( H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key ) {
                                           /* 字符串类型的关键词需要 strcmp 函数!! */
        /* 统计1次冲突，并判断奇偶次 */
        if( ++CNum%2 ){ /* 奇数次冲突 */
            NewPos = CurrentPos + (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
            if ( NewPos >= H->TableSize )
                NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
        }
        else { /* 偶数次冲突 */
            NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
            while( NewPos < 0 )
                NewPos += H->TableSize; /* 调整为合法地址 */
        }
    }
    return NewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/
}
 
bool Insert( HashTable H, ElementType Key )
{
    Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */
 
    if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占，说明Key可以插入在此 */
        H->Cells[Pos].Info = Legitimate;
        H->Cells[Pos].Data = Key;
        /*字符串类型的关键词需要 strcpy 函数!! */
        return true;
    }
    else {
        printf("键值已存在");
        return false;
    }
}

双重散列方法

所谓双重散列，意思就是不仅要使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

1.gif)

事实上，不管采用哪种探测方法，只要当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，需要尽可能保证散列表中有一定比例的空闲槽位。

一般使用加载因子（load factor）来表示空位的多少。

加载因子是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。

链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。如下动图所示，在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#define KEYLENGTH 15                   /* 关键词字符串的最大长度 */
typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
typedef int Index;                     /* 散列地址类型 */
/******** 以下是单链表的定义 ********/
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
/******** 以上是单链表的定义 ********/
 
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    List Heads;    /* 指向链表头结点的数组 */
};
 
HashTable CreateTable( int TableSize )
{
    HashTable H;
    int i;
 
    H = (HashTable)malloc(sizeof(struct TblNode));
    /* 保证散列表最大长度是素数，具体见代码5.3 */
    H->TableSize = NextPrime(TableSize);
 
    /* 以下分配链表头结点数组 */
    H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
    /* 初始化表头结点 */
    for( i=0; i<H->TableSize; i++ ) {
         H->Heads[i].Data[0] = '\0';
         H->Heads[i].Next = NULL;
    }
 
    return H;
}
 
Position Find( HashTable H, ElementType Key )
{
    Position P;
    Index Pos;
     
    Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
    P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
    /* 当未到表尾，并且Key未找到时 */ 
    while( P && strcmp(P->Data, Key) )
        P = P->Next;
 
    return P; /* 此时P或者指向找到的结点，或者为NULL */
}
 
bool Insert( HashTable H, ElementType Key )
{
    Position P, NewCell;
    Index Pos;
     
    P = Find( H, Key );
    if ( !P ) { /* 关键词未找到，可以插入 */
        NewCell = (Position)malloc(sizeof(struct LNode));
        strcpy(NewCell->Data, Key);
        Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
        /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
        NewCell->Next = H->Heads[Pos].Next;
        H->Heads[Pos].Next = NewCell; 
        return true;
    }
    else { /* 关键词已存在 */
        printf("键值已存在");
        return false;
    }
}
 
void DestroyTable( HashTable H )
{
    int i;
    Position P, Tmp;
     
    /* 释放每个链表的结点 */
    for( i=0; i<H->TableSize; i++ ) {
        P = H->Heads[i].Next;
        while( P ) {
            Tmp = P->Next;
            free( P );
            P = Tmp;
        }
    }
    free( H->Heads ); /* 释放头结点数组 */
    free( H );        /* 释放散列表结点 */
}

1.gif)

HashTable-Cpp

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#ifndef _HASH_MAP
#define _HASH_MAP

#include <vector>
#include <string>
using namespace std;

int operator % (const string & text, int max) {
	int code = 0;
	for (int i = 0; i < text.size(); ++ i) {
		int code1 = text[i];
		code1 = code1 << (i * 8 % 24);
		code = code ^ code1;
	}
	return code % max;
}

class NoSuchKeyException {};

template <typename K, typename V>
class HashTable
{
private:
		
	class Entry
	{
	public:
		K key;
		V value;
		bool isInUse;
		
		Entry() {
			isInUse = false;
		}
	};
	
	Entry * entries;
	
	int capacity;
	int count;
	
	void initialize(int capacity2) {
		count = 0;
		capacity = capacity2;
		entries = new Entry[capacity];
	}
	
	void assign(const HashTable & map2) {
		count = map2.count;
		capacity = map2.capacity;
		entries = new Entry[capacity];
		for (int i = 0; i < capacity; ++ i) {
			entries[i] = map2.entries[i];
		}
	}
	
public:
	
	HashTable() {
		initialize(2);
	}
	
	~HashTable() {
		delete [] entries;
	}
	
	HashTable(const HashTable & map2) {
		assign(map2);
	}
	
	HashTable & operator = (const HashTable & map2) {
		delete [] entries;
		assign(map2);
		return (*this);
	}
	
	void clear() {
		delete [] entries;
		initialize(2);
	}
	
private:
	
	int hashIndex(const K & key) const {
		return key % capacity;
	}
	
	int find(const K & key) const {
		int index = hashIndex(key);
		while (true) {
			if (! entries[index].isInUse) {
				return index;
			}
			if (entries[index].key == key) {
				return index;
			}
			index = (index + 1) % capacity;
		}
	}
	
	void resize(int capacity2) {
		Entry * entries0 = entries;
		int capacity0 = capacity;
		initialize(capacity2);
		for (int i = 0; i < capacity0; ++ i) {
			if (entries0[i].isInUse) {
				put(entries0[i].key, entries0[i].value);
			}
		}
		delete [] entries0;
	}
	
public:
	
	void put(const K & key, const V & value) {
		int index = find(key);
		entries[index].value = value;
		if (entries[index].isInUse) return; //已经存在
		
		entries[index].isInUse = true;
		entries[index].key = key;
		
		++ count;
		if (count > capacity / 2) {
			resize(capacity * 2);
		}
	}
	
	V get(const K & key) const {
		int index = find(key);
		if (! entries[index].isInUse) {
			throw NoSuchKeyException();
		}
		return entries[index].value;
	}
	
	bool remove(const K & key) {
		int index = find(key);
		if (! entries[index].isInUse) return false; //不存在
		fillNotInUseEntry(index);
		
		-- count;
		if (count < capacity / 4) {
			resize(capacity / 2);
		}
		return true;
	}
	
private:
	
	void fillNotInUseEntry(int index) { //补上被删之后的位置，否则下次查找的时候那个是空 然而其实跟他一样的key产生的其他的index不是空 造成错误
		int next = index;
		while (true) {
			next = (next + 1) % capacity;
			if (! entries[next].isInUse) { //下一个index已经是false无使用的，所以可以直接将当前index设置为false从而remove掉
				entries[index].isInUse = false;
				return;
			}
			//运行到这里说明下一个index有记东西
			int index0 = hashIndex(entries[next].key); //找到那个key所对应的最初计算得到的位置index0
			if (index < next) {    //若当前元素的哈希位置位于间隙和其当前位置之间，则不选择该元素。
				if (index0 > index &&
					index0 <= next) continue;  
			}
			else {
				if (index0 > index ||
					index0 <= next) continue;  
			} 
			entries[index] = entries[next]; //元素的哈希位置在允许的范围之外，即它为受影响的后置元素。
			index = next;   //选择该元素填充间隙。并删除该元素产生一个新间隙       
		}
	}
	
public:
	
	bool containsKey(const K & key) const {
		int index = find(key);
		return (entries[index].isInUse);
	}
	
	int size() const {
		return count;
	}

	vector<K> getKeys() const {
		vector<K> vec;
		for (int i = 0; i < capacity; ++ i) {
			if (entries[i].isInUse) {
				vec.push_back(entries[i].key);
			}
		}
		return vec;
	}
	
};

#endif


////////////////////////////////////
// TEST

#include <iostream>
#include <sstream>
using namespace std;

int main() {
	HashTable<string, double> map;
	for (int i = 0; i < 1000; ++ i) {
		stringstream ss;
		ss << "text" << (1 + i);
		map.put(ss.str(), 1.5 + i);
	}
	cout << map.size() << endl;
	for (int i = 0; i < 1000; ++ i) {
		stringstream ss("text");
		ss << "text" << (1 + i);
		if (! map.containsKey(ss.str())) {
			cout << "bad" << endl;
		}
		else {
			//cout << map.get(ss.str()) << " ";
		}
	}
	vector<string> keys = map.getKeys();
	for (int i = 0; i < keys.size(); ++ i) {
		map.remove(keys[i]);
	}
	cout << map.size() << endl;
}

这里的删除操作可能有点复杂，可以考虑给位置加多几个状态 例如填了东西，已经删除， 没用过 三个状态。
还有其他解决方法 例如用链表法 或者自然溢出

后续完善哈希表的高级操作与应用 以及例题 模板？

Donate? comment?