基础数据结构（散列和优先队列）

散列表，优先队列的二叉堆实现。

散列表

散列表（hash table）是一种较高效率的仅支持insert，search和delete（字典操作）的动态集合结构，是普通数组概念的推广，理想情况下可以在O（1）的时间内寻址。

直接寻址表和散列表

• 当关键字的全域U较小时，可以直接寻址。用一个数组T[0，1，2，…，n - 1]来对应U中的每一个关键字。每个单元k指向U中关键字为k的元素，如果集合中没有关键字为k的元素，则T[k] = NIL。其字典操作非常简单：search( T, k ){ return T[k]; }，insert( T, x ) { T[key(x)] = x; }以及delete( T, x ){ T[key(x)] = NIL; }。所有操作都只需要O（1）的时间。
• 如果U很大，可用内存限制不能存储整个表，或者U很大但实际使用的关键字很少，导致了过多空间资源的浪费。
• 当存储在字典中的关键字集合K比所有可能用到的关键字域U小很多时，散列表比直接寻址表需要的存储空间小很多。与直接寻址不同之处在于：直接寻址中，关键字k的元素被存放在槽k中，散列表中，该元素存储在槽h（k）中。h（）是散列（哈希）函数，根据关键字k计算出槽的位置，因此将关键字域U映射到散列表T的[0…n-1]的槽中。称之为，具有关键字k的元素被散列到槽h（k）上，或者说h（k）是关键字k的散列（哈希）值。采用散列函数的目的在于缩小需要处理的下标范围，将需要处理的下标从|U|降到n，从而降低了空间开销。

碰撞

根据上面的描述可以看出，h（）是根据关键字计算散列值的函数，因为具有某种固定的计算规则，所以可能会将两个不同的关键字映射到同一个槽上。我们将这种情况称为碰撞。最理想的解决方法是完全避免碰撞，这可以通过选择散列函数h来实现，目标是使h尽可能产生随机的散列值。但是根据鸽巢原理，一旦|U|>n，一定会出现碰撞，此时需要解决必然会出现的碰撞。

• 链接法

  • 实现：将散列到同一个槽k中的所有元素放到一个链表里，槽k存储链表的表头，如果不存在这样的链表，则槽k = NIL。通过链接解决碰撞后的字典操作如下：insert( T, x ) { insert element with key x at the head of list T[ h(x) ] }，search( T, x ) { search for an element with key x in list T[ h(k) ] }，delete( T, x ) { delete element with key x from the list T[ h(x) ] }，这里x是U中包含的关键字。
  • 性能：插入操作复杂度O（1），删除和搜索操作需要对槽k中的每个元素加以对比，因此与表的长度有关。假设有一个能存储n个元素，具有m个槽位的散列表T，在最差情况下，所有n个关键字全部散列到其中同一个槽中，这时查找时间为Θ（n），加上计算散列函数的时间将和线性表无异。散列方法的优势依赖于所选取的散列函数h在一般情况下将所有关键字分布在m个槽位上的均匀程度。假设任何元素散列到m个槽中的任何一个可能性是相同的，并且与其他元素已经散列的位置无关（称这个假设为简单一致散列，simple uniform hashing）：对于m个槽，列表T[i]的长度使用Ni表示，n = N0 + N1 + … + Nm-1，因此Ni的平均值为α = n / m。定义T的装载因子（load factor）为α，用来表示一个链中平均存储的元素个数。在O（1）的时间内计算出散列值h（x），因此查找关键字为x的元素的时间与表T[ h(x) ]的长度Nh(x)线性相关。分析（离散数学中关于算法最坏和平均复杂度的分析）可知，平均情况下查找的时间复杂度为Θ（1+α）。这说明：当散列表中槽数m和表中元素数n成正比时，即n = O（m）时，α = n / m = O（m）/ m = O（1）。因此：散列表中槽数和表中元素数成正比时，平均情况下全部字典操作都可以在O（1）时间内完成。
  • 以上部分的原文在《算法导论（第二版）》的224-225页可以找到，对其进行了部分修改。在算导原文（Page 224）中提出，采用链接法时，如果使用双向链表可以使删除操作复杂度在任何情况下都为O（1）：这里注意书中提出的“删除一个元素x的操作可以在O（1）时间内完成”，这里删除的是元素x，x是指向某个对象的指针，因此双向链表可以在O（1）内完成。

• 开放寻址法

  开放寻址法（open addressing），所有的元素都存储在散列表中，即每个槽或者包含一个元素，或者包含NIL。

  • 当插入某个关键字为x的元素时，先计算散列值h（x），如果槽h（x）是空槽，则将元素插入该槽，否则从h（x）槽开始向后连续探查，直到寻找到一个空槽来存储该元素。这里的连续探查不一定是0，1，2，…，n-1这样的顺序，而应该依赖于待插入的关键字x：为哈希函数h（）添加参数，变成{h（k，0），h（k，1），…，h（k，m-1）}，使其根据当前探查的次数来决定探查哪些槽，这样做的目的在于使查找的时间依赖于α（完全依赖于散列函数的查找序列近似依赖于关键字，而根据简单一致性散列，这样的查找时间便依赖于α）。改变后的h的不同，会导致效果的不同，将在后面详细介绍。下面给出插入的伪代码描述：

Open_addInsert( T, k ){
	i = 0
	repeat j = h( k, i )
		if T[j] == NIL // || T[j] == Deleted
			T[j] = k
			return j
		else 
			i = i + 1
	until i == m
	error "Overflow"
}

• 当查找某个元素时，需要从散列值指向的槽向后连续探查，直到找到要寻找的元素，或发现该元素不在表中。

Open_addSearch( T, k ){
	i = 0;
	repeat j = h( k, i )
		if T[j] == k
			return j
		i = i + 1
	until T[j] == NIL or i == m
	return NIL
}

• 从槽i删除元素时，不能直接将槽置为NIL，否则若删除前有某元素k插入，发现i被占用，将k置于槽i后面的某个位置，则在槽i被置为NIL后将无法检索到k。可以通过给槽i设置一个特殊的值Deleted表示已被删除，因此需要修改insert部分，增加一个判断（代码中注释部分）。但当使用Deleted标注时，查找时间将不再依赖于α（伪删除）。因此在必须删除关键字时，通常采用链接法。

  • 开放寻址法探查序列的计算

    计算探查序列通常有线性探查，二次探查和双重探查。这三种方法都可以保证对没个k，产生的{h（k，0），…，h（k，m-1）}都是{0，1，…，m-1}的一个排列。理想散列要求可以产生m！个探查序列，而这三种方法产生的探查序列可能结果都不超过m^2 个。

• 线性探查：给定一个普通散列函数h’：U->{0，1，…，m-1}，将其成为辅助散列函数，线性探查（linear probling）采用的散列函数h为h( k, i ) = ( h’(k) + i )mod m，其中i = 0，1，…，m-1。这种探查方法产生的探查序列近似于{0，1，2，…，m-1}的模式，并且完全依赖于初始探查位置，因此最多能产生m个不同的探查序列。线性探查容易实现，但存在一次群集（primary clustering）问题，随着时间的推移，连续占用的槽不断增加，平均查找时间也不断增加。因为当一个空槽前有i个满槽时，该空槽是下一个将被占用的槽的概率是（i+1）/ m（因为探查序列逐个向后偏移，每个散列到前面i个满槽的元素都会一直扫描到这个空槽才会停止），因此群集现象很容易出现，连续被占用槽会越来越长，平均查找时间也会随之增加。

• 二次探查：采用如下形式的散列函数h( k, i ) = ( h’(k) + P×i + Q×i^2 ) mod m，这里h’是一个辅助散列函数，P和Q（不等于0）是辅助常数，i = 0，1，…，m-1。初始探查位置为T[h’（k）]，后续探查位置会在此基础上增加一个偏移量，这个偏移量以二阶形式依赖于探查号i。常数P，Q的选择影响着该方法的效率。此外，如果两个关键字k1，k2的初始探查位置相同，那么他们接下来的探查序列也是相同的，因为h（k1,0） = h（k2,0）意味着h（k1,i）=h（k2,i）。这一性质可能导致程度较轻的群集现象，称为二次群集。此方法和线性探查一样，产生的探查序列都依赖于初始探查位置，因此只有m种不同的探查序列。
• 双重散列：是用于开放寻址法最好的方法之一，其产生的排列具有随机选择的排列特性。采用如下形式：h( k, i ) = ( h1(k) + ih2(k) ) mod m，其中h1和h2为辅助散列函数。初始探查位置为T[h1(k)]，后续的探查位置在此基础上加上偏移量h2（k）×探查号并对m取模。与前两种方式不同的是，这里的探查序列以两种方式依赖于关键字k，因为初始探查位置和偏移量都可能发生变化。为了能查找到整个散列表，值h2（k）要和表的大小m互质。一种确保这个条件成立的方法是取m为2的幂，并设计一个总产生奇数的h2（）。另一种可行的方法是取m为质数，并设计一个总产生比m小的正整数的h2（）。例如，可以取m为一个质数，并取h1（k）=k mod m，h2（k）=1+（k mod m’）这里的m’略小于m（可取m-1）；假如这里m = 701，m’ = 700，k = 123456，那么h1（k）=80，h2（k）=257，因此第一个探查位置为80，然后每257个槽（mod m）检查一次，直到找到关键字或检查过所有的槽。这种散列方法用了Θ（m^2)种探查序列，较为接近理想的“一致散列”。
• 性能：在开放寻址法中，α = n / m，因为每个槽最多只能有一个元素，因此n ≤ m，因此α ≤ 1。有定理：给定一个装载因子为α = n/m < 1的开放寻址散列表，假设一致散列，则在一次不成功的查找中，期望的探查数至多为1/（1-α），平均情况下插入一个元素至多需要做1/（1-α）次探查，一次成功查找中的期望探查数至多为-ln（1-α）/α。证明在算法导论242-243页。上述定理说明，散列表的α越小，期望效率越好。

散列函数

一个好的散列函数所应该近似满足简单一致散列的假设。当然一般情况下无法检测这一条件是否成立，因为无法确定关键字所属的概率分布，而关键字可能互相并不完全独立。实践中通常通过启发式技术构造好的散列函数，例如编译器的变量列表中，pt和pts相似并且经常出现，好的散列函数应该最小化将这二者映射到同一个槽中的可能性。部分应用可能会要求比简单一致更严格的性质，比如要求某些很相似的关键字具有完全不同的散列值。全域散列（unversal hasing）通常能够提供这些性质。

• 将关键字映射到自然数中，例如一个字符串中的每个关键字可以被解释成ascll码，标识符pt可以被解释为十进制整数对（112，116），之后按128为基数，pt即为112×128+116=14452。将关键字转换为较大的自然数更容易设计高效的散列方法。假设所有给定的关键字都是自然数。

  • 除法散列法：h（k）= k mod m。这里m不应该是2的幂，如果m = 2^p ，则h（k）为k的低p位。m的值通常是和2的整数幂不太接近的质数。
  • 乘法散列法：h（k）= m×（k×A mod 1）的下取整。常数A满足（ 0 < A < 1 ），即用m乘以kA的小数部分再取结果的底。这种方法对m的选择没有严格的要求，通常取m为2的某个幂次。某些特定的A值效果更好，最佳的A值和待散列的数据特征有关。Donald E.Knuth认为A = （ sqrt(5) - 1 ）/2 = 0.6180339887 是一个较为理想的值。可以取A为一个形如s/2^ω 的分数，并使其接近0.618。

• 全域散列：如果精心设计关键字使得所有关键字都全部散列到同一个槽中，那么每个特定的散列函数都可能出现这种最坏情况状态。因此唯一的改进方法是使散列函数独立于关键字，随机选取散列函数。很容易设计出一个全域散列函数类：选择一个足够大的质数p > |U| > m，使得每个关键字都可以落在0～p-1的范围内，则对于任意a∈{1，2，…，p-1}，b∈{0，1，…，p-1}，定义h(a,b)(k) = ( ( a × k + b ) mod p ) mod m。例如p=17，m=6，则h(3,4)(8)=5。

---

优先队列和二叉堆

普通队列是一种先进先出的数据结构，队尾插入，队头删除。在优先队列（priority queue）中，每个元素被赋予不同的优先级，出队时优先级最高的元最先被删除（largest-in，first-out）。优先队列适用范围很广，如构造哈夫曼编码（每次寻找到节点集合中频率最小的两个点，合并后继续循环），合并n个有序序列为一个有序序列（将n个有序序列的第一个元素取出，添加到优先队列，并且取最小值，再添加新元素，以此类推），操作系统中一些任务调度算法等。优先队列通常通过最小堆实现，因此适用于堆的应用都适用于优先队列。

完整实现

在排序和字符串匹配中给出过堆排序的实现，在Prim算法中也使用了堆优化。下面以整型元素为例给出完整的最小堆实现。

• 结构定义

typedef struct{
	int * list;
	int heapsize;
}heap;

• 下标获取

int Father( int u ){
	return u / 2;
}
int Left( int u ){
	return 2 * u;
}
int Right( int u ){
	return 2 * u + 1;
}

• 自顶向下维护

void heapDown( heap & h, int u ){
	while ( Left(u) <= h.heapsize ){
		int child;
		if ( Left(u) == h.heapsize || h.list[ Left(u) ] < h.list[ Right(u) ] )
			child = Left(u);
		else 
			child = Right(u);
		if ( h.list[ child ] < h.list[u] ){
			swap( h.list, u, child );
			u = child;
		}
		else 
			break;
	}
}

• 自底向上维护

void heapUp( heap & h, int u ){
	while ( u > 1 ){
		if ( h.list[ Father(u) ] > h.list[u] ){
			swap( h.list, u, Father(u) );
			u = Father(u);
		}
		else 
			break;
	}
}

• 入队

void push( heap & h, int w ){
	h.list[++h.heapsize] = w ;
	heapUp( h, h.heapsize );
}

• 出队

int pop( heap & h ){
	int root = h.list[1];
	swap( h.list, 1, h.heapsize-- );
  	heapDown( h, 1 );
	return root;
}

STL中优先队列的使用

• empty()	如果队列为空返回真
  pop()	删除队列头元素
  push()	加入元素
  size()	返回优先队列中拥有的元素个数
  top()	返回优先队列队头元素

• 头文件#include<queue>，声明方式（以整型数据为例）priority_queue<int> q;
• 自定义优先级

struct cmp{
	operator bool()( int x, int y ){
		return x > y;	// 数据小的优先级高
	}
};
priority_queue<int, vector<int>, cmp > q;

• 通过结构体声明比较优先级方式

struct node {
	int x, y; 	// y为值，x为优先级
	friend bool operator< ( node a, node b ){	重载运算符比较优先级
		return a.x > b.x; //在结构体中，x更小的优先级更高
	}
};
priority_queue<node> q;

---

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2015/09/28/Data-Structure-basis2/) 、作者信息（Forec）和本声明。