Week11散列查找
11.1散列表
已知的几种查找方法：
| 查找方法 | 时间复杂度 |
|---|---|
| 顺序查找 | $O(N)$ |
| 二分查找（静态查找） | $O(log_2N)$ |
| 二叉树搜索树 | $O(h)h$为二叉查找树的高度 |
| 平衡二叉树 | $O(log_2N)$ |
例 在登录QQ的时候， QQ服务器是如何核对你的身份？面对庞大的用户群,如何快速找到用户信息?
分析 看看是否可以用二分法查找。
- 十亿（109 ≈ 230） 有效用户，用二分查找30次。
- 十亿$(109 ≈ 230) × 1K ≈ 1024G， 1T$连续空间。
- 按有效QQ号大小有序存储： 在连续存储空间中， 插入和删除一个新QQ号码将需要移动大量数据。
问题 如何快速搜索到需要的关键词？ 如果关键词不方便比较怎么办？
查找的本质: 已知对象找位置。
- 有序安排对象：全序、半序
- 直接“算出”对象位置： 散列
散列查找法的两项基本工作：
计算位置：构造散列函数确定关键词存储位置；
解决冲突：应用某种策略解决多个关键词位置相同的问题
时间复杂度几乎是常量： $O(1)$， 即查找时间与问题规模无关！
散列表（哈希表）
类型名称:符号表（SymbolTable）
数据对象集： 符号表是“名字$(Name)$-属性$(Attribute)$”对的集合。
操作集：$ Table \in SymbolTable， Name \in NameType， Attr \in AttributeType$
SymbolTable InitializeTable(int TableSize)
//创建一个长度为TableSize的符号表；
Boolean IsIn(SymbolTable Table, NameType Name)
//查找特定的名字Name是否在符号表Table中；
AttributeType Find(SymbolTable Table, NameType Name)
//获取Table中指定名字Name对应的属性；
SymbolTable Modefy(SymbolTable Table, NameType Name, AttributeType Attr)
//将Table中指定名字Name的属性修改为Attr；
SymbolTable Insert(SymbolTable Table, NameType Name, AttributeType Attr)
//向Table中插入一个新名字Name及其属性Attr；
SymbolTable Delete(SymbolTable Table, NameType Name)
//从Table中删除一个名字Name及其属性。“散列（ Hashing）” 的基本思想是：
（ 1）以关键字key为自变量，通过一个确定的函数 h（散列函数） ，计算出对应的函数值$h(key)$，作为数据对象的存储地址。
（ 2） 可能不同的关键字会映射到同一个散列地址上，即$h(key_i) = h(key_j)$（当$key_i ≠key_j$），称为“冲突$(Collision)$”。—-需要某种冲突解决策略
例 有n = 11个数据对象的集合{18， 23， 11， 20， 2， 7， 27， 30，42， 15， 34}。
符号表的大小用$TableSize = 17$，选取散列函数h如下：$h(key) = key\ mod\ TableSize $(求余)
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键词 | 34 | 18 | 2 | 20 | 23 | 7 | 42 | 27 | 11 | 30 | 15 |
存放：
$h(18)=1, h(23)=6, h(11)=11, h(20)=3, h(2)=2, …….$
如果新插入35，$ h(35)=1$, 该位置已有对象！ 冲突！！
查找:
$key = 22, h(22)= 5$，该地址空，不在表中
$key = 30, h(30)= 13$，该地址存放是30，找到！
装填因子（Loading Factor）： 设散列表空间大小为$m$，填入表中元素个数是$n$，则称$α＝ n / m$为散列表的装填因子
$α＝11 / 17 ≈ 0.65$
例 将acos、 define、 float、 exp、 char、 atan、 ceil、 floor、clock、 ctime， 顺次存入一张散列表中。
散列表设计为一个二维数组$Table[26][2]$， 2列分别代表 2个槽。
如何设计散列函数$h (key ) =$ ?$ h(key) = key[0] – ‘a’$
| 槽0 | 槽1 | |
|---|---|---|
| 0 | acos | atan |
| 1 | ||
| 2 | char | cell |
| 3 | define | |
| 4 | exp | |
| 5 | float | floor |
| 6 | ||
| $\cdots$ | ||
| 25 |
如果没有溢出,$T_{查询} = T_{插入} = T_{删除} = O( 1 ) $
11.2 散列函数的构造方法
一个“好”的散列函数一般应考虑下列两个因素：
- 计算简单，以便提高转换速度；
- 关键词对应的地址空间分布均匀，以尽量减少冲突。
数字关键词的散列函数构造
1．直接定址法
取关键词的某个线性函数值为散列地址，即$h(key) = a \times key + b$ (a、 b为常数)
| 地址h(key) | 出生年份(key) | 人数(attribute) |
|---|---|---|
| 0 | 1990 | 1285万 |
| 1 | 1991 | 1281万 |
| 2 | 1992 | 1280万 |
| … | …… | …… |
| 10 | 2000 | 1250万 |
| … | …… | …… |
| 21 | 2011 | 1180万 |
$h(key)=key-1990$
2．除留余数法
散列函数为：$h(key) = key\ mod\ p$
例:$ h(key) = key \% 17$
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键词 | 34 | 18 | 2 | 20 | 23 | 7 | 42 | 27 | 11 | 30 | 15 |
这里：$ p = Tablesize = 17 $。一般， p 取素数
3．数字分析法
分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
比如： 取11位手机号码key的后4位作为地址：
散列函数为：$ h(key) = atoi(key+7) (char *key) $
如果关键词 key 是18位的身份证号码：
$h_1(key) = (key[6]-‘0’)\times 10^4 + (key[10]-‘0’)\times 10^3 +
(key[14]-‘0’)\times 10^2 + (key[16]-‘0’)\times 10 + (key[17]-‘0’) $
$h(key) = h1(key)\times 10 + 10$当$key[18]=’x’$时
或$= h1(key)\times 10 + key[18]-‘0’$当 $key[18] 为’0’-’9’$时
4．折叠法
把关键词分割成位数相同的几个部分，然后叠加
如： 56793542
$h(key)\equiv542+793+056\equiv1391\equiv391\ mod\ 1000$
5．平方取中法
如： 56793542
$56793542 \times 56793542 =3225506412905764 $
$h(56793542) = 641 $
字符关键词的散列函数构造
1．一个简单的散列函数——ASCII码加和法
对字符型关键词key定义散列函数如下：
$h(key) = (Σkey[i])\ mod\ TableSize$
冲突严重： a3、b2、 c1；eat、 tea；
2．简单的改进——前3个字符移位法
$h(key)=(key[0]\times 27^2 + key[1]\times 27 + key[2])\ mod\ TableSize$
3．好的散列函数——移位法
涉及关键词所有n个字符，并且分布得很好：
$h(key)=(\sum_{i=0}^{n-1}key[n-i-1]\times32^i)\ mod\ Tablesize$
仍然冲突： string、 street、strong、 structure等等；
空间浪费： $3000/263 ≈ 30%$
如何快速计算：
$h(“abcde”)=’a’\times 32^4+’b’\times 32^3+’c’\times 32^2+’d’\times 32+’e’ $
Index Hash(const char* Key, int TableSize){
unsigned int h = 0; /* 散列函数值， 初始化为0 */
while (*Key != ‘\0’) /* 位移映射 */
h = (h << 5) + *Key++;
return h % TableSize;
}11.3 冲突处理方法
常用处理冲突的思路：
换个位置: 开放地址法
同一位置的冲突对象组织在一起: 链地址法
开放定址法（Open Addressing）
一旦产生了冲突（该地址已有其它元素），就按某 种规则去寻找另一空地址
若发生了第 i 次冲突，试探的下一个地址将增加di， 基本公式是：
$h_i(key) = (h(key)+d_i)\ mod\ TableSize ( 1≤ i < TableSize ) $
di 决定了不同的解决冲突方案： 线性探测$(d_i=i)$、平方探测$(d_i=\pm i^2)$、双散列$(d_i=i*h_2(key))$。
1.线性探测法（Linear Probing）
线性探测法： 以增量序列$ 1， 2， ……，(TableSize -1)$循环试探下一个存储地址。
例 设关键词序列为 {47， 7， 29， 11， 9， 84， 54， 20， 30}，
散列表表长$TableSize =13$ （装填因子 $α = 9/13 ≈ 0.69$）；
散列函数为： $h(key) = key\ mod\ 11$。
用线性探测法处理冲突，列出依次插入后的散列表，并估算查找性能
| 关键词 （key） | 47 | 7 | 29 | 11 | 9 | 84 | 54 | 20 | 30 |
|---|---|---|---|---|---|---|---|---|---|
| 散列地址 $h(key)$ | 3 | 7 | 7 | 0 | 9 | 7 | 10 | 9 | 8 |
| 关键词 (key) | 47 | 7 | 29 | 11 | 9 | 84 | 54 | 20 | 30 |
|---|---|---|---|---|---|---|---|---|---|
| 散列地址 h(key) | 3 | 7 | 7 | 0 | 9 | 7 | 10 | 9 | 8 |
| 冲突次数 | 0 | 0 | 1 | 0 | 0 | 3 | 1 | 3 | 6 |
注意聚集现象！
散列表查找性能分析
成功平均查找长度$(ASLs) $
不成功平均查找长度 $(ASLu)$
| $H(key)$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| key | 11 | 30 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | ||||
| 冲突次数 | 0 | 6 | 0 | 0 | 1 | 0 | 3 | 1 | 3 |
$ASLs$： 查找表中关键词的平均查找比较次数（其冲突次数加1）
$ASLs= (1+7+1+1+2+1+4+2+4) / 9 = 23/9 ≈ 2.56$
$ASLu$：不在散列表中的关键词的平均查找次数（不成功）
一般方法：将不在散列表中的关键词分若干类。
如：根据$H(key)$值分类
$ASL u= (3+2+1+2+1+1+1+9+8+7+6)/ 11 = 41/11 ≈ 3.73 $
例 将acos、 define、 float、 exp、 char、 atan、 ceil、 floor，顺次存入一张大小为26的散列表中。
$H(key)=key[0]-’a’$，采用线性探测$d_i=i$
| cos | atan | char | define | exp | float | ceil | floor | ….. | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 25 |
$ASLs$： 表中关键词的平均查找比较次数
$ASLs= （1+1+1+1+1+2+5+3） / 8 = 15/8 ≈ 1.87$
$ASLu$：不在散列表中的关键词的平均查找次数（不成功）
根据$H(key)$值分为26种情况： H值为$0,1,2,…,25$
$ASLu= （9+8+7+6+5+4+3+2+1*18） / 26 = 62/26 ≈ 2.38 $
2.平方探测法（Quadratic Probing） — 二次探测
平方探测法： 以增量序列$1^2， -1^2， 2^2， -2^2， ……， q^2， -q^2$,且$q ≤\lfloor TableSize/2\rfloor$ 循环试探下一个存储地址。
[例] 设关键词序列为 {47， 7， 29， 11， 9， 84， 54， 20， 30}，
散列表表长$TableSize = 11$，
散列函数为：$ h(key) = key\ mod\ 11$。
用平方探测法处理冲突，列出依次插入后的散列表，并估算$ASLs$。
| 关键词 key | 47 | 7 | 29 | 11 | 9 | 84 | 54 | 20 | 30 |
|---|---|---|---|---|---|---|---|---|---|
| 散列地址h(key) | 3 | 7 | 7 | 0 | 9 | 7 | 10 | 9 | 8 |
| 冲突次数 | 0 | 0 | 1 | 0 | 0 | 2 | 0 | 3 | 3 |
$ASL s = (1+1+2+1+1+3+1+4+4) / 9 = 18/9 = 2$
是否有空间，平方探测（二次探测）就能找得到？
$h(k)= k\ mod\ 5 $
| 5 | 6 | 7 | ||
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 |
插入 11，$ h(11)=1$
探测序列：$ 1+1=2, 1-1=0, (1+2^2)mod\ 5=0, (1-2^2)mod\ 5=2,$
$(1+3^2)mod\ 5=0, (1-3^2)mod\ 5=2, (1+4^2)mod\ 5=2,…$
有定理显示：如果散列表长度$TableSize$是某个$4k+3$（k是正整数）形式的素数时， 平方探测法就可以探查到整个散列表空间。
typedef struct
HashTbl* HashTable;
struct HashTbl {
int TableSize;
Cell* TheCells;
}H;
HashTable InitializeTable(int TableSize){
HashTable H;
int i;
if (TableSize < MinTableSize) {
Error("散列表太小");
return NULL;
}
/* 分配散列表 */
H = (HashTable)malloc(sizeof(struct HashTbl));
if (H == NULL)
FatalError("空间溢出!!!");
H->TableSize = NextPrime(TableSize);
/* 分配散列表 Cells */
H->TheCells = (Cell*)malloc(sizeof(Cell) * H->TableSize);
if (H->TheCells == NULL)
FatalError("空间溢出!!!");
for (i = 0; i < H->TableSize; i++)
H->TheCells[i].Info = Empty;
return H;
}
Position Find(ElementType Key, HashTable H) { /*平方探测*/
Position CurrentPos, NewPos;
int CNum; /* 记录冲突次数 */
CNum = 0;
NewPos = CurrentPos = Hash(Key, H->TableSize);
while (H->TheCells[NewPos].Info != Empty &&
H->TheCells[NewPos].Element != Key) {
/* 字符串类型的关键词需要 strcmp 函数!! */
if (++CNum % 2) { /* 判断冲突的奇偶次 */
NewPos = CurrentPos + (CNum + 1) / 2 * (CNum + 1) / 2;
while (NewPos >= H->TableSize)
NewPos -= H->TableSize;
}
else {
NewPos = CurrentPos - CNum / 2 * CNum / 2;
while (NewPos < 0)
NewPos += H->TableSize;
}
}
return NewPos;
}
void Insert(ElementType Key, HashTable H){ /* 插入操作 */
Position Pos;
Pos = Find(Key, H);
if (H->TheCells[Pos].Info != Legitimate) {
/* 确认在此插入 */
H->TheCells[Pos].Info = Legitimate;
H->TheCells[Pos].Element = Key;
/*字符串类型的关键词需要 strcpy 函数!! */
}
}在开放地址散列表中， 删除操作要很小心。通常只能“懒惰删除” ，即需要增加一个“删除标记$(Deleted)$” ，而并不是真正删除它。以便查找时不会“断链”。其空间可以在下次插入时重用。
3.双散列探测法（Double Hashing）
双散列探测法: $d_i 为i*h_2(key)， h_2(key)$是另一个散列函数探测序列成： $h_2(key)， 2h_2(key)， 3h_2(key)， …… $
对任意的$key$， $h_2(key) ≠ 0$ ！
探测序列还应该保证所有的散列存储单元都应该能够被探测到。
选择以下形式有良好的效果：
$h_2(key) = p - (key\ mod\ p)$
其中：$ p < TableSize， p、 TableSize$都是素数。
4.再散列（Rehashing）
当散列表元素太多（即装填因子 α太大）时， 查找效率会下降；
实用最大装填因子一般取 $0.5 <= α<= 0.85 $
当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫做“再散列”（$Rehashing$）
分离链接法（Separate Chaining）
分离链接法：将相应位置上冲突的所有关键词存储在同一个单链表中
例 设关键字序列为 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21;
散列函数取为： $h(key) = key\ mod\ 11$；
用分离链接法处理冲突。
表中有9个结点只需1次查找，5个结点需要2次查找
查找成功的平均查找次数：$ ASL s=(9+5*2) / 14 ≈ 1.36$
struct HashTbl {
int TableSize;
List TheLists;
} *H;
typedef struct ListNode* Position, * List;
struct ListNode {
ElementType Element;
Position Next;
};
typedef struct HashTbl* HashTable;
struct HashTbl {
int TableSize;
List TheLists;
};
Position Find(ElementType Key, HashTable H){
Position P;
int Pos;
Pos = Hash(Key, H->TableSize); /*初始散列位置*/
P = H->TheLists[Pos].Next; /*获得链表头*/
while (P != NULL && strcmp(P->Element, Key))
P = P->Next;
return P;
}11.4 散列表的性能分析
平均查找长度（$ASL$）用来度量散列表查找效率：成功、不成功
关键词的比较次数，取决于产生冲突的多少
影响产生冲突多少有以下三个因素：
（1） 散列函数是否均匀；
（2） 处理冲突的方法；
（3）散列表的装填因子α。
分析：不同冲突处理方法、装填因子对效率的影响
1.线性探测法的查找性能
可以证明，线性探测法的期望探测次数 满足下列公式：
$$
p=\left\{
\begin{aligned}
&\frac{1}{2}[1+\frac{1}{(1-\alpha^2)}]\qquad (对插入和不成功查找而言) \newline
&\frac{1}{2}(1+\frac{1}{a-\alpha}) \qquad (对成功查找而言)
\end{aligned}
\right.
$$
当$α= 0.5$时，
插入操作和不成功查找的期望 $ASLu = 0.5*(1+1/(1-0.5) 2 ) = 2.5$ 次
成功查找的期望 $ASLs = 0.5*(1+1/(1-0.5) ) = 1.5$次
| H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| key | 11 | 30 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | ||||
| 冲突次数 | 0 | 6 | 0 | 0 | 1 | 0 | 3 | 1 | 3 |
$α= 9/13=0.69$，于是
期望$ ASLu = 0.5*(1+1/(1-0.69) 2 ) = 5.70$次
期望 $ASLs = 0.5*(1+1/(1-0.69) ) = 2.11$次（实际计算$ASLs =2.56$）
2.平方探测法和双散列探测法的查找性能
可以证明，平方探测法和双散列探测法探测次数 满足下列公式：
$$
p=\left\{
\begin{aligned}
&\frac{1}{1-\alpha}\qquad (对插入和不成功查找而言) \newline
&-\frac{1}{\alpha}ln(1-\alpha) \qquad (对成功查找而言)
\end{aligned}
\right.
$$
当$α= 0.5$时，
插入操作和不成功查找的期望$ ASLu = 1/(1-0.5) = 2 $次
成功查找的期望 $ASLs = -1/0.5* ln(1-0.5) ≈ 1.39$ 次
| H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| key | 11 | 30 | 20 | 47 | 84 | 7 | 29 | 9 | 54 | ||
| 冲突次数 | 0 | 3 | 3 | 0 | 2 | 0 | 1 | 0 | 0 |
$α= 9/11=0.82$，于是
期望 $ASLu = 1/(1-0.82) ≈ 5.56$次
期望$ ASLs = -1/0.5* ln(1-0.5) ≈ 2.09$次（例中$ASLs =2$）。
期望探测次数与装填因子α的关系:
当装填因子α< 0.5的时候，各种探测法的期望探测次数都不大，也比较接近。
随着 α 的增大，线性探测法的期望探测次数增加较快， 不成功查找和插入操作的期望探测次数比成功查找的期望探测次数要大。
合理的的最大装入因子α应该不超过0.85。
3.分离链接法的查找性能
所有地址链表的平均长度定义成装填因子α， α有可能超过1。
不难证明：其期望探测次数 p为：
$$
p=\left\{
\begin{aligned}
&\alpha + e^{-\alpha}\qquad (对插入和不成功查找而言) \newline
&1+\frac{\alpha}{2} \qquad (对成功查找而言)
\end{aligned}
\right.
$$
当$α = 1$时，
插入操作和不成功查找的期望 $ASLu = 1+e-1 = 1.37 $次，
成功查找的期望 $ASLs = 1+1/2 = 1.5$ 次。
前面例子14个元素分布在11个单链表中，所以α= 14/11≈1.27， 故
期望 $ASLu = 1.27+e^{-1.27} ≈ 1.55$次
期望 $ASLs = 1+1.27/2 ≈ 1.64$次（例中$ASLs =1.36$）。
选择合适的 h(key) ，散列法的查找效率期望是常数$O(1)$， 它几乎与关键字的空间的大小n无关！也适合于关键字直接比较计算量大的问题
它是以较小的α为前提。因此，散列方法是一个以空间换时间
散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。
开放地址法：
散列表是一个数组，存储效率高，随机查找。
散列表有“聚集”现象
分离链法：
散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。
关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。
太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。
11.5应用：文件中单词词频统计
例 给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频。
假设单词字符定义为大小写字母、数字和下划线，其它字符均认为是单词分隔符，不予考虑。
分析 关键：对新读入的单词在已有单词表中查找，如果已经存在，则将该单词的词频加1，如果不存在，则插入该单词并记词频为1。
如何设计该单词表的数据结构才可以进行快速地查找和插入？
散列表！
int main() {
int TableSize = 10000; /* 散列表的估计大小 */
int wordcount = 0, length;
HashTable H;
ElementType word;
FILE *fp;
char document[30] = "HarryPotter.txt"; /* 要被统计词频的文件名 */
H = InitializeTable(TableSize); /* 建立散列表 */
if ((fp = fopen(document, “r” )) == NULL) FatalError(“无法打开文件 !\n” );
while (!feof(fp)) {
length = GetAWord(fp, word); /* 从文件中读取一个单词 */
if (length > 3) { /* 只考虑适当长度的单词 */
wordcount++; /*统计文件中单词总数 */
InsertAndCount(word, H);
}
}
fclose(fp);
printf("该文档共出现 %d 个有效单词， ", wordcount);
Show(H, 10.0 / 100); /* 显示词频前10%的所有单词 */
DestroyTable(H); /* 销毁散列表 */
return 0;
}Show需要实现的功能：
（1）统计最大词频；
（2）用一组数统计从1到最大词频 的单词数；
（3）计算前10%的词频应该是多少
（4）输出前10%词频的单词
代码模板
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType; /* 关键词类型用整型 */
typedef int Index; /* 散列地址类型 */
typedef Index Position; /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;
typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry {
ElementType Data; /* 存放元素 */
EntryType Info; /* 单元状态 */
};
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
Cell *Cells; /* 存放散列单元数据的数组 */
};
int NextPrime(int N) { /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
int i, p = (N % 2) ? N + 2 : N + 1; /*从大于N的下一个奇数开始 */
while (p <= MAXTABLESIZE) {
for (i = (int)sqrt(p); i > 2; i--)
if (!(p % i))
break; /* p不是素数 */
if (i == 2)
break; /* for正常结束，说明p是素数 */
else
p += 2; /* 否则试探下一个奇数 */
}
return p;
}
HashTable CreateTable(int TableSize) {
HashTable H;
int i;
H = (HashTable)malloc(sizeof(struct TblNode));
/* 保证散列表最大长度是素数 */
H->TableSize = NextPrime(TableSize);
/* 声明单元数组 */
H->Cells = (Cell *)malloc(H->TableSize * sizeof(Cell));
/* 初始化单元状态为“空单元” */
for (i = 0; i < H->TableSize; i++)
H->Cells[i].Info = Empty;
return H;
}
Position Find(HashTable H, ElementType Key) {
Position CurrentPos, NewPos;
int CNum = 0; /* 记录冲突次数 */
NewPos = CurrentPos = Hash(Key, H->TableSize); /* 初始散列位置 */
/* 当该位置的单元非空，并且不是要找的元素时，发生冲突 */
while (H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != Key) {
/* 字符串类型的关键词需要 strcmp 函数!! */
/* 统计1次冲突，并判断奇偶次 */
if (++CNum % 2) { /* 奇数次冲突 */
NewPos = CurrentPos +
(CNum + 1) * (CNum + 1) / 4; /* 增量为+[(CNum+1)/2]^2 */
if (NewPos >= H->TableSize)
NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
} else { /* 偶数次冲突 */
NewPos = CurrentPos - CNum * CNum / 4; /* 增量为-(CNum/2)^2 */
while (NewPos < 0)
NewPos += H->TableSize; /* 调整为合法地址 */
}
}
return NewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/
}
bool Insert(HashTable H, ElementType Key) {
Position Pos = Find(H, Key); /* 先检查Key是否已经存在 */
if (H->Cells[Pos].Info !=
Legitimate) { /* 如果这个单元没有被占，说明Key可以插入在此 */
H->Cells[Pos].Info = Legitimate;
H->Cells[Pos].Data = Key;
/*字符串类型的关键词需要 strcpy 函数!! */
return true;
} else {
printf("键值已存在");
return false;
}
}
#define KEYLENGTH 15 /* 关键词字符串的最大长度 */
typedef char ElementType[KEYLENGTH + 1]; /* 关键词类型用字符串 */
typedef int Index; /* 散列地址类型 */
/******** 以下是单链表的定义 ********/
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
/******** 以上是单链表的定义 ********/
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
List Heads; /* 指向链表头结点的数组 */
};
HashTable CreateTable(int TableSize) {
HashTable H;
int i;
H = (HashTable)malloc(sizeof(struct TblNode));
/* 保证散列表最大长度是素数，具体见代码5.3 */
H->TableSize = NextPrime(TableSize);
/* 以下分配链表头结点数组 */
H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode));
/* 初始化表头结点 */
for (i = 0; i < H->TableSize; i++) {
H->Heads[i].Data[0] = '\0';
H->Heads[i].Next = NULL;
}
return H;
}
Position Find(HashTable H, ElementType Key) {
Position P;
Index Pos;
Pos = Hash(Key, H->TableSize); /* 初始散列位置 */
P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
/* 当未到表尾，并且Key未找到时 */
while (P && strcmp(P->Data, Key))
P = P->Next;
return P; /* 此时P或者指向找到的结点，或者为NULL */
}
bool Insert(HashTable H, ElementType Key) {
Position P, NewCell;
Index Pos;
P = Find(H, Key);
if (!P) { /* 关键词未找到，可以插入 */
NewCell = (Position)malloc(sizeof(struct LNode));
strcpy(NewCell->Data, Key);
Pos = Hash(Key, H->TableSize); /* 初始散列位置 */
/* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
NewCell->Next = H->Heads[Pos].Next;
H->Heads[Pos].Next = NewCell;
return true;
} else { /* 关键词已存在 */
printf("键值已存在");
return false;
}
}
void DestroyTable(HashTable H) {
int i;
Position P, Tmp;
/* 释放每个链表的结点 */
for (i = 0; i < H->TableSize; i++) {
P = H->Heads[i].Next;
while (P) {
Tmp = P->Next;
free(P);
P = Tmp;
}
}
free(H->Heads); /* 释放头结点数组 */
free(H); /* 释放散列表结点 */
}编程习题
1.电话聊天狂人
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。
输入格式:
输入首先给出正整数$N(≤10^5)$，为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832输出样例:
13588625832 3思路
解法1 – 排序
第1步：读入最多$2\times 10^5$个电话号码，每个号码存为长度为11的字符串
第2步：按字符串非递减顺序排序
第3步：扫描有序数组，累计同号码出现的次数，并且更新最大次数
编程简单快捷 ，但无法拓展解决动态插入的问题
解法2 – 直接映射
第1步：创建有$2\times 10^{10}$个单元的整数数组，保证每个电话号码对应唯一的单元下标；数组初始化为0
第2步：对读入的每个电话号码，找到以之为下标的单元，数值累计1次
第3步：顺序扫描数组，找出累计次数最多的单元
编程简单快捷，动态插入快
下标超过了unsigned long
需要 $2\times 10^{10}\times 2\ bytes \approx 37GB$
为了$2\times 10^5$个号码扫描$2\times 10^{10}$个单元
解法3 – 带智商的散列
手机号码分为网络识别号 、地区编码、 用户号码三部分。
取后5为用于散列。
AC code
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KEYLENGTH 11 /* 关键词字符串的最大长度 */
#define MAXD 4
/* 关键词类型用字符串 */
typedef char ElementType[KEYLENGTH + 1];
typedef int Index; /* 散列地址类型 */
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
int Count;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable;
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
List Heads; /* 指向链表头结点的数组 */
};
#define MAXTABLESIZE 1000000
int Hash(int Key, int P) { /* 除留余数法法散列函数 */
return Key % P;
}
int NextPrime(int N) { /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
int i, p = (N % 2) ? N + 2 : N + 1; /*从大于N的下一个奇数开始 */
while (p <= MAXTABLESIZE) {
for (i = (int)sqrt(p); i > 2; i--)
if (!(p % i)) break; /* p不是素数 */
if (i == 2)
break; /* for正常结束，说明p是素数 */
else
p += 2; /* 否则试探下一个奇数 */
}
return p;
}
HashTable CreateTable(int TableSize) {
HashTable H;
int i;
H = (HashTable)malloc(sizeof(struct TblNode));
H->TableSize = NextPrime(TableSize);
H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode));
for (i = 0; i < H->TableSize; i++) {
H->Heads[i].Data[0] = '\0';
H->Heads[i].Next = NULL;
H->Heads[i].Count = 0;
}
return H;
}
Position Find(HashTable H, ElementType Key) {
Position P;
Index Pos;
/* 初始散列位置 */
Pos = Hash(atoi(Key + KEYLENGTH - MAXD), H->TableSize);
P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
/* 当未到表尾，并且Key未找到时 */
while (P && strcmp(P->Data, Key)) P = P->Next;
return P; /* 此时P或者指向找到的结点，或者为NULL */
}
int Insert(HashTable H, ElementType Key) {
Position P, NewCell;
Index Pos;
P = Find(H, Key);
if (!P) { /* 关键词未找到，可以插入 */
NewCell = (Position)malloc(sizeof(struct LNode));
strcpy(NewCell->Data, Key);
/* 初始散列位置 */
NewCell->Count = 1;
Pos = Hash(atoi(Key + KEYLENGTH - MAXD), H->TableSize);
/* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
NewCell->Next = H->Heads[Pos].Next;
H->Heads[Pos].Next = NewCell;
return 1;
} else { /* 关键词已存在 */
P->Count++;
return 0;
}
}
void ScanAndOutput(HashTable H) {
int i, MaxCnt = 0, PCnt = 0;
ElementType MinPhone;
List Ptr;
MinPhone[0] = '\0';
for (i = 0; i < H->TableSize; i++) { /* 扫描链表 */
Ptr = H->Heads[i].Next;
while (Ptr) {
if (Ptr->Count > MaxCnt) { /* 更新最大通话次数 */
MaxCnt = Ptr->Count;
strcpy(MinPhone, Ptr->Data);
PCnt = 1;
} else if (Ptr->Count == MaxCnt) {
PCnt++; /* 狂人计数 */
if (strcmp(MinPhone, Ptr->Data) > 0)
strcpy(MinPhone, Ptr->Data); /* 更新狂人的最小手机号码 */
}
Ptr = Ptr->Next;
}
}
printf("%s %d", MinPhone, MaxCnt);
if (PCnt > 1) printf(" %d", PCnt);
printf("\n");
}
void DestroyTable(HashTable H) {
int i;
Position P, Tmp;
/* 释放每个链表的结点 */
for (i = 0; i < H->TableSize; i++) {
P = H->Heads[i].Next;
while (P) {
Tmp = P->Next;
free(P);
P = Tmp;
}
}
free(H->Heads); /* 释放头结点数组 */
free(H); /* 释放散列表结点 */
}
int main() {
int N, i;
ElementType Key;
HashTable H;
scanf("%d", &N);
H = CreateTable(N * 2); /* 创建一个散列表 */
for (i = 0; i < N; i++) {
scanf("%s", Key);
Insert(H, Key);
scanf("%s", Key);
Insert(H, Key);
}
ScanAndOutput(H);
DestroyTable(H);
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample 小数据，狂人唯一 | 答案正确 | 12 | 34 ms | 316 KB |
| 1 | 小数据，多个狂人并列 | 答案正确 | 3 | 4 ms | 296 KB |
| 2 | 最大N，随机 | 答案正确 | 10 | 300 ms | 15928 KB |
2.Hashing
The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be $H(key)=key\%TSize$ where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers:$ MSize (≤10^4)$ and $N (≤MSize)$ which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-“ instead.
Sample Input:
4 4
10 6 4 15Sample Output:
0 1 4 -思路
简单的平方探测法，只需要正数，注意素数判断！
AC code
#include <math.h>
#include <stdio.h>
int MSize, N, num;
int Hash(int Key, int P) { /* 除留余数法散列函数 */
return Key % P;
}
int NextPrime(int N) {
if (N == 1) // 1不是素数
return 2;
int i, p = N % 2 ? N : N + 1;
while (1) {
for (i = sqrt(p); i >= 2; i--)
if (p % i == 0) break;
if (i == 1)
break;
else
p += 2;
}
return p;
}
int main() {
scanf("%d %d", &MSize, &N);
MSize = NextPrime(MSize);
int H[MSize];
for (int i = 0; i < MSize; i++) H[i] = 0;
for (int i = 0; i < N; i++) {
if (i) printf(" ");
scanf("%d", &num);
int Pos = Hash(num, MSize);
int temp = Pos;
if (H[temp] == 0) {
H[temp] = num;
printf("%d", Pos);
} else {
int flag = 0;
for (int j = 1; j <= MSize / 2; ++j) {
int pos = Hash(temp + j * j, MSize);
if (H[pos] == 0) {
flag = 1;
H[pos] = num;
printf("%d", pos);
break;
}
}
if (flag == 0) printf("-");
}
}
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample，有无法插入的 | 答案正确 | 12 | 4 ms | 196 KB |
| 1 | 最小值 | 答案正确 | 3 | 3 ms | 192 KB |
| 2 | 最大MSize，测试插入边界 | 答案正确 | 5 | 4 ms | 320 KB |
| 3 | 最大随机 | 答案正确 | 5 | 8 ms | 324 KB |
3.QQ帐户的申请与登陆
实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。
输入格式:
输入首先给出一个正整数$N(≤10^5)$，随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。
输出格式:
针对每条指令，给出相应的信息：
1）若新申请帐户成功，则输出“New: OK”；
2）若新申请的号码已经存在，则输出“ERROR: Exist”；
3）若老帐户登陆成功，则输出“Login: OK”；
4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；
5）若老帐户密码错误，则输出“ERROR: Wrong PW”。
输入样例:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com输出样例:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK思路
题不难，注意判断即可。说句题外话，用c++STL就是秒杀。
AC code
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXTABLESIZE 100000
typedef struct Q *QQ;
struct Q {
int ID;
char pwd[20];
QQ next;
};
typedef struct Q *List;
typedef struct TblNode *HashTable;
struct TblNode { //散列表节点定义
int TableSize; /* 表的最大长度 */
List Heads;
};
int NextPrime(int N) {
int i, p = (N % 2) ? N + 2 : N + 1;
while (p <= MAXTABLESIZE) {
/* for循环用来判断p是不是素数 */
for (i = (int)sqrt(p); i > 2; i--)
if (!(p % i)) break; /* p不是素数break */
if (i == 2)
break; /* p是素数 结束for循环 */
else
p += 2; /* P不是素数，p+2继续向后找 */
}
return p;
}
HashTable CreateTable(int TableSize) {
HashTable H;
int i;
H = (HashTable)malloc(sizeof(struct TblNode));
/* 保证散列表的最大长度是素数 */
H->TableSize = NextPrime(TableSize);
H->Heads = (QQ)malloc(H->TableSize * sizeof(struct Q));
for (i = 0; i < H->TableSize; i++) //初始化
{
H->Heads[i].ID = 0;
H->Heads[i].pwd[0] = '\0';
H->Heads[i].next = NULL;
}
return H;
}
int Hash(int key, int HashTableSize) { return key % HashTableSize; }
void New(HashTable H, int ID, char pwd[]) { //申请QQ
int pos;
QQ user;
pos = Hash(ID, H->TableSize);
user = H->Heads[pos].next;
while (user) {
if (user->ID == ID) //有相同的ID就退出循环
break;
else
user = user->next;
}
if (user == NULL) { //没有相同的ID，开始申请QQ
QQ NewNode = (QQ)malloc(sizeof(struct Q));
NewNode->ID = ID;
strcpy(NewNode->pwd, pwd);
NewNode->next = H->Heads[pos].next;
H->Heads[pos].next = NewNode;
printf("New: OK\n");
} else
printf("ERROR: Exist\n");
}
void Login(HashTable H, int ID, char pwd[]) { //登录QQ
int pos;
QQ user;
pos = Hash(ID, H->TableSize);
user = H->Heads[pos].next;
while (user) {
if (user->ID == ID) {
if (strcmp(user->pwd, pwd) == 0)
printf("Login: OK\n");
else
printf("ERROR: Wrong PW\n");
break;
} else
user = user->next;
}
if (user == NULL) printf("ERROR: Not Exist\n");
}
int main() {
int N, ID, TableSize;
char c, pwd[17];
scanf("%d", &N);
TableSize = NextPrime(N);
HashTable H = CreateTable(TableSize);
getchar();
for (int i = 0; i < N; i++) {
scanf("%c %d %s", &c, &ID, pwd);
if (c == 'N')
New(H, ID, pwd);
else
Login(H, ID, pwd);
getchar();
}
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample 全部5种输出信息 | 答案正确 | 10 | 4 ms | 324 KB |
| 1 | 最大表，全部是新申请，密码全部16位 | 答案正确 | 7 | 76 ms | 8900 KB |
| 2 | N和L指令各一半，随机交错。帐号随机，取到上下界。密码随机，取到上下界 | 答案正确 | 8 | 67 ms | 6856 KB |
STL
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
map<string, string> QQ;
int main() {
int n;
scanf("%d", &n);
getchar();
char cmd;
string id, pwd;
for (int i = 0; i < n; i++) {
cmd = getchar();
if (cmd == 'N') {
cin >> id >> pwd;
if (QQ.find(id) != QQ.end())
printf("ERROR: Exist\n");
else {
QQ[id] = pwd;
printf("New: OK\n");
}
} else if (cmd == 'L') {
cin >> id >> pwd;
if (QQ.find(id) != QQ.end()) {
if (QQ[id] == pwd)
printf("Login: OK\n");
else
printf("ERROR: Wrong PW\n");
} else
printf("ERROR: Not Exist\n");
}
getchar();
}
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample 全部5种输出信息 | 答案正确 | 10 | 3 ms | 312 KB |
| 1 | 最大表，全部是新申请，密码全部16位 | 答案正确 | 7 | 346 ms | 16832 KB |
| 2 | N和L指令各一半，随机交错。帐号随机，取到上下界。密码随机，取到上下界 | 答案正确 | 8 | 309 ms | 9268 KB |
4.Hashing - Hard Version
Given a hash table of size N, we can define a hash function $H(x)=x\%N$. Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers.
However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer $N (≤1000)$, which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.
Output Specification:
For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.
Sample Input:
11
33 1 13 12 34 38 27 22 32 -1 21Sample Output:
1 13 12 21 33 34 38 27 22 32思路
已知 $H(x) = x\%N $以及用线性探测解决冲突问题
先给出散列映射的结果，反求输入顺序
关键：当元素x被映射到H(x)位置，发现这个位置已经有y了，则y一定是在x之前被输入！
有拓扑排序内味。
AC code
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
int H[MAXN], NewH[MAXN], position[MAXN * MAXN];
int Find(int cell, int N) {
int pos;
pos = cell % N;
while (NewH[pos] != -1) {
++pos;
if (pos >= N) pos = pos % N;
}
return pos;
}
int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
int main() {
int N, i, cell, cnt = 0;
scanf("%d\n", &N);
for (i = 0; i != N; ++i) {
position[i] = -1;
NewH[i] = -1;
}
for (i = 0; i != N; ++i) {
scanf("%d", &H[i]);
if (H[i] >= 0) {
position[H[i]] = i;
++cnt;
}
}
qsort(H, N, sizeof(int), compare);
int pos, num = 0;
int Inserted[MAXN] = {0};
while (num < cnt) {
for (i = 0; i != N; ++i) {
if (H[i] >= 0 && !Inserted[i]) {
pos = Find(H[i], N);
if (pos == position[H[i]]) {
++num;
NewH[pos] = H[i];
Inserted[i] = 1;
printf("%d", H[i]);
if (num <= cnt - 1) printf(" ");
break;
}
}
}
}
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample 有并列初始、中间产生更小并列值，hash取到0和N-1 | 答案正确 | 18 | 16 ms | 292 KB |
| 1 | 全部一次放好 | 答案正确 | 4 | 17 ms | 284 KB |
| 2 | 最大N，但是只有少数值，有非-1的空位 | 答案正确 | 2 | 16 ms | 312 KB |
| 3 | 最小N | 答案正确 | 2 | 8 ms | 316 KB |
| 4 | 最大N随机 | 答案正确 | 4 | 9 ms | 428 KB |
