一篇让你学会哈希表(散列)

一、篇让前言

哈希表的哈希历史

哈希散列的想法在不同的地方独立出现。1953 年 1 月，表散汉斯·彼得·卢恩 ( Hans Peter Luhn ) 编写了一份IBM内部备忘录，篇让其中使用了散列和链接。哈希开放寻址后来由 AD Linh 在 Luhn 的表散论文上提出。大约在同一时间，篇让IBM Research的哈希Gene Amdahl、Elaine M. McGraw、表散Nathaniel Rochester和Arthur Samuel为IBM 701汇编器实现了散列。篇让 线性探测的哈希开放寻址归功于 Amdahl，尽管Ershov独立地有相同的表散想法。“开放寻址”一词是篇让由W. Wesley Peterson在他的文章中创造的，该文章讨论了大文件中的哈希搜索问题。

二、表散哈希数据结构

哈希表的存在是为了解决能通过O(1)时间复杂度直接索引到指定元素。

这是什么意思呢？通过我们使用数组存放元素，都是按照顺序存放的，香港云服务器当需要获取某个元素的时候，则需要对数组进行遍历，获取到指定的值。如图所示；

而这样通过循环遍历比对获取指定元素的操作，时间复杂度是O(n)，也就是说如果你的业务逻辑实现中存在这样的代码是非常拉胯的。那怎么办呢？这就引入了哈希散列表的设计。

在计算机科学中，一个哈希表（hash table、hash map）是一种实现关联数组的抽象数据结构，该结构将键通过哈希计算映射到值。

也就是说我们通过对一个 Key 值计算它的哈希并与长度为2的n次幂的数组减一做与运算，计算出槽位对应的索引，将数据存放到索引下。那么这样就解决了当获取指定数据时，只需要根据存放时计算索引ID的高防服务器方式再计算一次，就可以把槽位上对应的数据获取处理，以此达到时间复杂度为O(1)的情况。如图所示；

哈希散列虽然解决了获取元素的时间复杂度问题，但大多数时候这只是理想情况。因为随着元素的增多，很可能发生哈希冲突，或者哈希值波动不大导致索引计算相同，也就是一个索引位置出现多个元素情况。如图所示；

当李二狗、拎瓢冲都有槽位的下标索引03的 叮裆猫 发生冲突时，情况就变得糟糕了，因为这样就不能满足O(1)时间复杂度获取元素的诉求了。

那么此时就出现了一系列解决方案，包括；HashMap 中的拉链寻址 + 红黑树、扰动函数、负载因子、ThreadLocal 的开放寻址、合并散列、杜鹃散列、跳房子哈希、罗宾汉哈希等各类数据结构设计。源码下载让元素在发生哈希冲突时，也可以存放到新的槽位，并尽可能保证索引的时间复杂度小于O(n)

三、实现哈希散列

哈希散列是一个非常常见的数据结构，无论是我们使用的 HashMap、ThreaLocal 还是你在刷题中位了提升索引效率，都会用到哈希散列。

只要哈希桶的长度由负载因子控制的合理，每次查找元素的平均时间复杂度与桶中存储的元素数量无关。另外许多哈希表设计还允许对键值对的任意插入和删除，每次操作的摊销固定平均成本。

好，那么介绍了这么多，小傅哥带着大家做几个关于哈希散列的数据结构，通过实践来了解会更加容易搞懂。

源码地址：https://github.com/fuzhengwei/java-algorithms (opens new window)-Java 算法与数据结构本章源码：https://github.com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/queue/DelayQueue.java(opens new window)1. 哈希碰撞

说明：通过模拟简单 HashMap 实现，去掉拉链寻址等设计，验证元素哈新索引位置碰撞。

public class HashMap01implements Map{

private final Object[] tab = new Object[8];

@Override

public void put(K key, V value) {

int idx = key.hashCode() & (tab.length - 1);

tab[idx] = value;

}

@Override

public V get(K key) {

int idx = key.hashCode() & (tab.length - 1);

return (V) tab[idx];

}

}

HashMap01 的实现只是通过哈希计算出的下标，散列存放到固定的数组内。那么这样当发生元素下标碰撞时，原有的元素就会被新的元素替换掉。

测试

@Test

public void test_hashMap01() {

Mapmap = new HashMap01<>();

map.put("01", "花花");

map.put("02", "豆豆");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

// 下标碰撞

map.put("09", "蛋蛋");

map.put("12", "苗苗");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

}

06:58:41.691 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

06:58:41.696 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：苗苗

Process finished with exit code 0通过测试结果可以看到，碰撞前 map.get("01") 的值是花花​，两次下标索引碰撞后存放的值则是苗苗这也就是使用哈希散列必须解决的一个问题，无论是在已知元素数量的情况下，通过扩容数组长度解决，还是把碰撞的元素通过链表存放，都是可以的。2. 拉链寻址

说明：既然我们没法控制元素不碰撞，但我们可以对碰撞后的元素进行管理。比如像 HashMap 中拉链法一样，把碰撞的元素存放到链表上。这里我们就来简化实现一下。

public class HashMap02BySeparateChainingimplements Map{

private final LinkedList>[] tab = new LinkedList[8];

@Override

public void put(K key, V value) {

int idx = key.hashCode() & (tab.length - 1);

if (tab[idx] == null) {

tab[idx] = new LinkedList<>();

tab[idx].add(new Node<>(key, value));

} else {

tab[idx].add(new Node<>(key, value));

}

}

@Override

public V get(K key) {

int idx = key.hashCode() & (tab.length - 1);

for (NodekvNode : tab[idx]) {

if (key.equals(kvNode.getKey())) {

return kvNode.value;

}

}

return null;

}

static class Node{

final K key;

V value;

public Node(K key, V value) {

this.key = key;

this.value = value;

}

public K getKey() {

return key;

}

public V getValue() {

return value;

}

}

}

因为元素在存放到哈希桶上时，可能发生下标索引膨胀，所以这里我们把每一个元素都设定成一个 Node 节点，这些节点通过 LinkedList 链表关联，当然你也可以通过 Node 节点构建出链表 next 元素即可。那么这时候在发生元素碰撞，相同位置的元素就都被存放到链表上了，获取的时候需要对存放多个元素的链表进行遍历获取。

测试

@Test

public void test_hashMap02() {

Mapmap = new HashMap02BySeparateChaining<>();

map.put("01", "花花");

map.put("05", "豆豆");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

// 下标碰撞

map.put("09", "蛋蛋");

map.put("12", "苗苗");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

}

07:21:16.654 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

07:22:44.651 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

Process finished with exit code 0

此时第一次和第二次获取01位置的元素就都是花花了，元素没有被替代。因为此时的元素是被存放到链表上了。

3. 开放寻址

说明：除了对哈希桶上碰撞的索引元素进行拉链存放，还有不引入新的额外的数据结构，只是在哈希桶上存放碰撞元素的方式。它叫开放寻址，也就是 ThreaLocal 中运用斐波那契散列+开放寻址的处理方式。

public class HashMap03ByOpenAddressingimplements Map{

private final Node[] tab = new Node[8];

@Override

public void put(K key, V value) {

int idx = key.hashCode() & (tab.length - 1);

if (tab[idx] == null) {

tab[idx] = new Node<>(key, value);

} else {

for (int i = idx; i < tab.length; i++) {

if (tab[i] == null) {

tab[i] = new Node<>(key, value);

break;

}

}

}

}

@Override

public V get(K key) {

int idx = key.hashCode() & (tab.length - 1);

for (int i = idx; i < tab.length; i ++){

if (tab[idx] != null && tab[idx].key == key) {

return tab[idx].value;

}

}

return null;

}

static class Node{

final K key;

V value;

public Node(K key, V value) {

this.key = key;

this.value = value;

}

}

}

开放寻址的设计会对碰撞的元素，寻找哈希桶上新的位置，这个位置从当前碰撞位置开始向后寻找，直到找到空的位置存放。

在 ThreadLocal 的实现中会使用斐波那契散列、索引计算累加、启发式清理、探测式清理等操作，以保证尽可能少的碰撞。

测试

@Test

public void test_hashMap03() {

Mapmap = new HashMap03ByOpenAddressing<>();

map.put("01", "花花");

map.put("05", "豆豆");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

// 下标碰撞

map.put("09", "蛋蛋");

map.put("12", "苗苗");

logger.info("碰撞前 key：{ } value：{ }", "01", map.get("01"));

}

07:20:22.382 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

07:20:22.387 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

07:20:22.387 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 数据结构：HashMap{ tab=[null,{ "key":"01","value":"花花"},{ "key":"09","value":"蛋蛋"},{ "key":"12","value":"苗苗"},null,{ "key":"05","value":"豆豆"},null,null]}

Process finished with exit code 0

通过测试结果可以看到，开放寻址对碰撞元素的寻址存放，也是可用解决哈希索引冲突问题的。

4. 合并散列

说明：合并散列是开放寻址和单独链接的混合，碰撞的节点在哈希表中链接。此算法适合固定分配内存的哈希桶，通过存放元素时识别哈希桶上的最大空槽位来解决合并哈希中的冲突。

public class HashMap04ByCoalescedHashingimplements Map{

private final Node[] tab = new Node[8];

@Override

public void put(K key, V value) {

int idx = key.hashCode() & (tab.length - 1);

if (tab[idx] == null) {

tab[idx] = new Node<>(key, value);

return;

}

int cursor = tab.length - 1;

while (tab[cursor] != null && tab[cursor].key != key) {

--cursor;

}

tab[cursor] = new Node<>(key, value);

// 将碰撞节点指向这个新节点

while (tab[idx].idxOfNext != 0){

idx = tab[idx].idxOfNext;

}

tab[idx].idxOfNext = cursor;

}

@Override

public V get(K key) {

int idx = key.hashCode() & (tab.length - 1);

while (tab[idx].key != key) {

idx = tab[idx].idxOfNext;

}

return tab[idx].value;

}

static class Node{

final K key;

V value;

int idxOfNext;

public Node(K key, V value) {

this.key = key;

this.value = value;

}

}

}

合并散列的最大目的在于将碰撞元素链接起来，避免因为需要寻找碰撞元素所发生的循环遍历。也就是A、B元素存放时发生碰撞，那么在找到A元素的时候可以很快的索引到B元素所在的位置。

测试

07:18:43.613 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花

07:18:43.618 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：苗苗

07:18:43.619 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 数据结构：HashMap{ tab=[null,{ "idxOfNext":7,"key":"01","value":"花花"},null,null,null,{ "idxOfNext":0,"key":"05","value":"豆豆"},{ "idxOfNext":0,"key":"12","value":"苗苗"},{ "idxOfNext":6,"key":"09","value":"蛋蛋"}]}

Process finished with exit code 0

相对于直接使用开放寻址，这样的挂在链路指向的方式，可以提升索引的性能。因为在实际的数据存储上，元素的下一个位置不一定空元素，可能已经被其他元素占据，这样就增加了索引的次数。所以使用直接指向地址的方式，会更好的提高索引性能。

5. 杜鹃散列

说明：这个名字起的比较有意思，也代表着它的数据结构。杜鹃鸟在孵化