文章目录
前言
好久没更新了，最近接近结课，很多报告、考试让人应接不暇，刚刚忙完其他的就来更新这个内容了。这一章描述的是散列的应用。
这一章出自于《Data Structures and Algorithm Analysis in C》的第五章，但是其在描述（或翻译）的时候有些抽象，这一篇还结合了《大话数据结构》中的描述。
散列表
我们之前有学过线性表（数组实现）、链表（和栈、队列等）、BST（二叉搜索树）以及堆这些数据结构，它们具有不同的特点，并都可以对一组元素进行各种操作。其中，我们寻找一个元素的基本思路一般都是：从表头开始，表中每一位数据与要找的数据进行比较，相等时返回。如果是有序表，则可以利用大小关系比较，二分查找返回。为了查找到结果，”比较”都是不可避免的，导致这一过程的时间复杂度至少为O(logN)（二叉查找），一般为O(N)。
散列(Hashing)是一种用于以常数平均时间（O(1)）执行插入、删除和查找的技术。它可以关键字key直接得到要查找的记录内存存储位置。散列的出现，解决了传统查找、插入和删除从头开始查找，逐位比较的问题。
解释散列的原理，我们从一个生活中的例子入手。
你有一个朋友的小名叫阿强，老师点名的时候对照名字表，表中只有阿强的本名，老师找人的过程就是普通的查找过程，依赖的是姓名关键字的比较。而有另外一个朋友，他问你阿强在哪里，你就带他去找阿强，并告诉他那个人的外号叫阿强。另外一个朋友找阿强的时候，没有遍历名字表，没有比较是不是阿强，只凭“我”对阿强别名的记忆，直接找到了阿强，这样的过程就是散列实现的过程。
如果把这个过程放到数学中，那此时存在某种函数F的映射关系，使得：
存储位置＝F (关键字)
于是这样我们可以通过查找关键字，而不需要比较就可获得需要的记录的存储位置。我们这样的函数F称为散列函数（Hashing function）。散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系F的存储技术。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表(Hash table)。
理想情况下，我们希望散列表中每个不同的关键字都映射到不同的单元，或称为槽（slot）上，如下左图。
但并不是所有情况都是理想的，我们时常会遇到几个关键字，例如key1 ≠ key2, 但是却有F(key1) = F(key2)，这种现象我们称为冲突(collision)，如上图右。处理冲突也将是我们处理散列时的一大难点。
我们知道“阿强”这个外号与别人无关，即散列技术的记录之间不存在什么逻辑关系，它只与关键字有关。因此，散列主要是面向查找的存储结构，适合查找与给定值相等的记录。但又因为它数据之间除了关键字外没有必然联系，散列技术不具备很多常规数据结构的能力，例如范围查找、多对一查找、找到最大最小等操作均不适合使用散列实现。
说了这么多，我们知道散列在于通过关键字查找数据，其中这个过程依靠的是散列函数，也是设计散列函数就是使用散列技术的重点。
散列函数
我们首先按照理想情况设计，即一个关键字只对应一个地址。我们在设计时一般遵循以下原则：
- 计算简单
- 分布均匀
其中对于数据为10进制整数的情况，我们最常用的就是MOD法。首先我们设散列表的长度为Tablesize，关键字为key。此时设计散列函数的思路就是 f(key)=key mod Tablesize这样的函数基于基数排列，只执行一次除法取余数操作就能找到在散列表中的地址。它满足了计算简单，并且可以根据mod的大小做到尽可能均匀分布。
很显然，本方法的关键就在于选择合适的Tablesize, Tablesize如果选得不好，就可能会容易产生冲突。
那么我们可以很容易想到一些不能设置的值，例如：10的幂（因为很多数mod10的幂会得到相同的值）、比较小的数（因为mod比较小的数很有可能产生重复结果）等等。
所以根据大量的总结，我们一般把Tablesize设置为一个质数。例如我们选取Tablesize为11，如下一组数据.
质数的Tablesize容易得到理想散列表的情况，而避免冲突。
但是如果我们多加一个关键字144,144%11=1，与关键字12冲突，如下图。此时我们就需要使用一些操作处理冲突了。
冲突处理
从刚才的例子也可以看出，我们设计得再好的散列函数也不可能完全避免冲突。既然冲突不能避免，就要考虑如何处理它。
两个关键字key1 ≠ key2, 但是却有F(key1) = F(key2)，这个是一个简单的冲突情况。对于这样的冲突，我们一般有三种方法去解决——分离链接法、开放定址法和再散列。
分离链接法（Separate Chaining）
分离链接法，其做法是将散列到同一个值的所有元素保存到一个单链表中，在散列表中只存储所有链表的头指针。说起来很容易，我们来看看怎么实现。
首先我们定义这个散列表，它是一个数组，里面存的是各个基数单链表的头指针，故它是一个二重指针。
typedef int ElementType;
typedef struct ListNode //单向链表
{
ElementType Element;
struct ListNode* Next;
}*List;
typedef struct HashTbl
{
int TableSize;
List *TheLists; //存储链表头指针的数组
}*HashTable;接下来就是我们的散列函数，它只需要执行key mod Tablesize，故非常简单。
int Hash(ElementType key, int tablesize)
{
return key % tablesize;
}接下来我们对新建的散列表进行初始化。我们生成tablesize的时候要满足：质数且大于等于数据数，这样可以保证少出现冲突，故我们需要寻找大于等于数据数的最小质数作为我们的tablesize。
HashTable InitializeTable(int TableSize)
{
int size=TableSize;
/*求大于等于Tablesize的最小质数*/
if(size>3) //若1<size<3，均为质数
{
for(int i=3;i<=(int)sqrt((double)size);) //若有约数，较小的约数比小于sqrt(size)
{
if(size % 2 == 0 || size % i == 0) //不是质数
{
size++; //一般合数下一位为质数，故这里加1；若不是下一次还会再加1。
i=3; //初始化i，重新判断是不是质数
continue; //初次的i跳过递加部分
}
i+=2;
}
}
/*建散列表*/
H->TheLists=(List *)malloc(sizeof(List) * size);
if(H->TheLists == NULL)
{
printf("Out of space!\n");
exit(-1);
}
/*建单向链表*/
for(int i=0;i<size;i++) { H->TheLists[i]=(List)malloc(sizeof(struct ListNode));
if(H->TheLists[i] == NULL)
{
printf("Out of space!\n");
exit(-1);
}
H->TheLists[i]->Next=NULL; //TheLists[i]此时为表头哑节点，初始化为NULL
}
return H;
}其中第一部分求大于等于Tablesize的最小质数时，这里采用了优化的思路。首先是若1<size<3，均为质数；其次，若一个数是合数，它一定是两个约数相乘，它们之间存在：一个大于等于√(n)，另一个小于等于√(n)的关系。故我们只需要找到其小的约数就行了，循环到√n就能知道是不是质数。
这里还有一个思路，即任一偶数均能分解为2和其他数的积，故一个数不能被2整除，那么这个数一定不能被其他偶数整除。所以我从3开始循环，每次都是比较奇数就可以了，在比较时额外判断是否能被2整除就可以知道能不能跳过偶数了。
其他的部分就是普通的新建过程，因为使用了单链表的头指针作为数组元素，初始化时要把这些头指针置为NULL。
接下来就是我们的查找操作了，调用我们的散列函数去查找：
List Find(ElementType Key, HashTable H)
{
int pos=Hash(Key,H->TableSize); //找到基数
List p=H->TheLists[pos]; //找到所在基数链表的头指针
while(!p && p->Element != Key) //找到关键字
p=p->Next;
return p;
}当然我们添加元素入表还需要插入操作：
void Insert( ElementType Key, HashTable H )
{
if(!Find(Key,H))
{
List P=(List)malloc(sizeof(struct ListNode));
if(P == NULL)
{
printf("Out of space!\n");
exit(-1);
}
List L=H->TheLists[Hash(Key,H->TableSize)];
P->Next=L->Next;
P->Element=Key;
L->Next=P; //往链表前端插入
}
}当然，插入后还有删除操作。在这里没有使用Find函数是因为我们删除的同时要连接前后结点，需要找到前一个结点，直接使用Find会使我们找到前节点的过程复杂。
void Delete(ElementType Key, HashTable H)
{
int pos=Hash(Key,H->TableSize); //找到基数
List L=H->TheLists[pos]; //找到所在基数链表的头指针
while(!L->Next && L->Next->Element != Key) //找到关键字的前一个结点L
L=L->Next;
if(L->Next == NULL) //关键字不存在
{
printf("No Found.\n");
return;
}
else //删除关键字
{
List p=L->Next;
L->Next=p->Next;
free(p);
}
}最后是销毁这个散列表：
void DestroyTable( HashTable H )
{
for(int i=0;iTableSize;i++) //逐个删除各个链表
{
List p=H->TheLists[i];
while(!p)
{
List t=p->Next;
free(p);
p=t;
}
}
free( H->TheLists );
free( H );
}以上就是我们的分离链接法的实现。它对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。
开放定址法（Open Addressing）
我们从一个生活中的例子入手理解开放定址法。当你在找房子时，重要选中一套心仪的房子，准备付定金的时候中介告诉你房子已经被别人买了，这个时候你该怎么做？当然是再找另外一套，这样的思想便是开放定址法。
开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
对于开放定址法，它的散列函数可以有如下规律：
fx(key)=(f(key)+F(i))mod Tablesize 其中i{0,1,2,...,Tablesize-1}
线性探测法
比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34} ，表长为12 。我们用散列函数f (key) =key mod 12 。
当计算前5 个数{12,67,56,16,25} 时，都是没有冲突的散列地址，直接存入。（已占位置0,1,4,7,8）
计算key=37 时，发现f (37) =1, 此时就与25 所在的位置冲突。即此时可以理解为这间房子被买了，我去买下一间，即我们把它放入位置2，如图：
接下来22,29,15,47 都没有冲突，正常的存入。（它们占了的位置为3,5,10,11）
到了key=48, 我们计算得到f (48) = 0, 与12 所在的 0 位置冲突了，我们像之前的操作一样，去下一个位置。然后发现下一个位置1,2,3,4,5都满了，那就一直往后找到了位置6，存下此时的48.
我们把这种解决冲突的开放定址法称为线性探测法。它的公式中，F(i)=i，可以写作：
f1(key)=(f(key)+Di)mod Tablesize 其中Di{0,1,2,...,Tablesize-1}
但我们发现，我们在解决冲突的时候，还会碰到如48 和37 这种本来不是同一基数，却需要争夺一个地址的情况，我们称这种现象为聚集。聚集的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。
因此针对这种情况，我们可以通过平方探测法或双散列来优化。
平方探测法
平方探测是消除线性探测中一次聚集问题的冲突解决方法。一般公式中，F(i)=i2.
增加平方运算的目的是为了不让关键字都聚集在某一块区域，可以概率减少聚集。但此时一旦表被填满超过一半，当表的大小不是素数时甚至在表被填满一半之前，就不能保证一次找到一个空单元了。这种方法也有待改进。
平方探测法的缺点也很明显，于是便出现了双散列，花费另外的一些乘法和除法更加高效解决聚集的问题。
双散列
双散列即使用两个散列函数 hash1(key)，hash2(key). 先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，直到找到空闲的存储位置。
此时的公式为：
f(key)=(hash1(Key) + i * hash2(Key)) mod Tablesize
这个公式说明，我们先通过hash1函数判断位置，然后再将第二个散列函数应用到Key，并在距离1*hash2(Key), 2*hash2(Key) ......处探测。
于是此时hash2函数的选择就非常关键，通常这个函数需要与hash1不同、不能计算出0值，且保证所有的单元都能被探测到，我们一般取hash2(Key) = R - (Key mod R)，其中R 为小于TableSize 的质数。
通过模拟，预期的探测次数几乎和随机冲突解决方法的情形相同。
我们通过一个例子来实现双散列。
设H(k) = k mod 10为初始的散列函数，其中k为关键字。还有一个散列函数G(k) = 7 – (k mod 7) 。其中有6个关键字需要插入{89, 18, 49, 58, 69}
我们列一个表：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| After 89 | ||||||||||
| After 18 | ||||||||||
| After 49 | ||||||||||
| After 58 | ||||||||||
| After 69 |
- 插入89，H(89)=9，把89插入位置9；
- 插入18，H(18)=8，把18插入位置8；
- 插入49，H(49)=9 产生冲突，使用双散列，G(49)=7-(49%7)=7，Hi(49) = (H(49) + 1*G(49))%10 = 16%10 = 6，把49插入到位置6；
- 插入58，H(58)=8 产生冲突，使用双散列，G(58)=7-(58%7)=5，Hi(58) = (H(58) + 1*G(58))%10 = 13%10 = 3，把58插入到位置3；
- 插入69，H(69)=9 产生冲突，使用双散列，G(69)=7-(69%7)=1，Hi(49) = (H(69) + 1*G(69))%10 = 10%10 = 0，把69插入到位置0.
故这样操作后，我们得到的表格就是这样的：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| After 89 | 89 | |||||||||
| After 18 | 18 | 89 | ||||||||
| After 49 | 49 | 18 | 89 | |||||||
| After 58 | 58 | 49 | 18 | 89 | ||||||
| After 69 | 69 | 58 | 49 | 18 | 89 |
那我们在程序中又会怎么实现它呢？
首先在定义散列表的时候，我们不需要使用链表，只使用数组就可以了。
因为此时我们散列函数的通式为：
f(key)=(hash1(Key) + i * hash2(Key)) mod Tablesize
我们应该自己定义一个结构同时存储数据与i的值，这里使用了HashEntry，里面记录着数据与状态。
typedef int ElementType;
enum KindOfEntry { Legitimate, Empty };
//标记当前位置的状态，Legitimate说明被占用，Empty则是空
struct HashEntry
{
ElementType Element;
enum KindOfEntry Info;
};
typedef struct HashEntry Cell;
struct HashTbl
{
int TableSize;
Cell *TheCells;
};
typedef struct HashTbl *HashTable;对于初始化部分，和之前的分离链接法差不多，只是不需要建立链表而已。
HashTable InitializeTable(int TableSize)
{
int size=TableSize;
/*求大于等于Tablesize的最小质数*/
if(size>3) //若1<size<3，均为质数
{
for(int i=3;i<=(int)sqrt((double)size);) //若有约数，较小的约数比小于sqrt(size)
{
if(size % 2 == 0 || size % i == 0) //不是质数
{
size++; //一般合数下一位为质数，故这里加1；若不是下一次还会再加1。
i=3; //初始化i，重新判断是不是质数
continue; //初次的i跳过递加部分
}
i+=2;
}
}
/*建散列表*/
HashTable H=(HashTable)malloc(sizeof(struct HashTbl));
if(H == NULL)
{
printf("Out of space!\n");
exit(-1);
}
H->TableSize=size;
H->TheCells=(Cell *)malloc(sizeof(Cell) * size);
if(H->TheCells == NULL)
{
printf("Out of space!\n");
exit(-1);
}
for(int i=0;i<size;i++) {
H->TheCells->Info=Empty;
}
return H;
}接下来就是两个散列函数了，这两个散列函数的部分一个和原来相同hash1(Key) = key mod Tablesize，另一个则是hash2(Key) = R - (Key mod R) R为小于Tablesize的最大质数。
int Hash1(ElementType Key, int TableSize)
{
return Key % TableSize;
}
int Hash2(ElementType Key, int TableSize)
{
int R=TableSize;
if(R<=3) //小于等于3时，质数2、3是连在一起的，此时-1即可
{
R--;
return R-(Key%R);
}
else //找到R，是比tablesize小的最大质数
{
R-=2; //质数之间除了2、3外不存在相邻的
for(int i=3;i<=(int)sqrt((double)R);) //若有约数，较小的约数比小于sqrt(size)
{
if(R % 2 == 0 || R % i == 0) //R不是质数
{
R-=2;
i=3;
continue;
}
i+=2;
}
return R-(Key%R);
}
}接下来到了查找操作，这个时候我们需要配合这个公式f(key)=(hash1(Key) + i * hash2(Key)) mod Tablesize编写。
int Find(ElementType Key, HashTable H)
{
int pos1,pos2,pos;
pos1=Hash1(Key,H->TableSize);
pos=pos1;
for(int i=0;H->TheCells[pos].Info != Empty && H->TheCells[pos].Element != Key;i++)
{
//i从0开始，判断新位置
pos2=Hash2(Key,H->TableSize);
pos=(pos1+i*pos2)%H->TableSize;
}
return pos;
}至于插入操作就更简单了，找到位置就插入：
void insert(ElementType Key, HashTable H)
{
int pos;
pos=Find(Key,H);
if( H->TheCells[pos].Info != Legitimate)
{
H->TheCells[pos].Info = Legitimate;
H->TheCells[pos].Element = Key;
}
}如果是删除的话，一般是先找到位置，然后直接删除即可，这个操作非常简单。还有销毁，直接free即可。
void delete(ElementType Key, HashTable H)
{
int pos;
pos=Find(Key,H);
H->TheCells[pos].Element=-1; //用-1标记已删除的
H->TheCells[pos].Info=Empty;
}
void DestroyTable( HashTable H )
{
free(H->TheCells);
free(H);
}再散列
回到生活中的例子，如果好的房子都被选完了，何不换一个离市中心远一点，但可以更大、更好的房子呢。于是建立另外一个大约两倍大的表（而且使用一个相关的新散列函数），扫描整个原始散列表，计算每个（未删除的）元素的新散列值并将其插入到新表中。这样的过程称为再散列。
它的公式我们可以用这样的式子表示：
fi (key) =RHi(key) (i=1,2,...,k)
这里RHi就是不同的散列函数，每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。
我们可以声明一个双倍大小的数组，并将每一个成员拷贝过来， 同时释放原来的队列。因此，再散列的实现很简单。我这里用了两个方法，方法一就是重新声明，方法二就是调整大小。
HashTable Rehash1( HashTable H )
{
int oldsize=H->TableSize;
Cell *oldcell=H->TheCells;
H=InitializeTable(2*oldsize); //重新初始化一个新的二倍大小的H
for(int i=0;i<oldsize;i++) //逐一拷贝过去
{
if(oldcell[i].Info == Legitimate)
insert(oldcell[i].Element,H);
}
free(oldcell);
return H;
}
HashTable Rehash2( HashTable H )
{
H->TheCells=(Cell *)realloc(H->TheCells,sizeof(Cell) * (2*H->TableSize));
H->TableSize*=2;
return H;
}
后记
关于散列，我们更多的是了解其过程，并能模拟解决冲突的情况。
Comments NOTHING