数据结构面试之十三——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（更易于编写，效率不错）
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]散列表的装填因子。
散列表的装填因子定义为：α=填入表中的元素个数 /散列表的长度。
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，
u α越大，填入表中的元素较多，产生冲突的可能性就越大；
u α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
5.简单的Hash表实现
template <typename _Type>
class HashTable
{
public:
HashTable(int Length)
{
Element = new _Type[Length];
for(int i=0;i<Length;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(_Type Data,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))
{
return Index;
}
else
{
return -1;
}
}
// 插入元素
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<Length;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<Length;i++)
{ Element[i] = -1;
}
Count = 0;
}
void Print()
{
for(int i=0;i<Length;i++)
{
printf("%d",Element[i]);
}
printf("\n");
}
protected:
_Type* Element; // Hash表
int Length; // Hash表大小
int Count; // Hash表当前大小
};
void main()
{
HashTable<int> H(10);
printf("Hash Length(10)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 j=0; j<6; j++)
{
printf("%d\n",H.InsertHash(Array[j]));
}
H.Print();
printf("Find(97):%d\n",H.SerachHash(97));
printf("Find(49):%d\n",H.SerachHash(49));
system("pause");
}
