更新时间:2021-10-08 10:29:42 来源:极悦 浏览930次
哈希表数据结构以键值对的形式存储元素,其中
键- 用于索引值的唯一整数
值- 与键关联的数据。
在哈希表中,使用键处理新索引。并且,对应于该键的元素存储在索引中。这个过程称为散列。
让 克 成为钥匙和小时(x) 是一个哈希函数。
这里, h(k) 会给我们一个新的索引来存储链接的元素克.
当哈希函数为多个键生成相同的索引时,就会出现冲突(该索引中存储什么值)。这称为 哈希冲突。
我们可以使用以下技术之一解决哈希冲突。
通过链接解决冲突
开放寻址:线性/二次探测和双散列
1. 通过链接解决冲突
在链式中,如果一个哈希函数为多个元素生成相同的索引,则这些元素通过使用双向链表存储在相同的索引中。
如果j是多个元素的插槽,则它包含一个指向元素列表头部的指针。如果不存在元素,则j包含NIL。
操作伪代码
chainedHashSearch(T, k)
return T[h(k)]
chainedHashInsert(T, x)
T[h(x.key)] = x //insert at the head
chainedHashDelete(T, x)
T[h(x.key)] = NIL
线性探测的问题是填充了一组相邻的插槽。插入新元素时,必须遍历整个簇。这增加了对哈希表执行操作所需的时间。
ii. 二次探测
它的工作原理类似于线性探测,但通过使用以下关系增加了插槽之间的间距(大于 1)。
h(k, i) = (h′(k) + c1i + c2i2) mod m在哪里,
c1和c2是正辅助常数,
i = {0, 1, ….}
如果在应用散列函数后发生冲突h(k),则计算另一个散列函数以查找下一个时隙。
h(k, i) = (h1(k) + ih2(k)) mod m
一个好的散列函数可能无法完全防止冲突,但它可以减少冲突的数量。
在这里,我们将研究不同的方法来找到一个好的哈希函数
1.除法
如果k是一个键并且m是哈希表的大小,则哈希函数h()计算如下:
h(k) = k mod m例如,如果一个哈希表的大小10和k = 112然后h(k) = 112国防部10 = 2。的值m不能是 的幂2。这是因为2二进制格式的的幂是10, 100, 1000, …. 当我们找到 时k mod m,我们总是会得到低阶 p 位。
如果 m = 22, k = 17,则 h(k) = 17 mod 22 = 10001 mod 100 = 01
如果 m = 23, k = 17,则 h(k) = 17 mod 22 = 10001 mod 100 = 001
如果 m = 24, k = 17,则 h(k) = 17 mod 22 = 10001 mod 100 = 0001
如果 m = 2p,则 h(k) = m 的 p 个低位
2. 乘法
h(k) = ⌊m(kA mod 1)⌋在哪里,
kA mod 1给出小数部分kA,
⌊ ⌋ 给出底值
A是任意常数。的值A介于 0 和 1 之间。但是,≈ (√5-1)/2Knuth会建议最佳选择。
3. 通用哈希
在通用散列中,散列函数是随机选择的,与密钥无关。
// Java program to demonstrate working of HashTable
import java.util.*;
class HashTable {
public static void main(String args[])
{
Hashtable<Integer, Integer>
ht = new Hashtable<Integer, Integer>();
ht.put(123, 432);
ht.put(12, 2345);
ht.put(15, 5643);
ht.put(3, 321);
ht.remove(12);
System.out.println(ht);
}
}
哈希表在何处实现
需要恒定时间查找和插入
密码应用
需要索引数据
大家如果想了解更多相关知识,不妨来关注一下极悦的Java极悦在线学习,里面有更多的知识可以学习,从基础到进阶的都有,很适合零基础的小伙伴学习哦。
0基础 0学费 15天面授
Java就业班有基础 直达就业
业余时间 高薪转行
Java在职加薪班工作1~3年,加薪神器
工作3~5年,晋升架构
提交申请后,顾问老师会电话与您沟通安排学习