Day-24 Hash Table(杂凑表)

字典(Dictionary) 抽象资料结构

在字典里，有个物品，每一样东西都会跟随着一个(假设物品和物品之间，不会有相同的)，我们可以透过去找出我们想要的物品，而在字典这个资料结构，支援了以下三种操作

• Insert : 把一个物品插入到
• Delete : 把一个物品从中移除
• Search : 输入一个，如果有对应到的物品，回传该物品，如果找不到对应的物品，则回传NULL。

在字典中，如果我们使用Search搜寻不到对应到的物品，我们是没有办法像是二元搜寻树一样，找到前一个物品或是下一个物品的。

我们要解决上面这个字典的问题，我们可以使用AVL tree，他可以使Insert, Delete, Search这三个操作的时间复杂度均为，但我们希望在Search这个操作，我们希望能够达到的时间。

在python中，就存在dictionary这种资料结构，而他的底层细节即是使用杂凑表(hash table)的方式实现的

名词解释:

• satellite data(卫星数据)与key(键值): 以C语言作为举例，假设我们定义学生为一个结构(struct)如下:

sturct student{
    int age;
    char* name;
    int ID;
};

如果我们想要对学生以年纪(age)进行排序，那麽对於排序来说，age就是排序的关键字，或是键值(key)，而name和ID就称为satellite data(卫星数据)。可以想像成排序时，name和ID等satellite data是跟随age这个key进行排序。

Direct-address tables(直接寻址表)

运用直接寻址表，可以让我们在时间内完成Search的操作。

我们可以想像，我们开出了一个很大的阵列，而这个阵列中存放许多元素，每一个元素对应到的index当作是元素对应到的key，如图所示。

假设有一个集合存在有个元素，，每一个元素皆为keys(对应到阵列的index)，且这些keys彼此之间相互独立。

令为一直接循址表(以阵列的形式存在)，记为，其中中每一个位置(槽, slot)，对应到集合中的key，也就是集合中的元素。

会指向集合中key值为的元素，如果不存在，则NULL

表示所有关键字(key)的集合，表示该关键字有对应到的元素的关键字(key)集合，为直接循址表，透过去查询到欲寻找的元素，和集合就是集合的index。

假设我们有一条纪录，他的key为15，那我们就去查询(呼叫Search)是否存在某一条纪录的key为15，如果存在，则存在，并回传，否则为NULL。
而以下为SEARCH, INSERT, DELETE的虚拟码

DIRECT-ADDRESS-SEARCH(T, k)
return T[k]

DIRECT-ADDRESS-INSERT(T, x)
T[x.key]=x

DIRECT-ADDRESS-DELETE(T,x)
T[x.key] = NULL

而上面这些操作，都只需要的时间

但是在实务上，会遇到两个问题

1. 如果是一个很大的数值，那我们就必须要开一个超大的阵列。
2. 诚如上面的学生排序问题，如果我们将学生姓名作为key，那会变得非常麻烦。(可以将字串转成ASCII储存，或是使用类似prehash的技术)

因为上面我的使用阵列的index作为元素关联的key。我们希望我们能够保存数据的同时，让表的规模越小越好。

在阵列中，每一个空格我们可以把它称为的一个槽(slot)。

杂凑表(Hash table)与杂凑函数(Hash function)

为了避免掉直接循址表需要开出超级大的阵列这个问题，我们可以使用杂凑函数(Hash function)这项技术进行处理，使用杂凑函数去运算出key。也就是我们希望把一堆构成的集合，变成一个比较小的集合

在使用直接循址的方式时，具有关键字的元素会被存放在中，也就是的槽。而使用杂凑的方式，元素是存放在杂凑函数运算出的结果。由关键字透过杂凑函数计算出槽所在的位置，也就是，这里杂凑函数会将元素为关键字的集合映射(Mapping)到杂凑表上，而的值会比直接循址中集合的大小来的小的许多。

而此时我们可以说运算出的值是关键字的杂凑值(Hashing)。

概念上就是有用到的有个，而整个Table的大小为，我们希望

上面的操作我们会发现一件事情，如果关键字经过杂凑函数後得到的杂凑值和其他关键字得到的杂凑值相同时，他们会存取到相同的数值，发生这样的情况，我们称为冲突(collision)。例如一个Table中，有两笔资料存到同一个slot中。

会发生冲突的原因，在於我们给的关键字可以任意数值($U$集合中)，但是我们产生出的杂凑值需要在一定的范围内，也就是在的index内，因此会发生冲突。举例如下:

假设我们定义hash function为，假设，则如果我们要放入57和65这两个item，则经过hash function,,，这两个数值会存入到hash table中相同的slot，而这就是冲突。

冲突定义:

链接法(chaining)

链接法，概念为如果有超过一个以上的元素经过hash function後，储存到同样的slot，则在该slot使用linked list(链结串列)将资料全部储存在槽(slot)中，如下图所示

在使用这样的方法後，杂凑表$T$上的字典操作大概如下

CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE
delete x from the list T[h(x.key)]

插入和删除的操作皆为(假设为双向链结串列)，在最坏的情况下，就是所有资料都在同一个槽里面，而这时候Search的操作就会是，那杂凑表的效率就跟链结串列的效率差不多了，但是在实务上，最坏情况几乎不会发生，他的平均情况是非常好的。

链接法效率分析

上面提到，Search的最差情况就是所有元素都在同一个槽(slot)中，而Search的时间会取决於链结串列的长度。我们假设有一个具有个槽位的杂凑表，总共有个元素，有个元素要放入个槽位。

接着再做出一个假设，所有的再经过杂凑函数运算後，他们被映射到杂凑表中每一个槽的机率皆是相等的，机率皆为，且每一次均为独立事件，我们可以估计在使用链接法的情况下，中每一个槽的链结串列平均长度为(每一个元素映射到槽的机率为，总共个元素)，而我们会称他为杂凑表的装载因子(load factor)，会简称为。可以大於，等於，或是小於1，如果，则，也就是当，成立。

我们发现到使用杂凑表，它的效率取决於杂凑函数将分布在中个槽位的均匀程度，我们在上面假设了每一个元素出现在个槽位的机率皆是相等的，且为独立事件，我们称这个假设为简单均匀杂凑(simple uniform hashing)

杂凑表每一个槽的平均长度，可以使用期望值以下面形式表示

对於, 的链结串列长度以表示，则，并且的期望值为。

而当我们使用Search寻找为的元素，会有两种情况，第一种为在中没有找到一个元素的key为，第二种为成功找到key为的元素。

• 在第一次寻找不成功的情况下，我们要遍历链结串列的平均长度为，而假设计算杂凑函数需要的时间，则Search平均所需要的时间。
• 在第一次就成功寻找到，我们需要考虑到每一个槽中的链结串列被寻找到的机率并不是均等的，所含元素越多的链结串列，被寻找到的机率越大。但是，Search的期望值仍然为。

证明 : 假设欲寻找的元素是n个元素中任意一个，且每一个元素被寻找到的机率皆均等。在一次就成功寻找到元素的情况下，我们需要遍历的元素数量为前面的元素数量加1，因为之前的元素都是在之後插入在链接串列中，为了确保之前的元素都有被遍历到，对所在的链结串列，对以前插入到链结串列元素数量的期望值加1，在对所有个元素取平均，得到平均情况的机率。

令为插入到链结串列中第个元素，并设。对於和，定义指示器随机变数，表示经过杂凑函数，出现在杂凑表中同一个slot的情况，如果为真则，反之为0。在前面的简单均匀杂凑的假设之下，，发生两个经过杂凑函数映射到杂凑表中同一个slot机率的期望值，因此，在一次成功就寻找到元素，期望遍历过的元素总数的期望值可以用以下式子进行表示:

n个元素选一个，遍历整个Hash table()，每个Hash table需要检查的元素数量()

因此，一次成功寻找到元素所需要的全部时间就是遍历元素个数的期望值加上计算杂凑函数的时间。

因此，成功一次就寻找到元素和第一次没有成功寻找到，他们的平均情况皆为

经过上面的证明，得到当每一个slot中皆为双向链结串列时，Insert, Delete, Search的操作皆为的时间可以完成。当然，上面这些证明是基於这是一个简单均匀杂凑的条件下。

不是hash table都会是，实际上是取决於装载因子(如果有很多元素，但Hash table很小，那他必定不会是常数时间，如果能够保证Hash table随着元素的数量增长，才能够说他是常数时间)。Hash table之所以好用，就是因为我们可以在常数时间内完成动态集合的字典操作。

参考资料:Introduction to algorithms 3rd