- 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实现
1. 直接寻址表(Direct-address Tables)正好以前上算法课的时候有做过hash的笔记,直接把笔记搬运过来了,可能和具体实现有点不一样,但道理是一样的。当时上课的书是算法导论
所有代码实现:Tian-hy/c_ds
直接寻址表,记为 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
优点 | 将对象直接存放在表的槽中,从而节约空间 |
只需要知道下标就可以找到元素,不必存储关键字。然而不存储关键字,就必须用某种方法确定槽是否为空。 | |
缺点 | 易造成表的空间不够或空间被浪费 |
- 在直接寻址下,具有关键字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随机,但是难免出现冲突。
优点:
- 散列表的存储需求只需要 θ ( ∣ K ∣ ) \theta (|K|) θ(∣K∣),且查找一个元素任然只需要 O ( 1 ) O(1) O(1)
缺点:
- O ( 1 ) O(1) O(1)是平均情况时间,对直接寻址表来说是最坏情况时间
- 会出现冲突(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:
-
放n个元素、具有m个槽位的散列表T,定义装载因子(load factor) α = n / m \alpha =n/m α=n/m。
-
简单均匀散列(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。 -
定义:
查找不成功,表中没有一个元素的关键字为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的个字符并不会改变其散列值。
-
用关键字k乘上常数A( 0 ≤ A ≤ 1 0\le A\le 1 0≤A≤1),并提取KA的小数部分
-
用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)⌋
- 无论输入是否相同都能具有较好的平均情况性能。
- 设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
)
>
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 三种计算开放寻址法的探查序列
-
简介:
- 难以实现的均匀散列(uniform hashing)每个关键字的探查序列等可能地为<0, 1, …, m-1>的 m! 种排列中的任一种
- 辅助散列函数(auxiliary hash function)为一个普通的散列函数 h ′ : U → { 0 , 1 , . . . , m − 1 } h':U \rightarrow \{0, 1, ..., m-1\} h′:U→{0,1,...,m−1}
-
线性探查(linear probing)
- 散列函数: 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
- 探查顺序: 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]
- 初始探查位置决定了整个序列,故只有m种不同的探查序列。
- 一次群集(primary clustering) 问题:平均查找时间随着连续被占用的槽增加而增加。若一个空槽前有i个槽被占用,那下一次占用i的概率为 i + 1 m \frac{i+1}{m} mi+1。连续被占用的槽会越来越长。
-
二次探查(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)+c1i+c2i2) 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) -
双重探查(double hashing)(最好的方法)
- 散列函数: 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)均为辅助散列函数
- 探查顺序: 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],...
- 要求:
h
2
(
k
)
h_2(k)
h2(k)需要与表的大小m互素。
技巧:- m为2的幂, h 2 h_2 h2的值总为奇。
- m为素数, h 2 h_2 h2的值 ≤ m \le m ≤m
- 取别的也行,但是难找
- 相比于线性探查与二次探查只用到了 θ ( m ) \theta(m) θ(m)种探查序列,双重探查用到了 θ ( m 2 ) \theta(m^2) θ(m2)种探查序列,更接近理想的均匀散列的性能。
- 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} α1ln1−α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−1nj2]<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;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)