2011年软考程序员考点：Hash表(散列表)

欢迎大家继续浏览本系列文章，在本章为各位备考软件水平考试的同窗提供《2011年软考程序员常考考点：Hash表(散列表)》，下列是本章详细内容：

Hash表(散列表)

(1)基本概念

若结构中存在症结字和K相等的记录，则一定在f(K)的存储位置上。由此，不需对比便可直接获得所查记录。称这个对应瓜葛f为散列函数(Hash function)，按这个思想树立的表为散列表。

对不同的症结字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这类现象称冲突。拥有相同函数值的症结字对该散列函数来讲称做同义词。综上所述，依据散列函数H(key)和处理冲突的法子将一组症结字映象到一个有限的连续的地址集(区间)上，并以症结字在地址集中的“象”作为记录在表中的存储位置，这类表便称为散列表，这一映象进程称为散列造表或散列，所得的存储位置称散列地址。

若对症结字聚拢中的任一个症结字，经散列函数映象到地址聚拢中任何一个地址的几率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使症结字经由散列函数得到一个“随机的地址”，从而减少冲突。

(2)经常使用的构造散列函数的法子

散列函数能使对一个数据序列的走访进程更为迅速有效，通过散列函数，数据元素将被更快地定位。

[1]直接定址法：取症结字或症结字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数(这类散列函数叫做本身函数)

[2]数字分析法： 一般取一些大一点的素数，效果更好点。

[3]平方取中法:计算症结值再取中间r位构成一个2^r位的表[4]折叠法:把所有字符的ASCII码加起来 (对字符串)

[5]随机数法：选择一个随机函数，取症结字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常症结字长度不等时采取此法构造哈希函数较恰当。

[6]除留余数法：取症结字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不但可以对症结字直接取模，也可在折叠、平方取中等运算以后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易发生同义词。

[7]针对字符串的一些经常使用法子，譬如ELFHash和BKDRHash(更容易于编写，效力不错)
（2011年软考程序员常考考点）
 [NextPage]

(3)处理冲突的法子

[1]开放定址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有以下三种

取法：

di=1,2,3,…, m-1，称线性探测再散列;

di=1^2, -1^2, 2^2,-2^2,3^2, …, ±k^2,(k<=m/2)称二次探测再散列;

di=伪随机数序列，称伪随机探测再散列。

[2]再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词发生地址冲突时计算另外一个散列函数地址，直到冲突再也不产生，这类法子不容易发生“汇集”，但增添了计算时间。

[3]链地址法(拉链法)

[4]树立一个公共溢出区
(4)查找的机能分析

散列表的查找进程基本上和造表进程相同。一些枢纽码可通过散列函数转换的地址直接找到，另外一些枢纽码在散列函数得到的地址上发生了冲突，需要按处理冲突的法子进行查找。在介绍的三种处理冲突的法子中，发生冲突后的查找依然是给定值与症结码进行对比的进程。所以，对散列表查找效力的量度，仍然用平均查找长度来衡量。

查找进程中，症结码的对比次数，取决于发生冲突的多少，发生的冲突少，查找效力就高，发生的冲突多，查找效力就低。因而，影响发生冲突多少的因素，也就是影响查找效力的因素。影响发生冲突多少有下列三个因素：

[1]散列函数是不是均匀;

[2]处理冲突的法子;

[3]散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。因为表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，发生冲突的可能性就越大;α越小，填入表中的元素较少，发生冲突的可能性就越小。

实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的法子有不同的函数。
（2011年软考程序员常考考点）
 [NextPage]

//简单的Hash表实现

#include

template

class HashTable

{

public:

HashTable(int Length)

{

Element = new _Type[Length];

for(int i=0;i

Element[i] = -1;

this->Length = Length;

Count = 0;

}

~HashTable()

{

delete[] Element;

}

// Hash函数

virtual int Hash(_Type Data)

{

return Data % Length;

}

// 再散列法

virtual int ReHash(int Index,int Count)

{

return (Index + Count) % Length;

}

// 查找某个元素是不是在表中

virtual bool SerachHash(_TypeData,int& Index)

{

Index = Hash(Data);

int Count = 0;

while(Element[Index] != -1 &&Element[Index] != Data)

Index = ReHash(Index,++Count);

return Data == Element[Index] ? true :false;

}

virtual int SerachHash(_Type Data)

{

int Index = 0;

if(SerachHash(Data,Index)) returnIndex;

else return -1;

}
（2011年软考程序员常考考点）
 [NextPage]

// 插入元素

bool InsertHash(_Type Data)

{

int Index = 0;

if(Count < Length &&!SerachHash(Data,Index))

{

Element[Index] = Data;

Count++;

return true;

}

return false;

}

// 设置Hash表长度

void SetLength(int Length)

{

delete[] Element;

Element = new _Type[Length];

for(int i=0;i

Element[i] = -1;

this->Length = Length;

}

// 删除某个元素

void Remove(_Type Data)

{

int Index = SerachHash(Data);

if(Index != -1)

{

Element[Index] = -1;

Count--;

}

}

// 删除所有元素

void RemoveAll()

{

for(int i=0;i

Element[i] = -1;

Count = 0;

}

void Print()

{

for(int i=0;i

printf("%d",Element[i]);

printf("\n");

}

protected:

_Type* Element; // Hash表

int Length; // Hash表大小

int Count; // Hash表当前大小

};
（2011年软考程序员常考考点）
 [NextPage]

void main()

{

HashTable H(十);

printf("Hash Length(十)Test:\n");

int Array[6] = {49,38,65,97,13,49};

for(int i=0;i<6;i++)

printf("%d\n",H.InsertHash(Array[i]));

H.Print();

printf("Find(97):%d\n",H.SerachHash(97));

printf("Find(49):%d\n",H.SerachHash(49));

H.RemoveAll();

H.SetLength(30);

printf("Hash Length(30)Test:\n");

for(int i=0;i<6;i++)

printf("%d\n",H.InsertHash(Array[i]));

H.Print();

printf("Find(97):%d\n",H.SerachHash(97));

printf("Find(49):%d\n",H.SerachHash(49));

system("pause");

}

以上就是考试百科的小编为大家提供的《2011年软考程序员常考考点：Hash表(散列表)》的全体内容，更多关于软件水平考试相干资讯请您继续关注考试百科的小编。

*******************************************************************

【友谊举荐】:2011年软考程序员常考考点

【友谊举荐】:2011年软考程序员辅导摹拟试题汇总

【友谊举荐】:软考程序员jQuery辅导：15天学会jQuery

更多相干内容请登录闪讯IT考试网：http://pc.kaoshibaike.com