算法（C语言）-hash查询-学习笔记07

文章目录

• 1. 直接寻址表（Direct-address Tables）
• 2. 散列表
• • • 解决冲突1：链接法
    • • 1. 链接发的介绍
      • 2. 链接法散列的分析（查找一个给定关键字的时间）
• 3. 散列函数
• • 3.1 除法散列法
  • 3.2 乘法散列法
  • 3.3 全域散列法
• 4. 开放寻址法（open addressing）
• • 4.1 介绍
  • 4.2 三种计算开放寻址法的探查序列
  • 4.3 开放寻址散列的分析（探查的期望次数）
• 5. 完全散列（perfect hashing）
• 6. 简单用c实现

正好以前上算法课的时候有做过hash的笔记，直接把笔记搬运过来了，可能和具体实现有点不一样，但道理是一样的。当时上课的书是算法导论
所有代码实现：Tian-hy/c_ds

1. 直接寻址表（Direct-address Tables）

直接寻址表，记为 T [ 0... m − 1 ] T[0...m-1] T[0...m−1], 其中每个位置称为槽（Slot），对应全域U的一个关键字（Key），key指向satellite data，若没有key为k的satellite data，则 T [ k ] = N I L T[k]=NIL T[k]=NIL。

---

O ( 1 ) O(1) O(1)

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

O ( 1 ) O(1) O(1)

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

O ( 1 ) O(1) O(1)

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

---

优点	将对象直接存放在表的槽中，从而节约空间
	只需要知道下标就可以找到元素，不必存储关键字。然而不存储关键字，就必须用某种方法确定槽是否为空。
缺点	易造成表的空间不够或空间被浪费

2. 散列表

• 在直接寻址下，具有关键字k的元素被放到槽k中。在散列的方式下，该元素被放到 h ( k ) h(k) h(k)中；即利用散列函数（hash function）h，计算出关键字k的槽的位置。

​ h : U → { 0 , 1 , . . . , m − 1 } h:U \rightarrow \{0, 1, ..., m-1\} h:U→{0,1,...,m−1}

• 读作：关键字k的元素被散列到槽 h ( k ) h(k) h(k)上，或 h ( k ) h(k) h(k)是关键字k的散列值
• 尽管尽可能的使h随机，但是难免出现冲突。

---

优点：

1. 散列表的存储需求只需要 θ ( ∣ K ∣ ) \theta (|K|) θ(∣K∣)，且查找一个元素任然只需要 O ( 1 ) O(1) O(1)

缺点：

1. O ( 1 ) O(1) O(1)是平均情况时间，对直接寻址表来说是最坏情况时间
2. 会出现冲突（collision）

---

解决冲突1：链接法 1. 链接发的介绍

• 在链接法中，把散列到同一槽中的所有元素都放在一个链表中。槽j中有一个指针，指向散列到j的元素的链表的表头；弱不存在这样的元素，则指向NIL

---

Insert: O ( 1 ) O(1) O(1)，插入相较于其他 *** 作要稍微快一点，因为在此假设插入的元素没有出现在表中；若要检查x是否在表中需要付出额外代价，需要执行一个search来查找。

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

Search: O ( n ) O(n) O(n)，查找方法的最坏情况运行时间与表的长度成正比。

​ O ( 1 ) O(1) O(1)，期望时间。（ O ( 1 + α ) O(1+\alpha) O(1+α)，而 α \alpha α为 O ( 1 ) O(1) O(1)）

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

Delete:

双向链表： O ( 1 ) O(1) O(1)，因为我们输入的是x，而x包含x.key，所以无需搜索就可以直接找到x的位置，叫x.prev的元素指向x.next的元素，即可完成删除 *** 作。

单向链表： O ( n ) O(n) O(n)，我们可以直接找到x.key的位置，但是因为是单向链表所以无法直接找到x.prev，也就是说需要遍历链表找到x.prev，再将前一个元素的key指向后一个元素的key，完成删除 *** 作，渐进运行时间与search相同。

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

---

2. 链接法散列的分析（查找一个给定关键字的时间）

• 最坏情况下查找的时间为 θ ( n ) \theta(n) θ(n)

• 散列的平均性能依赖于所选取的散列函数h

• Assume：

  1. 放n个元素、具有m个槽位的散列表T，定义装载因子（load factor） α = n / m \alpha =n/m α=n/m。

  2. 简单均匀散列（simple uniform hashing）
     对于 j = 0 , 1 , . . . , m − 1 j=0, 1, ..., m-1 j=0,1,...,m−1，列表 T [ j ] T[j] T[j]的长度用 n j n_j nj​来表示，于是有
     n = n 0 + n 1 + . . . + n m − 1 n=n_0+n_1+...+n_{m-1} n=n0​+n1​+...+nm−1​
     n j n_j nj​的期望长度为 E [ n j ] = α = n / m E[n_j]=\alpha=n/m E[nj​]=α=n/m。

  3. 定义：
     查找不成功，表中没有一个元素的关键字为k
     查找成功，成功找到关键字为k的元素

---

定理11.1: 在简单均匀散列的假设下，对于用链接法解决冲突的散列表，一次不成功search的avg time为 θ ( 1 + α ) \theta(1+\alpha) θ(1+α)。

定理11.2: 在简单均匀散列的假设下，对于用链接法解决冲突的散列表，一次成功查询的avg time为 θ ( 1 + α ) \theta(1+\alpha) θ(1+α)。

结论: 若散列表中槽数与表中的元素成正比，全部字典 *** 作平均情况下都可以在 O ( 1 ) O(1) O(1)的时间内完成

3. 散列函数

介绍散列的三种具体方法：两种启发式方法（乘法与除法进行散列）与一种利用随机技术来提供可证明的良好性能（全域散列，universal hashing）

• 一种好的方法导出的散列值，在某种程度上应独立与数据可能存在的任何模式，甚至很接近的关键字要被散列到截然不同的散列值上。

• 将关键字转换为自然数

  将字符串转换为ASCII码，随后以128为基数来表示。

  举例： p t → ( p = 112 , t = 116 ) → p t = ( 112 ∗ 128 ) + 116 = 14452 pt\rightarrow (p=112, t=116) \rightarrow pt=(112*128)+116=14452 pt→(p=112,t=116)→pt=(112∗128)+116=14452

---

3.1 除法散列法

• 通过取k除以m的余数，将关键字k映射到m个槽上。 h ( k ) = k   m o d   m h(k)=k\ mod\ m h(k)=k mod m
• 避免取2的幂，若取则h(k)就是k的p个最低为数字；或者当k是一个按基数 2 k 2^k 2k表示的字符串时，选择 m = 2 p − 1 m=2^p-1 m=2p−1是一个糟糕的选择。因为排列k的个字符并不会改变其散列值。

3.2 乘法散列法

1. 用关键字k乘上常数A（ 0 ≤ A ≤ 1 0\le A\le 1 0≤A≤1），并提取KA的小数部分

2. 用m（ m = 2 p , p → i n t < 32   o r   64 m=2^p, p\rightarrow int<32\ or\ 64 m=2p,p→int<32 or 64）乘这个值在向下取整
   h ( k ) = ⌊ m ( k A   m o d   1 ) ⌋ h(k)=\lfloor m(kA\ mod \ 1)\rfloor h(k)=⌊m(kA mod 1)⌋

3.3 全域散列法

• 无论输入是否相同都能具有较好的平均情况性能。
• 设KaTeX parse error: Can't use function '\H' in math mode at position 1: \̲H̲为一组有限散列函数（finite collection of hash function），它将给定的关键字全域U映射到｛0, 1, …, m-1｝中，这样一个函数称为全域的。

定理11.3：如果h选自一组全域散列函数，将n个关键字散列到一个大小为m的表T中，并用链接法解决冲突。如果关键字k不在表中，则k被散列到其中的链表的期望长度 E [ n h ( k ) ] ≤ α = n / m E[n_{h(k)}]\le \alpha =n/m E[nh(k)​]≤α=n/m（因为不包含k所以没有和后面一样 α + 1 \alpha +1 α+1）；若关键字k在表中，则包含关键字k的链表的期望长度 E [ n h ( k ) ] ≤ 1 + α E[n_{h(k)}]\le1+\alpha E[nh(k)​]≤1+α（149页）

定理11.4：m个槽且初始为空的表，采用全域散列法和链接法，需要 θ ( n ) \theta(n) θ(n)的期望时间来处理包含了n个INSERT，SEARCH和DELETE的 *** 作序列，其中该序列包含了 O ( m ) O(m) O(m)个INSERT *** 作。（注： n = O ( m ) n=O(m) n=O(m)）(150页)

• 设计一个全域散列函数类

  Assume：p是一个素数，一共有m个槽， a ∈ Z p ∗ = { 1 , 2 , . . . , p − 1 } , b ∈ Z p = { 0 , 1 , . . . , p − 1 } a\in \Z_p^*=\{1, 2, ..., p-1\}, b\in \Z_p=\{0, 1, ..., p-1\} a∈Zp∗​={1,2,...,p−1},b∈Zp​={0,1,...,p−1}

  ​ h a b ( k ) = ( ( a k + b )   m o d   p )   m o d   m h_{ab}(k)=((ak+b)\ mod\ p)\ mod \ m hab​(k)=((ak+b) mod p) mod m

  所有这样的散列函数构成的函数簇为：（a有p-1种选择，b有p种选择，该函数簇共有p(p-1)种选择）
  H p m = { h a b : a ∈ Z p ∗ , b ∈ Z p } H_{pm}=\{h_{ab}: a\in \Z_p^*, b\in \Z_p\} Hpm​={hab​:a∈Zp∗​,b∈Zp​}

定理11.5：由上述两个公式所定义的散列函数簇是全域的。（150页）

4. 开放寻址法（open addressing） 4.1 介绍

• 与链接法不同，所有元素都需要存入表中。因此装载因子 α ≤ 1 \alpha \le 1 α≤1，若想齐大于1可以在最后一个元素中加入链表
• 优点不用指针，节约空间，可以在同等空间中加入更多的槽，减少冲突，提高效率
• 若想要插入一个元素需要不停的探查（probe）直到找到NIL位置
• 散列函数为 h : U x { 0 , 1 , . . . , m − 1 } → { 0 , 1 , . . , m − 1 } h:Ux\{0, 1, ..., m-1\} \rightarrow \{0, 1, .., m-1\} h:Ux{0,1,...,m−1}→{0,1,..,m−1}
• 对每一个关键字k使用开放寻址法的探查序列（probe sequence） < h ( k , 0 ) , . . . , h ( k , m − 1 ) > <h(k,0),...,h(k,m−1)>

---

HASH-INSERT(T, k)
i=0
repeat
	j = h(k, i)
	if T[j] == NIL
		T[j] = k
		return j
    else i = i+1
until i==m
error "hash table overflow"

HASH-SEARCH(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

若要删除用链接法，因为如果引入delete标志后，虽然可以删除，但是无法用装载因子进行分析了。

---

4.2 三种计算开放寻址法的探查序列

1. 简介：

   1. 难以实现的均匀散列（uniform hashing）每个关键字的探查序列等可能地为<0, 1, …, m-1>的 m! 种排列中的任一种
   2. 辅助散列函数（auxiliary hash function）为一个普通的散列函数 h ′ : U → { 0 , 1 , . . . , m − 1 } h':U \rightarrow \{0, 1, ..., m-1\} h′:U→{0,1,...,m−1}

2. 线性探查（linear probing）

   1. 散列函数： h ( k , i ) = ( h ′ ( k ) + i )   m o d   m ,   i = 0 , 1 , . . . , m − 1 h(k,i)=(h'(k)+i)\ mod \ m, \ i=0,1,...,m-1 h(k,i)=(h′(k)+i) mod m, i=0,1,...,m−1
   2. 探查顺序： T [ h ′ ( k ) ] , T [ h ′ ( k ) + 1 ] , . . . , T [ m − 1 ] , T [ 0 ] , T [ 1 ] , . . . , T [ h ′ ( k ) − 1 ] T[h'(k)], T[h'(k)+1], ...,T[m-1],T[0],T[1],...,T[h'(k)-1] T[h′(k)],T[h′(k)+1],...,T[m−1],T[0],T[1],...,T[h′(k)−1]
   3. 初始探查位置决定了整个序列，故只有m种不同的探查序列。
   4. 一次群集（primary clustering） 问题：平均查找时间随着连续被占用的槽增加而增加。若一个空槽前有i个槽被占用，那下一次占用i的概率为 i + 1 m \frac{i+1}{m} mi+1​。连续被占用的槽会越来越长。

3. 二次探查（quadratic probing）
   1. 散列函数： h ( k , i ) = ( h ′ ( k ) + c 1 i + c 2 i 2 )   m o d   m ,   i = 0 , 1 , . . . , m − 1 h(k,i)=(h'(k)+c_1i+c_2i^2)\ mod \ m, \ i=0,1,...,m-1 h(k,i)=(h′(k)+c1​i+c2​i2) mod m, i=0,1,...,m−1
   2. 比线性探查好，但是为了充分利用散列表， c 1 , c 2 , m c_1, c_2, m c1​,c2​,m要受限制。
   3. 若初始位置相同，那么探查序列也相同，m种探查序列，这一性质导致轻度群集
   ∵ h ( k 1 , 0 ) = h ( k 2 , 0 ) ∴ h ( k 1 , i ) = h ( k 2 , i ) \because h(k_1,0)=h(k_2,0) \therefore h(k_1,i)=h(k_2,i) ∵h(k1​,0)=h(k2​,0)∴h(k1​,i)=h(k2​,i)

4. 双重探查（double hashing）（最好的方法）

   1. 散列函数： h ( k , i ) = ( h 1 ( k ) + i h 2 ( k ) )   m o d   m ,   i = 0 , 1 , . . . , m − 1 h(k,i)=(h_1(k)+ih_2(k))\ mod \ m, \ i=0,1,...,m-1 h(k,i)=(h1​(k)+ih2​(k)) mod m, i=0,1,...,m−1， h 1 ( k ) , h 2 ( k ) h_1(k), h_2(k) h1​(k),h2​(k)均为辅助散列函数
   2. 探查顺序： T [ h 1 ( k ) ] , T [ ( h 1 ( k ) + h 2 ( k ) )   m o d   m ] , . . . T[h_1(k)], T[(h_1(k)+h_2(k))\ mod \ m], ... T[h1​(k)],T[(h1​(k)+h2​(k)) mod m],...
   3. 要求： h 2 ( k ) h_2(k) h2​(k)需要与表的大小m互素。
      技巧：
      1. m为2的幂， h 2 h_2 h2​的值总为奇。
      2. m为素数， h 2 h_2 h2​的值 ≤ m \le m ≤m
      3. 取别的也行，但是难找
   4. 相比于线性探查与二次探查只用到了 θ ( m ) \theta(m) θ(m)种探查序列，双重探查用到了 θ ( m 2 ) \theta(m^2) θ(m2)种探查序列，更接近理想的均匀散列的性能。

4.3 开放寻址散列的分析（探查的期望次数）

• Define：装载因子 α = n / m \alpha=n/m α=n/m， ∵ n ≤ m ∴ α ≤ 1 \because n\le m \therefore \alpha \le 1 ∵n≤m∴α≤1
• Assume: 均匀散列
• Analyze：用开放寻址法来进行散列是探查的期望次数

定理11.6: α = n / m ≤ 1 \alpha=n/m\le 1 α=n/m≤1的均匀散列的开放寻址散列表，则一次不成功的查找，其期望的探查次数至多为 1 / ( 1 − α ) 1/(1-\alpha) 1/(1−α)。

​ 结论： 若 α \alpha α是常数，一次不成功的运行时间是O(1)。若半满 α = 0.5 ⇒ E [ X ] = 2 \alpha=0.5 \Rightarrow E[X]=2 α=0.5⇒E[X]=2；若 α = 0.9 ⇒ E [ X ] = 10 \alpha=0.9 \Rightarrow E[X]=10 α=0.9⇒E[X]=10

定理11.7: 均匀散列，平均情况下，向 α \alpha α的开放寻址散列表中插入一个元素至多需要 1 / ( 1 − α ) 1/(1-\alpha) 1/(1−α)次探查。

定理11.8: α < 1 \alpha<1 α<1的均匀散列的开放寻址散列表，一次成功查找中的探查期望数至多为 1 α ln ⁡ 1 1 − α \frac{1}{\alpha}\ln\frac{1}{1-\alpha} α1​ln1−α1​。

​结论：若散列表是半满的探查的期望数小于1.387，若散列表是90%满的探查的期望数小于2.559

5. 完全散列（perfect hashing）

• 完全散列的平均性能最好。只要关键字集合是**静态（static）时，最坏情况也能提供O(1)**次访问完成。

• 采用两级的散列方法来设计完全散列，在每一级上采用全域散列。

• 在第一级上采用全域散列，若出现冲突，运用二级全域散列。

• 为了二级散列不出现冲突， S j S_j Sj​的散列大小为 m j = n j 2 ( + 3 ) ， + 3 m_j=n_j^2(+3)，+3 mj​=nj2​(+3)，+3是为了增加存储二级全域散列的m，a与b。

结论： 出现冲突的概率<1/2，二次散列表所需的存储总量的期望值<2n，且总量 ≥ 4 n \ge4n ≥4n的概率 < 1 / 2 <1/2 <1/2。所以多试几次就能得到较优解。

分析过程：

定理11.9：全域散列函数中随机选出散列函数h，将n个关键字存储在大小为 m = n 2 m=n^2 m=n2的散列表中，出现冲突的概率<0.5。

定理11.10: 全域散列函数中随机选出散列函数h，将n个关键字存储在大小为 m = n m=n m=n的散列表中，则有 E [ ∑ j = 0 m − 1 n j 2 ] < 2 n E[\sum_{j=0}^{m-1}n_j^2]<2n E[∑j=0m−1​nj2​]<2n， n j n_j nj​为散列到槽j中的关键词字数。

推论11.11：全域散列函数中随机选出散列函数h，将n个关键字存储在大小为 m = n m=n m=n的散列表中，并将每个二次散列表的大小设置为 m j = n j 2 ， ( j = 0 , 1 , . . . , m − 1 ) m_j=n_j^2，(j=0,1,...,m-1) mj​=nj2​，(j=0,1,...,m−1)，存储二次散列表所需的存储总量的期望值<2n。

推论11.12：全域散列函数中随机选出散列函数h，将n个关键字存储在大小为 m = n m=n m=n的散列表中，并将每个二次散列表的大小设置为 m j = n j 2 ， ( j = 0 , 1 , . . . , m − 1 ) m_j=n_j^2，(j=0,1,...,m-1) mj​=nj2​，(j=0,1,...,m−1)，存储总量 ≥ \ge ≥ 4n的概率<0.5。

6. 简单用c实现

• 用最大质数的余数取地址，冲突用链表解决
• hash.h

#ifndef _HASH_H_
#define _HASH_H_

#define N 15

typedef int data_t;
typedef struct node{
	data_t key;
	data_t value;
	struct node *next;
}listnode, *linklist;

typedef struct{
	listnode data[N];
}hash;

hash *hash_create();
int hash_append(hash *ht, data_t key);
linklist hash_search(hash *ht, data_t key);

#endif

• hash.c

#include 
#include 
#include 
#include "hash.h"

hash * hash_create() {
	hash * HT;

	if ((HT = (hash *)malloc(sizeof(hash))) == NULL) {
		printf("malloc failed\n");
		return NULL;
	}

	memset(HT, 0, sizeof(hash));

	return HT;
}

int hash_insert(hash *HT, datatype key) {
	linklist p, q;

	if (HT == NULL) {
		printf("HT is NULL\n");
		return -1;
	}

	if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
		printf("malloc failed\n");
		return -1;
	}
	p->key = key;
	p->value = key % N;
	p->next = NULL;

	q = &(HT->data[key % N]);

	while (q->next && q->next->key < p->key ) {
		q = q->next;
	}

	p->next = q->next;
	q->next = p;

	return 0;

}

linklist  hash_search(hash *HT, datatype key) {
	linklist p;

	if (HT == NULL) {
		printf("HT is NULL\n");
		return NULL;
	}

	p = &(HT->data[key % N]);

	while (p->next && p->next->key != key) {
		p = p->next;
	}

	if (p->next == NULL) {
		return NULL;
	} else {
		printf("found\n");
		return p->next;
	}
}