词典(二) 哈希表(Hash table)

散列表(hashtable)是一种高效的词典结构,可以在期望的常数时间内实现对词典的所有接口的操作。散列完全摒弃了关键码有序的条件,所以可以突破CBA式算法的复杂度界限。

散列表

逻辑上,有一系列可以存放词条的单元(桶)组成。各个桶按照逻辑次序,在物理上也应当是连续的,因而,可以采用数组来实现,散列表也可以称为桶数组。合法的秩空间[0,R)也可以称作地址空间。

散列函数

散列,即为关键码空间到桶地址空间的映射,hash():key->hash(key)

假设学号为2013300000-2013303999,一个长度为4000的散列表A[0-3999],只需要hash(key)=key-2013300000,即可实现没有空余也没有重复的散列,称为完美散列。

实际上,完美散列是非常困难的,比如,一个电话号码为7位,而一个单位的电话为几千个,此时按照这种映射,仍然需要10^7次方规模的桶数组。定义装填因子为非空桶/桶的总数,此时的利用率非常低。

因此,制定合理的映射,是非常重要的。散列函数的选取,在计算上应当尽量简单,关键码经过映射后尽量占据整个地址空间,并且映射到各个桶的概率应当接近于1/M。简单的散列函数策略有几种:

(1)除余法:hash(key)=key mod M。显然,如此简单的策略会造成很大的问题,随机性并不好而且容易冲突。

(2)MAD法:multiple-add-divide,hash(key)=(a*key+b) mod M。可以看到,除余法是a=1,b=0的特例。相当于是一种线性方法。

(3)数字分析法:从key的特定进制展开中取出特定的若干位。

还有平方取中法、折叠法异或法等...实现的时候为了简单,可以采用随机数法,不过不同的语言和平台随机数的实现方式可能不同,需谨慎。

 template<typename K, typename V> class Hashtable :public Dictionary<K, V>
{
private:
Entry<K, V>** ht;//桶数组,存放词条指针
int M;//桶数组的数量
int N;//词条的数量
Bitmap* lazyRemoval;//懒惰删除标记
#define lazilyRemoved(x) (lazyRemoval->test(x))
#define markAsRemoved(x) (lazyRemoval->set(x))
protected:
int probe4Hit(const K& k);//沿关键码k对应的查找链,找到词条匹配的桶
int probe4Free(const K& k);//沿关键码k对应的查找链,找到首个可用的桶
void rehash();//重散列算法:扩充桶数组,保证装填因子的警戒线之下
public:
Hashtable(int c = );//创建一个容量不小于c的散列表
~Hashtable();//释放桶数组及其中各元素所指向的词条
int size() const { return N; }
bool put(K k, V v);
V* get(K k);
bool remove(K k);
};

散列表的实现,内部主要是维护一个桶数组,外部接口即为词典的接口。

 template<typename K, typename V> Hashtable<K, V>::Hashtable(int c)
{
M = primeNLT(c,,"prime.txt");//不小于c的素数,应当计算好后列表备查
N = ;
ht = new Entry<K, V>*[M];
memset(ht, , sizeof(Entry<K, V>*) * M);
lazyRemoval = new Bitmap(M);
}
int primeNLT(int c, int n, std::string file)//查找素数
{
Bitmap b(n);
std::ifstream ifile(file);
int num;
while (ifile >> num)
b.set(num);
while (c < n)
if (!b.test(c)) c++;//若当前位为0,继续寻找
else
return c;
return ;
}

这里实现的策略,是从事先计算好的文件中选取一个素数作为桶的初始数量。

 template<typename K, typename V> Hashtable<K, V>::~Hashtable()
{
for (int i = ; i < M; i++)
if (ht[i]) delete ht[i];//释放非空的桶
delete ht;
delete lazyRemoval;
}

析构函数要注意,释放掉非空的桶以及用来标记的位图结构。

冲突

散列表的一个很大问题,就是冲突。因为散列的基本思想,就是通过快速把key转换为一个秩,从而可以迅速进行查询、插入和删除这样的词典操作。但是,即使把桶数组设置地非常大,或者选择特别合适的哈希函数,也非常有可能造成冲突,即hash(key1)=hash(key2)。此时,后一个词条插入的时候,对应的已经被占用了。因此,必须采用一种办法,化解这种冲突。常见的冲突排解方法有几种:

(1)多槽位法。把一组冲突的词条设置为一个小规模的词典,分别存放在对应的桶单元中。一种简单的方法,把每个桶细分为小的槽位,比如用向量或者列表来实现。这种方法的缺陷显而易见,很多槽位是空着的,利用率很低。

(2)独立链法。与多槽位法类似,不过把每组冲突的词条组织为一个链表的形式。这种方法的缺点在于,查找冲突的时候需要遍历整个链表。

(3)公共溢出区法。在原来的散列之外另设置一个词典,插入冲突时就转存到其中。

闭散列

说了那么多,最后还是要采用一种别的方法0 0闭散列的方法,就是充分利用散列表中的空桶,桶地址对于散列中的其他桶是开放的,散列内部与外界是封闭的。具体地,采用查找链的方法。最简单的就是线性试探,每次冲突的时候,在后继中查找最近的空桶,第i次试探的桶单元为(hash(key)+i) mod M。这种方法也存在较大的缺陷,容易局部聚集从而加长查找的长度,可以采用平方试探法等方法改进。

这种线性查找的方法,可能会因为多个相邻的冲突词条,而产生彼此的交替,在这种情况下,查找的长度也会增大。如果删除了其中的元素,查找链会断裂,从而影响到其他词条的查询。一种解决的办法是懒惰删除,即删除一个元素后,用位图结构来标记,删除掉实际的词条。这样,在实际的查找过程中,无论桶是否空,只要标记存在,就可以继续向下进行查找。基于线性试探的策略如下:

 template<typename K, typename V> V* Hashtable<K, V>::get(K k)
{
int r = probe4Hit(k);
return ht[r] ? &(ht[r]->value) : NULL;
}
template<typename K, typename V> int Hashtable<K, V>::probe4Hit(const K& k)//寻找匹配的桶
{
int r = hashCode(k) % M;
while ((ht[r] && (k != ht[r]->key)) || (!ht[r] && lazilyRemoval(r)))//冲突,或者桶为空但是标记过
r = (r + ) % M;//沿着查找链试探
return r;
}
template<typename K, typename V> bool Hashtable<K, V>::remove(K k)
{
int r = probe4Hit(k); if (!ht[r])return false;//如果词条不存在无法删除
delete ht[r]; ht[r] = NULL; markAsRemoved(r); N--;
return true;
}

对于插入操作,需要先寻找一个合适的空桶,如果没有空桶,那么需要重新分配一个哈希表。为了保证效率,规定装填因子不超过1/2。

 template<typename K, typename V> bool Hashtable<K, V>::put(K k, V v)
{
if (ht[probe4Hit(k)]) return false;
int r = probe4Free(k);//寻找空桶(控制装填因子,故必然成功)
ht[r] = new Entry<K, V>(k, v); ++N;//懒惰删除标志无需复位
if (N * > M) rehash();//装填因子小于0.5重散列
return true;
}
template<typename K, typename V> int Hashtable<K, V>::probe4Free(const K& k)
{
int r = hashCode(k) % M;//除余法确定起始桶
while (ht[r]) r = (r + ) % M;//沿着查找链直到首个空桶(无论是否带有懒惰删除标记)
return r;
}
template<typename K, typename V> void Hashtable<K, V>::rehash()
{
int old_capacity = M;//记录之前的桶数
Entry<K, V>** old_ht = ht;
M = primeNLT( * M, , "prime.txt");//容量加倍
N = ; ht = new Entry<K, V>*[M]; memset(ht, , sizeof(Entry<K, V>*)*M);
delete lazyRemoval; lazyRemoval = new Bitmap(M);//新申请一个位图
for (int i = ; i < old_capacity; i++)
if (old_ht[i])
put(old_ht[i]->key, old_ht[i]->value);
delete[] old_ht;
}

rehash()的策略并不复杂,其实就是重新分配一个数组,并把原来的数组转移到其中,再释放掉之前的数组。

最后,因为key不可能总数整数,因此,需要把char double long等等类型转换为hashcode,方法有很多,在此不表0 0

在介绍理论的最后0 0哈希函数的选择以闭策略的选择都有很多,其实只要弄懂散列的思想以及实现就可以了,细节的方法,各种语言都有自己的哈希表,甚至好多种...

散列的应用

没刷过题,就先搬运下书上的几个例子吧。

桶排序

桶排序可以打破CBA式排序理论上nlogn的界限。通过哈希的策略,通过独立链构建方法,即可实现基于哈希的排序。具体操作,即使用最简单的哈希函数hash(key)=key,把数字存入相应的桶,然后再从头到尾输出桶数组即可。只需要遍历数字一遍,常数时间计算hash(key),再遍历输出一遍即可,复杂度为O(n)。

基数排序

假设一组词条采用字典序等方式排序,比如英文词典。这时,只需要用多趟桶排序即可完成。具体地,从优先级最低的位开始进行桶排序,排序后的结果再按照优先级的顺序,知道最后一趟排序完,结果即为所需。具体的证明就忽略了...复杂度为O(t*(n+M)),其中M为各个字段的取值范围的最大值,t为趟数。

上一篇:PHP关联数组和哈希表(hash table) 未指定


下一篇:golang数据结构之散哈希表(Hash)