通俗的说，程序是能够完成既定目标的具有特定逻辑组织形式的指令集序列。既然有现实的需求，那么我们知道外界环境必然会给予程序某些特定形式的“输入”，然而在机器的内部，这种“输入”将转换为数据的形式，继而这就要求我们为用以描述现实世界需求的数据建立一个结构化的模型，使其能够被机器指令高效的处理。通常，对于数据的处理无外乎以下几种：读取/更新/删除数据项，或者插入新项，其中除插入外其他几种操作均要求对集合进行搜索。而结构化的模型可以通过数组、链表或者树形结构等建立，不同的建模方式对于数据处理中的各种操作有不同的性能表现。由于本文是偏向介绍算法，所以对于数组、链表等数据结构只做简单介绍，并将由这两种结构引出本文的主题——散列，而对树结构的介绍及对其进行操作的算法将会写在后续文章中。一般来讲，数据结构将直接影响对其处理的算法的选择，在本文中的散列函数算法又会反过来影响散列表这种结构之于数据的存贮效率，可以说，数据结构与算法的关系就好比是一卵双生。
我们先简单看一下数组与链表这两种数据结构存储数据的方式：
图1
由上图，我们可以得出以下几点：
- 通常总是会为动态集合的字典操作预留一定的资源，并且通过额外的空间记录现有元素集合的大小或是链表的表头/尾，因此对于插入操作来说其运行时间为O(1)。
- 因为读取/更新操作均建立在搜索的基础上，因此运行效率取决于定位待操作的数据项的时间。我们首先来看数组，如果所存储的元素集是无序的，那么搜索集合中的任一元素的期望时间E=(1+2+…+n)/n=O(n)，因此搜索某个数据项几乎总是需要遍历整个集合。如果需要大量的搜索操作，那么对于现有集合可以通过排序执行适当的预处理，并在此之后调用运行时间为O(㏒n)的二分搜索以获得较好的整体性能。但这几乎总是受到外界环境不稳定因素的限制，例如动态插入操作将导致现有结构的序性质遭到破坏，并且这种预处理将会消耗O(n)或是O(n㏒n)的运行时间。再来看链表结构，因为其无法提供随机访问能力，因此这决定了即使对链表进行排序也无法运用二分搜索快速查找具有某个固定值的元素，并且同未排序的普通数组一样，链表的搜索操作的期望时间也为O(n)。
- 对于数据的删除操作，我们发现在有序数组中还需要将已删除数据项所占位置之后的元素逐个前移，使得在维持序关系时整个数组仍然保持紧凑，而在链表中，虽然只需改变待删除数据项的前驱的指向，但高效利用空间的前提条件将会要求我们能够维护一个空闲链表(freelist)，这些都需要额外的时间开销。
- 最后我们知道这两种结构对存储空间的利用率都很高，谁说这不是一个优点呢，至少对于散列来说是的。
需要注意的两点是，在实际情况中还可以运用循环数组/链表，双向链表等变形，数据结构的合理选择总是需要考虑特定的应用需求和外部环境。
什么是散列
在解释散列的含义之前，我们先来深入的观察一下普通数组这种数据结构，由图1所示，将集合{a,b,c,d,e,f}存储在数组中时占据了索引为0~5的6个存储空间，我们可以形式化的表示为有序对(An ordered pair)的集合，即{(a,0),(b,1),(c,2),(d,3),(e,4),(f,5)}。但其实这个集合中任意一个有序对的元素之间的关系是未定义的(undefined)，因此这样的有序对集合可以有6!个。然而我们是否可以构造一个关系，使得待存储的集合{a,b,c,d,e,f}中的任意一个元素通过这个关系都能找到一个指定的索引值，由下图更形象的表示：
图2
根据上图我们知道原有集合中的元素被散列之后所得到的有序对的集合为{(d,0),(b,2),(c,2),(a,3),(f,4),(e,5)}。其中，散列表中的1号槽为空，表示经过散列函数作用之后，原集合中没有任何元素被散列至该位置，而2号槽中则存在两个元素，将两个不同元素散列至相同位置的情形我们称为碰撞(Collision)。如上图所示，我们通过使用链表将不同元素链接起来解决碰撞，在后文中还将介绍另外一种称为开放寻址(Open
addressing)的解决方法。这里更具体的说明一下链接法的链接形式：因为散列至同一个槽的元素并无顺序上的先后要求，因此为效率计，我们将总是采用在链表头插入碰撞元素的做法，最终导致的结果是，在一个链表中，越靠近表头的节点，在原数组中被散列的次序越靠后。综上所述，可以对散列函数hash进行如下形式化定义：
设在大小为N的集合中存在元素elem，存储原集合中元素的散列表共有m个槽位，则有
hash: elem→γ∈{0,1,2,…,m-1}
散列分析
这里主要是对链接散列进行分析，其中的问题分析与解决思路同样适用于开放寻址。因为通过设计某个散列函数hash我们定义了集合元素与散列表下标之间一一对应的关系，从而使得搜索操作只需在常量时间内即可完成，即假定存在某个待搜索的关键字key，那么该关键字必定在槽hash(key)中。唯一需要关心的问题是，集合中的元素在被散列之后的分布状况如何？在最坏情况下，有可能选取的散列函数将所有元素均散列至同一个槽中，使得该散列表实际已退化为链表，在这种情况下的搜索操作将花费O(n)的运行开销。显然，我们并非因为散列具有这种最坏情况才去使用它，而能在多数情况下避免这种“退化”，将要求我们更深入的思考以下两个问题：
- 如何设计一个好的散列函数？
- 散列表的大小为多少较好，是否正如图2所示，使用与原集合大小相同的散列表？我们将通过量化证明。
首先针对第二个问题进行分析，即散列表的大小为多少较好？
- 设所有元素之间均相互独立，且每个元素被散列至每个槽的概率均相等 ------------> 假设①
并设原集合的尺寸为n，散列表的大小为m，装载因子α=n/m -------------->假设②
最重要的是，我们并不考虑散列函数所消耗的计算开销 ---------------->假设③
由假设①，元素被散列至每个槽的概率相等，再根据假设②中散列表的大小为m，有P{elem→γ∈{0,1,2,…,m-1}}=1/m
设待查找的关键字为k，因此存在两种情况：Ⅰ、待查找关键字k不存在； Ⅱ、关键字k存在
然而其实情况Ⅰ的搜索开销即为情况Ⅱ的最坏情况运行时间，因为关键字k不存在时将查找整个链表
以下是更详细的分析：
------>Ⅰ、由假设①，并且根据假设②有装载因子α=n/m，所以α表示每个槽的结点数。因为当待查找的关键字k不存在时，我们必将搜索到该槽中的最后一个结点处，因此在这种情况下的搜索开销为O(α)。
------>Ⅱ、对于关键字k存在的情况，其实不做详细分析我们就已经知道，这种情况下的运行时间必然不超过O(α)，然而单单分析本身就是一件很有趣的事情，为何不做得彻底一些？更重要的是，下面所用到的这种方法，其体现的思想对于分析随机过程将具有极大的益处。
综上可知，如果我们将散列表设定为与原集合大小相同时，装载因子α=1，此时的搜索时间为O(1)，但其实设置为原集合尺寸的1/2或是2倍并没有多大区别。需要注意的是虽然散列表越大导致搜索时间减少，但其所占内存空间将会增大。
设计散列函数
如何设计一个好的散列函数？需要一定的数论功底才能回答，因此这一部分不会去详细解释为什么这样做。尽管脱离了能够对其解释的理论，工程实践将会变得“矮”很多截，但这里所用的一些东西在实际生活中具有广泛应用，为了应用而去了解并积累他们仍是有趣的。此外，无论是字符或是数据在机器内部总是以数值的形式表现，所以总能设置一种机制将任何输入转换为数值，例如对字符'a'进行散列，若将'a'解释为与其对应的ASCII码97，则hash('a')=hash(97)，只是当输入变得复杂时这种设计也将变得更加困难，这里我们将避开这些复杂性而直接假设所有的输入均为某一个数。
- 除余散列法
设 hash(key)=key mod m，其中key表示被散列的关键字，而m则表示散列表的大小，mod则为取余操作。
这是一种比较简单的散列函数，但简单并不意味着高效。当待散列的元素之间存在某种模式时，这种散列法会有相当糟糕的性能表现。对该函数一个有用的指导原则是将m选取为接近待散列集合大小的质数。 - 乘法散列法
设 hash(key)=floor(m×(A×key mod 1))，其中floor()表示对表达式进行下取整，A∈(0,1)，m如上同样表示散列表的大小，且在这种方法中对m并无任何特殊的要求。
[A×key mod 1]表示将key乘上某个在0~1之间的数并取乘积的小数部分，该表达式等价于A×key-floor(A×key)
这里最重要的是A的值应该如何设定，Don•Knuth老大认为A=(√5-1)/2 [黄金分割点] 比较好。 - 全域散列法(universal hashing)
设 hasha,b(key)=(a×key+b) mod m，如同除余散列法中一样，m的值应为质数，而a∈{1,2,3,…,m-1}，b∈{0,1,2,…,m-1}且a,b的值应在运行时动态确定。
全域散列的基本思想是给出hash函数的基本“骨架”，而其中的某些参数通过运行时在指定范围内随机选取确定，从而实际上形成了一个函数簇。根据上述a,b的取值范围，我们知道这个函数簇中存在m×(m-1)个函数。因为对于同一个输入，每次执行时选取不同的参数将拥有不同的性能表现，因此设计的函数实际上独立于任意被散列的关键字。只有当一个相对糟糕的输入——即该输入不构成随机分布，遇到一个选取的相对糟糕的散列函数时，才将导致较差的性能，在多数情况下这类散列往往具有较好的运行时性能表现。 - 完全散列法(perfect hashing)
完全散列法与其说是一种函数设计方法，倒不如说是对碰撞(Collision)情况的另一种解决策略。具体来讲，存在待查找的元素key，经过一次散列，该元素被存放在槽hash(key)处，然而其他元素也有可能被散列至该处，因此对散列至该槽的元素继续进行散列，所得到的值hash'(hash(key))即为元素key的确切存储位置。其中外层hash过程称为一级散列，内层hash'过程称为二级散列。
这个策略会存在几个问题，首先二级散列之后可能还会存在碰撞问题，是否需要进行三级散列甚至更多级的散列？其次，某个槽对应的二级散列函数应如何选取？最后，一级散列中某个槽所对应的二级散列表的尺寸应该如何设置？
这三个问题其实可以一并解决。首先对于是否需要更多级的散列，因为外层的一级散列已经将原集合分为一系列子集，若我们将一级散列表设置为与原集合尺寸相近的大小，同时合理的选取一个散列函数，那么在每个槽中发生碰撞的元素个数将在一个可控范围内，此时如果为了少部分元素再设置三级散列的话，不仅增加了整个结构的复杂性以及对于内存的要求，而且还要再次为三级散列选取合理的散列函数，成本相对较大。接着来看解决二级散列函数的选取问题，我们发现在全域散列法中，只需设置不同的参数，即能生成特定于某个槽的散列函数，若生成的散列函数导致二级散列表中发生碰撞，那么重新从全域散列函数簇中选取，直至不发生碰撞为止即可。另外，只需合理设置二级散列表的大小，这种重新选取的概率将变得极低，一个可行的指导原则是将二级散列表的大小设置为外层散列至该槽的元素个数的平方。
图3完全散列的分析更形象化的说明如图3所示。最后要说明的一点是，这种通过两次散列的方法虽然提供了高效的搜索，但代价是花费了更多的内存空间，同时因为插入操作有可能导致在二级散列表中发生碰撞，因此这种方法只适用于静态关键字集合中，“静态”意指该集合一旦确定，便不再发生动态变化，即不发生插入或是删除操作。
开放寻址(open addressing)
同链接法一样，开放寻址是一种用于解决碰撞的策略。不同之处在于，在链接法中，每个关键字只能对应一个固定的槽，而在开放寻址中，每个关键字可以对应散列表中的多个槽，因为有可能在首次寻址过程中，该槽已被先前的关键字所占据，因而接下来我们根据事先所制定的某个规则继续试探下一个槽是否可用，直至找到一个可用的槽并将关键字存储在其中为止。这里存在的一个问题是，如果仅将待散列的关键字作为函数的输入，那么最终必定只有与其对应的单个输出，因此我们必须寻找一个诱导因子，使得在关键字不变的情况下诱使函数的输出发生变化。因为所有的关键字放在一个散列表中，因而将该诱导因子的值域设置成与散列表的大小相同，能够更充分的利用整个散列表：
设原集合中存在元素elem，诱导因子为i，散列表的大小为m，则有
hash: (elem, i)→γ，其中 i,γ∈{0,1,2,…,m-1}
并且该函数所形成的探查序列为 <hash(elem,0), hash(elem,1), …, hash(elem,m-1)>
这里诱导因子i被形式化地定义为区间[0,m)中的某个值，其取值序列被固定为<0,1,…,m-1>只是为了方便散列函数的实现，实际可根据原集合中的元素所存在的模式制定更具针对性的值域及取值序列，这里我们将重点放在开放寻址中散列函数的设计上。通常在开放寻址中所用的散列函数主要由以下几种：
- 线性试探法
设 hash(key, i)=(hash'(key)+i) mod m，其中 i=0,1,…,m-1，hash'为辅助散列函数
在线性试探中，首次探查位置取决于hash'(key)的值，若发生碰撞，则接下来所探查的位置为(hash'(key)+1) mod m，从而所形成的探查序列为<hash'(key), hash'(key)+1,…, m-1, 0,…, hash'(key)-1>。因为散列表的大小为m，所以整个散列表总共提供m种不同的探查序列。并且由于线性试探使用连续探查的方式，因此随着散列表中元素的增加，所占用的槽逐渐呈连续分布状况，从而增加插入/搜索操作的期望时间。 - 二次试探法
设 hash(key,i)=(hash'(key)+c1i+c2i2) mod m，如上所述，i=0,1,…,m-1，hash'为辅助散列函数，c1，c2为辅助参数
可以发现，线性试探法实际是二次试探的特殊情况，若取参数c1=1，c2=0，那么二次试探将“退化”为线性试探。同样的，整个探查序列也是由hash'(key)所决定的，因为虽然探查序列中各元素之间的增量[c1i+c2i2]不再以线性的方式进行，但对于每个元素来说，引导因子i总是以步长1的方式递增，这就导致所有元素的探查序列的增加方式是相同的，因此整个散列表同样提供m种不同的探查序列。但随着散列表中元素的增加，这种跳跃式的增量方式使得插入/搜索操作的运行时间受到的影响较小。 - 双重试探法
设 hash(key,i)=(hash'(key)+i×hash''(key)) mod m，其中i=0,1,…,m-1，hash'，hash''均为辅助散列函数
双重试探法的首个探查位置为hash'(key)，当产生碰撞之后，接下来的探查位置为(hash'(key)+hash''(key)) mod m，因此我们发现在双重试探法中，不仅初始探查位置依赖于关键字key，探查序列中的增量hash''(key)同样依赖于关键字key，因而整个散列表提供了m2种不同的探查序列，较之于前两种开放寻址具备了更多的灵活性。这里还要注意的是应保证hash''(key)与m互质，因为根据固定的偏移量所寻址的所有槽将形成一个群，若最大公约数p=gcd(m, hash''(key))>1，那么所能寻址的槽的个数为m/p<m，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的槽为<1,
4, 7, 10>，寻址个数为12/gcd(12,3)=4。
最后要注意的一点是，因为开放寻址将所有的关键字均存放在散列表中，因此我们必须保证散列表的大小始终大于原集合的元素规模，使得在任何时刻都能将元素存放在散列表中。但动态集合的插入操作有可能使得散列表被填满，这种情况下如果还需进行插入操作，那么我们就必须扩大散列表，由于散列表的大小m发生变化，考虑到m是散列函数中的参数，因此能保证m发生变化之后，同样一个关键字能被散列至相同的槽中，所以存放在原先散列表中的关键字必须被重新散列，这就带来了额外的开销。因此我们首先应充分挖掘待存储的数据的特点，比如作用在该集合上的操作是否在大多数情况下为搜索，而动态的插入/删除操作较少发生，或者是预留一个较大的散列表，能够保证原集合必定不超过该散列表的大小，在这之后才考虑使用开放寻址。
以下是链接法[除余散列，乘法散列，全域散列]和开放寻址[线性试探，二次试探，双重试探]的性能测试，由于所使用的数据集为随机生成数，因而可以预知对于链接法中的三种散列方法来说，散列之后的元素分布状况并不会存在多大差别，但开放寻址中的三种散列方法仍具有测试价值，这里我们一并进行测试：
#include <iostream>
#include <cmath>
#include <ctime>
#include <string>
#include <exception>
#include <Windows.h>
#include <engine.h>
using namespace std;
//#define __TEST__
#pragma warning(disable:4244)
#pragma warning(disable:4996)
#pragma warning(disable:4290)
const size_t KEY_SCALE = 600; //the number of keys in source set
const size_t SLOTS_IN_CHAIN = 45; //the number of slots in chained hash table
const size_t SLOTS_IN_OPENADDR = KEY_SCALE; /*in open addressing hash table*/
const size_t COUNT_OF_EXECUTE = 60; //counts of hash by open addressing
class MatDraw{
public:
MatDraw(const mwSize&);
~MatDraw()
{
mxDestroyArray(paForXOrder);
mxDestroyArray(paForYOrder);
engClose(ep);
}
void mdPlot(double **, const size_t&);
void EvalStr(string str)
{ engEvalString(ep, str.c_str()); }
private:
MatDraw(const MatDraw&);
MatDraw& operator=(const MatDraw&);
private:
Engine *ep;
mxArray *paForXOrder;
mxArray *paForYOrder;
size_t ArrLength;
};
class Hash{
public:
virtual void plot() = 0;
virtual void RunAndGetCollision() = 0;
Hash(const size_t&, const size_t&);
virtual ~Hash()
{ if(SrcSet) delete [] SrcSet; }
protected:
typedef size_t index;
void GeneRand(const size_t&);
size_t GeneFrom(size_t left, size_t right) const //generate random [left,right]
{ return (rand()%(right-left+1))+left; }
size_t getClosePrime() const;
void Exit() const { system("pause"); exit(0); }
size_t *SrcSet; //source set to be hashed
size_t szSet; //size of source set
size_t approSlot; //let user choose approximate Slot in hash table
size_t nSlot; //the size of hash table
protected:
/*this universal function provide service for chain
*hash & open address at the same time*/
index unihash(const size_t &key, const size_t &arg_a, const size_t &arg_b)
{
//hash(key)=(a*key+b) mod m -->a & b are random
return (arg_a*key+arg_b) % nSlot;
}
};
class chainHash : public Hash{
private:
typedef index (chainHash::*ChHsh)(const size_t&);
struct ChainNode{
size_t key;
ChainNode *next;
};
struct HashTable{
ChainNode *head;
size_t szCnt; //the number of node in chain
};
public:
typedef enum { REMAIN, MULTI, UNIVER } HashFunc;
chainHash(const size_t&, const size_t&);
~chainHash();
void getCorresIndex(const HashFunc&);
void IterEveryChain(const HashFunc &) const;
void InsertIntoHashTable(const HashFunc&);
void RunAndGetCollision();
void plot()
{
pmd->mdPlot(ColliMatrix,chainHash::NumOfHashF);
pmd->EvalStr(string("legend('remainder','multiplicate','univerhash');").c_str());
}
private:
chainHash(const chainHash&);
chainHash& operator=(const chainHash&);
/*three methods for chained hash*/
index remainder(const size_t &key) { return key%nSlot; }
index multiplicate(const size_t &key)
{
//hash(key) = floor(m*(A*key mod 1))
float A = (sqrt(5.0)-1)/2; //golden section ratio
float temp = A*key;
return (temp-static_cast<size_t>(temp))*nSlot;
}
index univerhash(const size_t &key)
{
//hash(key)=(a*key+b) mod m -->a & b are random
return unihash(key, a, b);
}
private:
//here store the argument for the 'univerhash' in a instance
size_t a, b;
private:
HashTable *pht; //dynamic allocate hash table
ChainNode *pcn; //allocate nodes in chain dynamically
static ChHsh hfTable[]; //function table
static size_t NumOfHashF;
double **ColliMatrix; //store the counts of Collision
class MatDraw *pmd; //picture pen
};
class openAddrHash : public Hash {
private:
typedef index (openAddrHash::*OAHashF)(const size_t&, const size_t&);
struct HashTable {
size_t szCnt;
bool IsNotEmpty;
};
public:
typedef enum { LINEAR, QUADRATIC, DBHASH} HashFunc;
openAddrHash(const size_t&, const size_t&);
~openAddrHash();
void plot()
{
pmd->EvalStr(string("figure;").c_str());
pmd->mdPlot(ColliMatrix, openAddrHash::NumOfHashF);
pmd->EvalStr(string("legend('linear','quadratic','doublehash');").c_str());
}
void RunAndGetCollision();
private:
/*three methods for Open Addressing -->hash' & hash'' are assist functions*/
/* hash(key, i)=(hash'(key)+i) mod m*/
index linearprob(const size_t &key, const size_t &ix)
{ return (unihash(key, arg[0], arg[1])+ix)%nSlot; }
/* hash(key, i)=(hash'(key)+c1*i+c2*i*i) mod m*/
index quadprob(const size_t &key, const size_t &ix)
{ return (unihash(key, arg[2], arg[3])+c1*ix+c2*ix*ix)%nSlot; }
/* hash(key, i)=(hash'(key)+i*hash''(key)) mod m*/
index dbhashprob(const size_t &key, const size_t &ix)
{ return (unihash(key, arg[4], arg[5])+ix*unihash(key, arg[6], arg[7]))%nSlot; }
void getCorresIndex(const HashFunc&) throw(exception);
void printInfo(const HashFunc&);
private:
//used in assist hash functions
/*in array 'arg' ---->
*arg[0]~arg[1] is used for linearprob
*arg[2]~arg[3] is used for quadprob
*arg[4]~arg[7] is for dbhashprob since it has two assist hash functions*/
#define ARG_IN_HASHFUNC 8
size_t arg[ARG_IN_HASHFUNC];
void GeneArg(const HashFunc&);
/*for quadprob*/
#define START 1
#define END 5
/*assist arguments ranged from [START, END] -- here can be changed*/
size_t c1, c2; /*extra arguments used in quadprob function*/
private:
HashTable *pht;
double **ColliMatrix; //total counts of collision
class MatDraw *pmd; //picture pen
static OAHashF hfTable[];
static size_t NumOfHashF;
};
chainHash::ChHsh chainHash::hfTable[] = {&chainHash::remainder,
&chainHash::multiplicate,
&chainHash::univerhash};
size_t chainHash::NumOfHashF = sizeof(chainHash::hfTable)/sizeof(chainHash::hfTable[0]);
openAddrHash::OAHashF openAddrHash::hfTable[] = {&openAddrHash::linearprob,
&openAddrHash::quadprob,
&openAddrHash::dbhashprob};
size_t openAddrHash::NumOfHashF = sizeof(openAddrHash::hfTable)/
sizeof(openAddrHash::hfTable[0]);
int main(int argc, char *argv[])
{
srand(static_cast<unsigned>(time(NULL)));
Hash *ph = new chainHash(KEY_SCALE,SLOTS_IN_CHAIN);
ph->RunAndGetCollision();
ph->plot();
delete ph;
ph = new openAddrHash(KEY_SCALE,SLOTS_IN_OPENADDR);
ph->RunAndGetCollision();
ph->plot();
delete ph;
system("pause");
return EXIT_SUCCESS;
}
Hash::Hash(const size_t &szKey, const size_t &slot) : szSet(szKey),
approSlot(slot),nSlot(getClosePrime())
{
if(!(SrcSet = new size_t[szSet]))
{
cout<<"Fail to Allocate Memory!"<<endl;
Exit();
}
GeneRand(szSet);
}
inline void Hash::GeneRand(const size_t &nSize)
{
for(size_t index = 0; index != nSize; index++)
SrcSet[index] = static_cast<size_t>(rand());
}
inline size_t Hash::getClosePrime() const
{
size_t start = approSlot;
for( ; ; )
{
size_t index = 2, bound = sqrt(static_cast<double>(start));
for(; index <= bound; index++ )
if(start%index == 0) break;
if(index > bound) break;
else ++start;
}
return start;
}
chainHash::chainHash(const size_t &nSize, const size_t &slot) : Hash(nSize, slot)
{
if( !(pht = new HashTable[nSlot]) ||
!(pcn = new ChainNode[nSize]) ||
!(ColliMatrix = new double*[chainHash::NumOfHashF]))
{
cout<<"Fail to Allocate Memory!"<<endl;
Exit();
}
if(!(pmd = new MatDraw(nSlot)))
{
cout<<"Fail to start initialize matlab engine!"<<endl;
Exit();
}
for(size_t index = 0; index != chainHash::NumOfHashF; index++)
{
ColliMatrix[index] = new double[nSlot];
if(!ColliMatrix[index]) {
cout<<"Fail to Allocate Memory!"<<endl;
Exit();
}
memset(ColliMatrix[index], 0, nSlot*sizeof(double));
}
a = GeneFrom(1,nSlot-1);
b = GeneFrom(0,nSlot-1);
memset(pht, 0, nSlot*sizeof(HashTable));
memset(pcn, 0, nSize*sizeof(ChainNode));
for(size_t index = 0; index != szSet; index++)
pcn[index].key = SrcSet[index];
}
chainHash::~chainHash()
{
if(pht) delete [] pht;
if(pcn) delete [] pcn;
if(pmd) delete pmd;
for(size_t index = 0; index != chainHash::NumOfHashF; index++)
delete [] ColliMatrix[index];
delete [] ColliMatrix;
}
void chainHash::getCorresIndex(const HashFunc &hf)
{
#ifdef __TEST__
ChHsh phf = hfTable[hf];
for(size_t iter = 0; iter != szSet; iter++)
cout<<SrcSet[iter]<<' '<<(this->*phf)(SrcSet[iter])<<endl;
cout<<endl;
#endif
}
void chainHash::InsertIntoHashTable(const HashFunc &hf)
{
ChHsh phf = hfTable[hf];
size_t szLabel;
for(size_t index = 0; index != szSet; index++)
{
szLabel = (this->*phf)(pcn[index].key);
pcn[index].next = pht[szLabel].head;
pht[szLabel].head = &pcn[index];
++pht[szLabel].szCnt;
}
}
void chainHash::IterEveryChain(const HashFunc &hf) const
{
#ifdef __TEST__
if(hf == chainHash::REMAIN)
cout<<"Iterate the chain hashed by <remainder>"<<endl;
else if(hf == chainHash::MULTI)
cout<<"Iterate the chain hashed by <multiplicate>"<<endl;
else if(hf == chainHash::UNIVER)
cout<<"Iterate the chain hashed by <univerhash>"<<endl;
else {
cout<<"Wrong : Iterate the chain hashed by NULL function"<<endl;
Exit();
}
#endif
for(size_t index = 0; index != nSlot; index++)
{
size_t szCnt = pht[index].szCnt;
*(ColliMatrix[static_cast<size_t>(hf)]+index) = szCnt;
#ifdef __TEST__
cout<<"the number of nodes in the chain : "<<szCnt
<<'\t'<<"the node :";
for(ChainNode *p=pht[index].head; p != NULL; p = p->next)
cout<<p->key<<"-->";
cout<<endl;
#endif
}
}
void chainHash::RunAndGetCollision()
{
size_t limit = sizeof(chainHash::hfTable)/sizeof(chainHash::hfTable[0]);
for(size_t index = 0; index != limit; ++index)
{
getCorresIndex(static_cast<HashFunc>(index));
InsertIntoHashTable(static_cast<HashFunc>(index));
IterEveryChain(static_cast<HashFunc>(index));
memset(pht, 0, nSlot*sizeof(HashTable));
for(size_t ix = 0; ix != szSet; ix++)
pcn[ix].next = NULL;
#ifdef __TEST__
for(size_t ix = 0; ix !=nSlot; ix++)
cout<<*(ColliMatrix[index]+ix)<<' ';
cout<<endl<<endl;
#endif
}
}
void openAddrHash::GeneArg(const HashFunc &hf)
{
size_t start, end;
switch(hf) {
case openAddrHash::LINEAR:
start = 0; end = 1+1; break;
case openAddrHash::QUADRATIC:
start = 2; end = 3+1; break;
case openAddrHash::DBHASH:
start = 4; end = 7+1; break;
default:
cout<<"Wrong : No existing hash function !"<<endl;
Exit();
}
for(size_t index = start; index != end; index += 2)
{
arg[index] = GeneFrom(1, nSlot-1);
arg[index+1] = GeneFrom(0, nSlot-1);
}
}
openAddrHash::openAddrHash(const size_t &nSize, const size_t &slot) : Hash(nSize, slot)
{
if(!(pht = new HashTable[nSlot]) ||
!(ColliMatrix = new double*[openAddrHash::NumOfHashF]) )
{
cout<<"Fail to Allocate Memory!"<<endl;
Exit();
}
if(!(pmd = new MatDraw(COUNT_OF_EXECUTE)))
{
cout<<"Fail to start initialize matlab engine!"<<endl;
Exit();
}
for(size_t index = 0; index != openAddrHash::NumOfHashF; index++)
{
if(!(ColliMatrix[index] = new double[COUNT_OF_EXECUTE]))
{
cout<<"Fail to Allcate Memory!"<<endl;
Exit();
}
memset(ColliMatrix[index], 0, COUNT_OF_EXECUTE*sizeof(double));
}
memset(pht, 0, nSlot*sizeof(HashTable));
for(size_t index = 0; index != openAddrHash::NumOfHashF; index++)
GeneArg(static_cast<HashFunc>(index));
c1 = GeneFrom(START, END);
c2 = GeneFrom(START, END);
}
openAddrHash::~openAddrHash()
{
if(pht) delete [] pht;
if(pmd) delete pmd;
for(size_t index = 0; index != openAddrHash::NumOfHashF; index++)
delete [] ColliMatrix[index];
delete [] ColliMatrix;
}
void openAddrHash::getCorresIndex(const HashFunc &hf) throw(exception)
{
#ifdef __TEST__
printInfo(hf);
#endif
OAHashF pOpenAddrHf = hfTable[hf];
size_t szLabel, ix;
for(size_t index = 0; index != szSet; index++)
{
for(ix = 0; ix != nSlot; ix++)
{
szLabel = (this->*pOpenAddrHf)(SrcSet[index], ix);
++pht[szLabel].szCnt;
#ifdef __TEST__
cout<<SrcSet[index]<<'\t'<<szLabel<<endl;
#endif
if(!pht[szLabel].IsNotEmpty) {
pht[szLabel].IsNotEmpty = true;
break;
}
}
if(ix == nSlot)
throw exception("hash Failure, restart ...\n");
}
#ifdef __TEST__
for(size_t index = 0; index != nSlot; index++)
cout<<"Slot : "<<index<<"\tCounts of Collision : "<<pht[index].szCnt<<endl;
#endif
}
void openAddrHash::RunAndGetCollision()
{
size_t totalCollision, totalKeyInHashTable;
for(size_t index = 0; index != COUNT_OF_EXECUTE; index++)
{
for(size_t ix = 0; ix != openAddrHash::NumOfHashF; ix++)
{
try{
memset(pht, 0, nSlot*sizeof(HashTable));
totalCollision = totalKeyInHashTable = 0;
getCorresIndex(static_cast<HashFunc>(ix));
for(size_t j = 0; j != nSlot; j++)
totalCollision += pht[j].szCnt;
} catch(exception &e) {
cout<<e.what();
GeneArg(static_cast<HashFunc>(ix));
--ix; continue;
}
ColliMatrix[ix][index] = totalCollision;
}
cout<<index<<" test has been finished!"<<endl;
GeneRand(szSet); //Regenerate source set & continue to test
}
#ifdef __TEST__
for(size_t index = 0; index != openAddrHash::NumOfHashF; index++)
{
for(size_t ix = 0; ix != COUNT_OF_EXECUTE; ix++)
cout<<ColliMatrix[index][ix]<<' ';
cout<<endl;
}
#endif
}
void openAddrHash::printInfo(const HashFunc &hf)
{
cout<<"hash' & hash'' assist hash function --->"
" (a*key+b) mod m, here m="<<nSlot<<endl;
switch(hf) {
case openAddrHash::LINEAR:
cout<<"Linear Probing : \n"<<"a1="<<arg[0]<<"\tb1="<<arg[1]<<'\n';
cout<<"hash(key,i)=(hash'(key)+i) mod m"<<endl;
break;
case openAddrHash::QUADRATIC:
cout<<"Quadratic Probing : \n"<<"a1="<<arg[2]<<"\tb1="<<arg[3]<<'\n';
cout<<"c1="<<c1<<"\tc2="<<c2<<'\n';
cout<<"hash(key,i)=(hash'(key)+c1*i+c2*i*i) mod m"<<endl;
break;
case openAddrHash::DBHASH:
cout<<"DoubleHash Probing : \n"<<"a1="<<arg[4]<<"\tb1="<<arg[5]<<'\n';
cout<<"a2="<<arg[6]<<"\tb2="<<arg[7]<<'\n';
cout<<"hash(key,i)=(hash'(key)+i*hash''(key)) mod m"<<endl;
break;
default:
cout<<"Wrong : There has no More Hash Function!"<<endl;
Exit();
}
}
MatDraw::MatDraw(const mwSize &n_Length) : ArrLength(n_Length)
{
double * InitForXOrder = new double[n_Length];
/*start matlab engine*/
if(!(ep = engOpen(NULL))) {
cout<<"Fail to start Matlab!"<<endl;
exit(0);
}
engSetVisible(ep, false); /*hide the main window*/
/*create maxtrix as a variable*/
if(!(paForXOrder = mxCreateDoubleMatrix(1, n_Length, mxREAL)) ||
!(paForYOrder = mxCreateDoubleMatrix(1, n_Length, mxREAL)))
{
cout<<"Fail to create matrix!"<<endl;
exit(0);
}
for(size_t index = 0; index != n_Length; index++)
InitForXOrder[index] = index;
/*copy InitForXOrder to mxArrary*/
memmove(mxGetPr(paForXOrder), InitForXOrder, ArrLength*sizeof(double));
/*write mxArray into matlab workerspace*/
engPutVariable(ep, "paForXOrder", paForXOrder);
delete InitForXOrder;
}
/*RowsOfMatrix from [0,8)*/
void MatDraw::mdPlot(double **pd, const size_t &RowsOfMatrix)
{
char temp[1024];
string EvalStr("title('collision statistics');"), colStr("rgbykmc");
sprintf(temp, "xlabel('x=[0 : %d]');", ArrLength);
EvalStr += string(temp);
EvalStr += string("ylabel('the count ofs collision');");
EvalStr += string("hold on;");
for(size_t index = 0; index != RowsOfMatrix; index++)
{
memmove(mxGetPr(paForYOrder), pd[index],
ArrLength*sizeof(double));
engPutVariable(ep, "paForYOrder", paForYOrder);
EvalStr += string("plot(paForXOrder,paForYOrder,\'")
+colStr[index]+string("*-\');");
engEvalString(ep, EvalStr.c_str());
EvalStr.clear();
}
}
上述测试不再生成matlab脚本，而是直接在vc中调用其函数库，因此需要进行如下设置（VS2010）：
- 右击解决方案 --> 打开属性窗口 --> 点击"VC++目录"选项卡。
- 在“包含目录”选项中添加头文件目录，如“d:\Program Files\MATLAB\R2009a\extern\include;”。
- 在“库目录”中添加库文件目录，如”d:\Program Files\MATLAB\R2009a\extern\lib\win32\microsoft;“。
- 最后选中”链接器“ --> "输入"选项卡，在”附加依赖项“中添加添加如下库"libeng.lib;libmx.lib;libmex.lib;"。
上述最后一步也可以换成在源代码中添加预处理指令，格式如#pragma comment(lib,"libeng.lib")，将上述三个库显式命令链接器加载。
与测试用例相关的配置介绍完了，我们最后简单分析执行所得结果：
在我们的测试用例中，测试函数散列状况的方法是将同一个待散列集合中的每一个元素根据某个散列函数得到与其对应的槽，并将所有元素以链表的形式链接在该槽中，最终统计各个槽中存储的元素个数用来表示碰撞的次数。可以发现，集合被除余散列，乘法散列以及全域散列作用之后的散列状况大致相同，这是因为在我们的测试中，使用的待散列元素为随机生成数。这里不再精确计算每个散列函数下的碰撞次数的方差，因为如果重新生成新的随机散列集合，方差也将随之改变，因此在随机生成的集合下判定到底哪个函数的散列性能较好没有意义，一个重要的原则是首先分析待散列的集合具有什么样的特点，之后再具体选择有针对性的散列函数。
上述执行结果为开放寻址下的三种函数的散列性能，测试所用的方法是为每个槽设置一个计数值，并且元素在探查到某个空槽之前将探查序列中的每个槽所对应的计数值均自增1（包括该空槽），最终统计槽被该散列集合中的元素碰撞的总次数，以此表示该散列函数性能，之后多次重新生成随机数的集合进行测试。我们开放寻址下的三种函数中，线性试探法的散列性能最差，而二次试探与双重散列的性能相当，这是因为线性试探法中存在严重的群集现象。
后记
散列表这种数据结构仅仅只是散列函数一个较为简单的应用。试想一下散列函数将输入映射为某个输出，既然可以将该输出解释为所要寻址的槽，那么自然也可以具有其他的解释，一个具有重大意义的应用领域即为密码学。这里简单提一下王小云教授对MD5所采用的破解方式，准确来说她所采用的方法不叫破解，而是构造了一种能够快速产生碰撞的方法，即给出一个p1，通过该方法可以很快算出一个不等于p1的p2使得
MD5(p1)=MD5(p2)，根据这一点就足以把MD5枪毙掉了。这种方法并不意味着能根据MD5的Hash函数反算出明文来，亦即这是一种单向加密函数——不存在逆函数可以将密文重新变为明文。最后要提的一点是，现有的加密方式也就那么几种，并且数据/字符所组合而成的输入也是有限的，那么自然可以通过穷举所有输入，并且根据现有的散列函数预先计算出所有的输出用以加速破解，详细见彩虹表。