1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 1.开放定址法: 一旦发生冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入
Hi = (H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列;di可有下列三种取法:
1.di=1,2,3,…, m-1,称为线性探测再散列;
缺点: 造成大量元素在相邻的散列地址上"聚集",大大降低查找效率
2.di=1^2, -(1^2), 2^2, -(2^2), 3^2, …, ±(k^2),(k<=m/2)，称为二次探测再散列；
优点: 避免出现"堆积"问题。
缺点: 不能探测到散列表上的所有单元,但至少能探测到一半单元
3.di=伪随机数序列,称为伪随机探测再散列。
缺点: 用同样的随机种子，将得到相同的数列。
缺点:
1.存储记录的数目不能超过桶数组的长度,如果超过就需要扩容,而扩容会导致某次操作的时间成本飙升,这在实时或者交互式应用中可能会是一个严重的缺陷
2.使用探测序列,有可能其计算的时间成本过高,导致哈希表的处理性能降低
3.由于记录是存放在桶数组中的,而桶数组必然存在空槽,所以当记录本身尺寸(size)很大并且记录总数规模很大时,空槽占用的空间会导致明显的内存浪费
4.删除记录时,比较麻烦;比如需要删除记录a,记录b是在a之后插入桶数组的,但是和记录a有冲突,是通过探测序列再次跳转找到的地址,所以如果直接删除a,a的位置变为空槽,而空槽是查询记录失败的终止条件,这样会导致记录b在a的位置重新插入数据前不可见,所以不能直接删除a,而是设置删除标记.这就需要额外的空间和操作
2.再散列函数法: 在同义词产生地址冲突时就换用另一个散列函数计算散列地址,直到碰撞不再发生
优点: 不易产生"聚集"
缺点: 增加了计算时间
3.链地址法: 将所有关键字为同义词的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针
优点:
1.对于记录总数频繁可变的情况,处理的比较好(也就是避免了动态调整的开销)
2.由于记录存储在结点中,而结点是动态分配,不会造成内存的浪费,所以尤其适合那种记录本身尺寸(size)很大的情况,因为此时指针的开销可以忽略不计了
3.删除记录时,比较方便,直接通过指针操作即可
缺点:
1.存储的记录是随机分布在内存中的,在查询记录时,相比结构紧凑的数据类型(比如数组),哈希表的跳转访问会带来额外的时间开销
2.如果所有的key-value对是可以提前预知,并之后不会发生变化时(即不允许插入和删除),可以人为创建一个不会产生冲突的完美哈希函数(perfect hash function),此时封闭散列的性能将远高于开放散列
使用:
HashMap使用了链地址法解决hash值相同的冲突
4.公共溢出区法: 为所有冲突的关键字记录建立一个公共的溢出区来存放;在查找时,对给定关键字通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表进行顺序查找.如果相对于基本表而言,在有冲突的数据很少的情况下,公共溢出区的结构对查找性能来说是非常高的
|
