rambo

HashTable（一）

2015年5月26日 Data Strcuture 0 Comments

Hash Table（散列表）在插入、删除、搜寻等操作上具有“常数平均时间” 的表现。这种表现以统计为基础，不需要依赖于输入元素的随机性。

可提供对任何有名项(named item)的存取操作和删除操作。由于操作对象是有名项，所以hash table可以视作为一种字典结构。一般情况下，记录是由若干字段组成的，每个字段负责保存记录所代表实体的一段特殊类型的信息。键(key）就是用来查找的数据成员。哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

举例来说，如果所有元素都是16bits，且 为无符号整数，范围为0~65535，首先配置一个array A，拥有65535个元素，索引号码为0~65535，初始值全部为0。每一个元素值代表相应元素的出现次数，插入元素i，A[i]++；删除元素i，A[i]--。搜寻元素i，检查A[i]是否为0。这种方法的额外负担是array的空间和初始化时间。这其实也是“计数排序的思想”。

这个方法存在两个问题，1）如果元素是32-bits，那么array A的大小为2^{32}=4GB，显然array的大小太大了。2）如果元素是字符串而非整数，就无法被拿来作为array的索引。（当然每个字符字可以用7-bit的数值（即ASCII码编码），产生的索引值会非常大）。

散列表及散列函数

把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。(Key mod Tablesize)。显然，单元的数目是有限的。需要寻找一种散列函数，该函数要在单元之间均匀地分配键。理想情况下应保证任何两个不同的键映射到不同的单元。当两个键散列到同一个值时，成为冲突(collision)（若表的大小是10而键的个位是零）。 好的方法是保证表的大小是素数，同时当输入键为随机整数时，散列函数不仅运算简单而且键的分配很均匀。

散列法（hashing）的思想就是把键分布在一个称为散列表(hash table)的一维数组中H[0,...,tablesize-1]，即把键映射到0~tablesize-1中的某个数，并放到适当的单元。

  • 把键通过hash函数转换成一个整型数字，将该数字对数组长度取余（key mod tablesize)，取余结果为数组下标，将value存在以该数字为下标的数组空间中。
  • 当使用哈希表进行查询的时候，即再次利用哈希函数将key转换为对应的数组下标，并定位到该空间获取value。（利用数组的定位性能进行数据定位）

显然，如果散列表长度m小于键的数量n，就会发生碰撞（collision），就会有两个或者更多的键被散列到散列表的同一个单元的现象。即使m相对于足够大，这种碰撞还是会发生。在最坏的情况下，所有的键都会散列到散列表的同一个单元格中。QQ截图20150626225444

散列函数的选择：比如表的大小是10，而键的个位都是0，那么取余的散列函数就一个不好的选择。好的办法是保证表的大小是素数。当输入的键为随机整数时，散列函数不仅简单而且键分配均匀。通常，键是字符串，这种情况下，散列函数需要仔细选择。

1）把字符串中的字符的ASCII码值相加起来。这显然是一种不均匀的分配，因为求模可能会不起作用。

1
2
3
4
5
6
7
int hashmap1(const string &key, int tablesize){
int hashVal = 0;
for (int i = 0; i < key.length(); i++){
hashVal += key[i];
}
return hashVal%tablesize;
}

2）假设Key至少有3个字符。散列函数只考察前3个字符。

1
2
3
int hashmap2(const string &key, int tablesize){
return (key[0] + 27 * key[1] + 729 * key[2]) % tablesize;
}

3）涉及键中的所有字符。允许溢出，可能会引进负数，在末尾有附加的测试。

Horner 算法是以英国数学家 William George Horner 命名的一种多项式求值的快速算法，实际上，这种快速算法在他之前就已经被Paolo Ruffini使用过了。而中国数学家秦九韶提出这种算法要比William George Horner 早600多年。

1

直接计算的话，需要进行的乘法次数为：1+2+3+......+n，O(n^{2})

Horner给出的算法：

2

构造序列:

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//用计算散列函数节省下来的时间来补偿由此产生的对均匀分布的函数的轻微干扰
int hashmap3(const string&key, int tablesize){
string s;
if (key.size()>1024)  //如果str太长，则只取前1024个字符
s = key.substr(0, 1024);
else s = key;
int hashVal = 0;
for (int i = 0; i < key.length(); i++){
hashVal = 37 * hashVal + key[i];  //Horner 法则
}
hashVal %= tablesize;
if (hashVal < 0)//允许溢出，可能会引进负数，需要附加测试
hashVal += tablesize;
return hashVal;
}

 解决碰撞方法

1、分离链接法

将散列到同一个值得所有元素保留到一个链表中，可以使用标准库中表的实现方法（如果空间紧，避免使用，因为其实现为双向链表）或者采用其他的数据结构，如二叉查找树、甚至是另外一个散列表，它们的查找速度都比链表要快。但是我们期望的是散列函数足够地好、槽足够地多，所以对应的链表都应该很短，不值得去尝试更复杂的结构。

当一个HashTable太满后，发生冲突的概率就会大大增加。我们的策略是：当达到事先设定的装载因子时，就把槽位扩展成原先的2倍以上（取最小的素数），重新进行再散列。原先的HashTable完全释放，申请新的更大的空间，然后把已有的元素重新散列到新的HashTable。再散列开销很大，但我们期望的是发生再散列的次数很少。

QQ截图20150909173721

例子：一个可以存储在一般散列表中的Employee类，该类使用name成员作为键值。

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
#ifndef _HASHTABLE_H
#define _HASHTABLE_H
#include <string>
#include <vector>
#include <list>
using namespace std;
 
template<typename HashObj> class HashTable{
private:
int capacity;//已容纳的元素个数
int slots; //取素数
double alpha; //loading factor
vector<list<HashObj> > table;//the array of lists  here two > has a space,>> is an operator
int hashmap(const HashObj& key);//内部散列函数，负责将数据映射到[0，slots-1]
void rehash();//当达到loading factor时，槽数扩大为原来的2倍（取最小的素数），进行再散列
public:
bool contain(const HashObj& key);//判断一个数是否在HashTable中
bool insert(const HashObj& key); //插入一个元素到HashTable中
//从HashTable中删除一个元素。如果指定元素不在HashTable中，则删除失败，返回false
bool remove(const HashObj &key);
 
HashTable(int slots = 10007, double alpha = 0.7) :slots(slots), alpha(alpha){
capacity = 0;
table.resize(slots);
}
 
int getSlots(){
return slots;
}
 
void setSlots(int num){
slots = num;
}
};
//将string转换为int
int hashString(const string&key){
string s;
if (key.size() > 1024)  //如果str太长，则只取前1024个字符
s = key.substr(0, 1024);
else s = key;
int hashVal = 0;
for (int i = 0; i < key.length(); i++){
hashVal = 37 * hashVal + key[i];  //Horner 法则
}
//hashVal %= tablesize;
//if (hashVal < 0)//允许溢出，可能会引进负数，需要附加测试
// hashVal += tablesize;
return hashVal;
}
 
 
class Employee{
private:
string name;
double salary;
int seniority;
public:
Employee(string name = "", double salary = -1, int seniority = -1) :name(name), salary(salary), seniority(seniority){}
 
bool operator ==(const Employee&item)const{
return this->name == item.name;
}
 
bool operator !=(const Employee&item)const{
return !(*this == item);// 重载过的==号
}
 
const string &getName()const{
return name;
}
int Employhash()const{
return hashString(name);
}
void setName(string str){
name = str;
}
void setSalary(double sala){
salary = sala;
}
void setSenirioty(int  senior){
seniority = senior;
}
};
 
#endif

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 "HashTable.h"
#include <assert.h>
#include<cassert>
#include<algorithm>
//using namespace std;
 
template<typename HashObj>int HashTable<HashObj>::hashmap(const HashObj& key){
int hashVal = key.Employhash();
hashVal %= slots;
if (hashVal < 0)//允许溢出，可能会引进负数，需要附加测试
hashVal += slots;
return hashVal;
 
}
 
//检查链表是否该元素已经在表中了，如果要插入重复元，
//那么通常留出一个额外的数据成员，当出现匹配事件时这个数据成员增加1.
template<typename HashObj>bool HashTable<HashObj>::contain(const HashObj&key)
{
int index = hashmap(key);
const list<HashObj> &whichlist = table[index];
return find(whichlist.begin(), whichlist.end(), key) != whichlist.end();
}
 
//如果差个元素是新的元素，那么一般被插到表的前端，因为最后插入的元素最有可能不久再次被访问
template<typename HashObj> bool HashTable<HashObj>::insert(const HashObj &key)
{
int index = hashmap(key);
list<HashObj> &whichlist = table[index];
if (find(whichlist.begin(), whichlist.end(), key) != whichlist.end())
return false;
whichlist.push_back(key);
capacity++;
if (capacity*1.0 / slots > alpha)
rehash();
return true;
}
 
template<typename HashObj> bool HashTable<HashObj>::remove(const HashObj &key)
{
int index = hashmap(key);
list<HashObj> & whichlist = table[index];
typename list<HashObj>::iterator itr = find(whichlist.begin(), whichlist.end(), key);
if (itr == whichlist.end())
return false;
whichlist.erase(itr);//删除list中一个元素
capacity--;
return true;
}
 
template<typename HashObj>void HashTable<HashObj>::rehash(){
int oldSlots = getSlots();
int newSlots = oldSlots * 2;
//while (!isPrime)
 
vector<list<HashObj> > oldVector = table;
for (int i= 0; i < table.size(); i++)
table[i].clear();
 
table.resize(newSlots);
//成员函数可以直接使用类定义中的任一成员(数据成员或函数成员)
setSlots(newSlots);
capacity = 0;
 
for (int i = 0; i < oldVector.size(); i++){
typename list<HashObj>::iterator itr = oldVector[i].begin();
while (itr != oldVector[i].end())
insert(*(itr++));
}
 
}

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
int _tmain(int argc, _TCHAR* argv[]){
const int arrsize = 9;
HashTable<Employee> hashTable(7, 1.0);//刚开始设槽数为7
string names[arrsize] = { "hujintao", "jiangzeimng", "heizeming",
"chaogai", "jingchengwu", "liangchaowei",
"wenjiabao", "zhangsanbao", "zengxiaoxian" };
double salaries[arrsize] = { 111.1, 121.2, 132.2,
10.5, 19.8, 89.2,
99.2, 100.2, 10.2 };
Employee employee[arrsize];
for (int i = 0; i < arrsize; ++i){
employee[i].setName(names[i]);
employee[i].setSalary(salaries[i]);
employee[i].setSenirioty(i + 1);
}
 
for (int i = 0; i < arrsize; ++i){
bool insertsuccess=hashTable.insert(employee[i]);
}
 
assert(hashTable.getSlots() == 14);       //扩容后槽数应该为17
 
for (int i = 0; i < arrsize; ++i){
assert(hashTable.contain(employee[i]));
hashTable.remove(employee[i]);
assert(!hashTable.contain(employee[i]));
}
 
return 0;
}

111

在这里，此时hashmap值为6，放入(list) table[6]中，push_back是在链尾加入；

112

113

114

当capacity为8时，需要rehash()，槽位数应为素数，这里省略判断，直接扩大一倍。(这里我没有进行素数测试)

115

2、 不使用链表的散列表

分离链接散列算法的缺点是使用链表，由于给新单元分配地址需要时间，导致算法速度较慢；使用链表的另一个解决冲突方法是当冲突发生时尝试选择另一个单元 ，直到找到空的单元。对于不使用分离链接法的散列表来说，其装填银子应该低于\lambda=0.5，称为“探测散列表”。

2.1、线性探测

负责系数（loading factor）

假设一个散列表能容纳n个元素，具有m个槽（表长），负载系数为 n/m。假如散列函数能够使键均匀分配，每一个元素散列到m个槽位的可能性是相同的，并与其他元素已被散列到什么位置独立无关（称为简单一致散列，simple uniform hashing）。平均情况下查找一个元素是否在散列表中的时间复杂度为O(1+\alpha)。

QQ截图20150909172011

hash function计算出某个元素的插入位置，若该位置上的空间已不再可用，那么循序往下一一寻找（如果到达尾端，就绕到头部继续寻找），只要表格足够大，总可以找到一个空间。两个假设：1）表格(array)足够大；2）每个元素都够独立（这个假设太天真）。观察上图，如果新元素为8，9，0，1，2，3中的任何一个，都会落在#3位置上。（即使表相对较空，占据的单元也会开始形成一些区块）新元素如果是4或5或6或7，才会落在相应的位置上。也就是说，平均插入成本的成长幅度远高于负载系数的成长幅度。这种现象称为“主集团”(primary clustering)。可以证明，使用线性探测的预期探测次数对于插入和不成功的查找来说大约为\frac{1}{2}(1+1/(1-\lambda)^{2})，而对于成功的查找来说则是\frac{1}{2}(1+1/(1-\lambda))

2.2、二次探测(quadratic probing)

二次探测主要用于解决主集团问题。如果hash function计算出新元素的位置为H，而该位置实际上已被使用，那么依次尝试H+1^{2},H+2^{2},...,H+i^{2}，而不是像线性探测那样尝试H+1,H+2,...,H+i。

QQ截图20150909184433

对于线性探测来说，让散列表近乎填满元素不是好主意；对于平方探测，情况 甚至更糟：一旦表被填满超过一半，若表的大小不是素数，甚至在表被填满一半之前，就不能保证找到空的单元了。

定理：如果表的大小为素数 ，而且永远保持负载系数在0.5以下（也就是说超过0.5就重新配置并重新整理表格），那么可以保证每插入一个新元素的探测次数不多于2。

举个例子：Tablesize=11，h_{0}(x)=0，h_{1}(x)=1，h_{2}(x)=4，h_{3}(x)=9，h_{4}(x)=5，h_{5}(x)=3，h_{6}(x)=3，h_{7}(x)=5，h_{8}(x)=9

证明：令表的大小Tablesize为一个大于3的（奇）素数。可证前\lceil Tablesize/2 \rceil个备选位置（包括初始位置h_{o}(x)是互异的。其中两个位置是h(x)+i^{2}(mod Tablesize)和 h(x)+j^{2}(mod Tablesize)，其中i\leq,j\leq\lceil Tablesize/2 \rceil。矛盾法，假设这两个位置相同，但i!=j。

QQ截图20150909190808

由于Tablesize为素数，因此，或者i-j=0(mod Tablesize)或者i+j=0(mod Tablesize)。第一种情况显然不可能，因为i、j互异。第二种情况i\leq,j\leq\lceil Tablesize/2 \rceil，也不可能。从而，前\lceil Tablesize/2 \rceil个备选位置是互异的。如果最多有\lfloor Tablesize/2 \rfloor个位置被使用，那么空单元总能够找到。有两点需要记住

  • 如果哪怕表有比一半多一个的位置被填满，那么插入都有可能失败（虽然这种可能性极小）
  • 表的大小是素数。如果不是素数，那么备选单元的个数可能会锐减。例如，若表大小为16，那么备选单元只能在距散列值1、4或9远处。

在散列表中标准的删除操作不能执行，因为相应的单元可能已经引起过冲突，元素绕过它存储在别处。例如，删除89，那么实际上所有剩下的find操作都将失败。

实现复杂度：二次探测需要一个加法(i-1 -> i)，一个乘法（计算i^{2}），另一个加法，以及Mod运算。

QQ截图20150909192918

这个公式表明了可以用前面一个H值来计算下一个H值，而不需要执行二次探测所需的乘法。

二次探测可以消除主集团，但可能会造成次集团(secondary clustering)。两个元素经hash function计算出来的位置若相同，则插入时所探测的位置也相同。

2.3、双散列

双散列选择f(i)=i\cdot hash_{2}(x)，将第二个散列函数应用到x并在距离hash_{2}(x)，2hash_{2}(x)，...等处探测。hash_{2}(x)的选择非常重要。

R为小于Tablesize的素数。

QQ截图20150909193747

如果双散列正确实现，预期探测次数几乎和随机冲入解决方法的情形相同。但是在实践中，键为字符串时，其散列函数的计算很耗时。