哈希数据结构表

哈希表数据结构以键值对的形式存储元素，其中

键- 用于索引值的唯一整数

值- 与键关联的数据。

散列(散列函数)

在哈希表中，使用键处理新索引。并且，对应于该键的元素存储在索引中。这个过程称为散列。

让 克 成为钥匙和小时(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示例

// 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); 
  } 
} 

哈希表的应用

哈希表在何处实现

需要恒定时间查找和插入

密码应用

需要索引数据

大家如果想了解更多相关知识，不妨来关注一下赢咖4的Java赢咖4在线学习，里面有更多的知识可以学习，从基础到进阶的都有，很适合零基础的小伙伴学习哦。