作者：小傅哥
沉淀、分享、成长，让自己和他人都能有所收获！😄
哈希表的历史
哈希散列的想法在不同的地方独立出现。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 还是你在刷题中位了提升索引效率，都会用到哈希散列。
只要哈希桶的长度由负载因子控制的合理，每次查找元素的平均时间复杂度与桶中存储的元素数量无关。另外许多哈希表设计还允许对键值对的任意插入和删除，每次操作的摊销固定平均成本。
好，那么介绍了这么多，小傅哥带着大家做几个关于哈希散列的数据结构，通过实践来了解会更加容易搞懂。
说明：通过模拟简单 HashMap 实现，去掉拉链寻址等设计，验证元素哈新索引位置碰撞。
public class HashMap01<K, V> implements Map<K, V> { 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]; } } 
测试
@Test public void test_hashMap01() { Map<String, String> map = 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 花花，两次下标索引碰撞后存放的值则是苗苗说明：既然我们没法控制元素不碰撞，但我们可以对碰撞后的元素进行管理。比如像 HashMap 中拉链法一样，把碰撞的元素存放到链表上。这里我们就来简化实现一下。
public class HashMap02BySeparateChaining<K, V> implements Map<K, V> { private final LinkedList<Node<K, V>>[] 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 (Node<K, V> kvNode : tab[idx]) { if (key.equals(kvNode.getKey())) { return kvNode.value; } } return null; } static class Node<K, V> { 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; } } }
测试
@Test public void test_hashMap02() { Map<String, String> map = 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 花花了，元素没有被替代。因为此时的元素是被存放到链表上了。说明：除了对哈希桶上碰撞的索引元素进行拉链存放，还有不引入新的额外的数据结构，只是在哈希桶上存放碰撞元素的方式。它叫开放寻址，也就是 ThreaLocal 中运用斐波那契散列+开放寻址的处理方式。
public class HashMap03ByOpenAddressing<K, V> implements Map<K, V> { private final Node<K, V>[] 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<K, V> { final K key; V value; public Node(K key, V value) { this.key = key; this.value = value; } } }
测试
@Test public void test_hashMap03() { Map<String, String> map = 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 说明：合并散列是开放寻址和单独链接的混合，碰撞的节点在哈希表中链接。此算法适合固定分配内存的哈希桶，通过存放元素时识别哈希桶上的最大空槽位来解决合并哈希中的冲突。
public class HashMap04ByCoalescedHashing<K, V> implements Map<K, V> { private final Node<K, V>[] 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<K, V> { final K key; V value; int idxOfNext; public Node(K key, V value) { this.key = key; this.value = value; } } }
测试
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 说明：这个名字起的比较有意思，也代表着它的数据结构。杜鹃鸟在孵化🐣的时候，雏鸟会将其他蛋或幼崽推出巢穴；类似的这个数据结构会使用2组key哈希表，将冲突元素推到另外一个key哈希表中。
private V put(K key, V value, boolean isRehash) { Object k = maskNull(key); if (containsKey(k)) { return null; } if (insertEntry(new Entry<K, V>((K) k, value))) { if (!isRehash) { size++; } return null; } rehash(2 * table.length); return put((K) k, value); } private boolean insertEntry(Entry<K, V> e) { int count = 0; Entry<K, V> current = e; int index = hash(hash1, current.key); while (current != e || count < table.length) { Entry<K, V> temp = table[index]; if (temp == null) { table[index] = current; return true; } table[index] = current; current = temp; if (index == hash(hash1, current.key)) { index = hash(hash2, current.key); } else { index = hash(hash1, current.key); } ++count; } return false; }
测试
07:52:04.010 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花 07:52:04.016 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：苗苗 07:52:04.016 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 数据结构：{01=花花, 12=苗苗, 05=豆豆, 09=蛋蛋} Process finished with exit code 0 说明：跳房子散列是一种基于开放寻址的算法，它结合了杜鹃散列、线性探测和链接的元素，通过桶邻域的概念——任何给定占用桶周围的后续桶，也称为“虚拟”桶。 该算法旨在在哈希表的负载因子增长超过 90% 时提供更好的性能；它还在并发设置中提供了高吞吐量，因此非常适合实现可调整大小的并发哈希表。
public boolean insert(AnyType x) { if (!isEmpty()) { return false; } int currentPos = findPos(x); if (currentPos == -1) { return false; } if (array[currentPos] != null) { x = array[currentPos].element; array[currentPos].isActive = true; } String hope; if (array[currentPos] != null) { hope = array[currentPos].hope; x = array[currentPos].element; } else { hope = "10000000"; } array[currentPos] = new HashEntry<>(x, hope, true); theSize++; return true; }
测试
@Test public void test_hashMap06() { HashMap06ByHopscotchHashing<Integer> map = new HashMap06ByHopscotchHashing<>(); map.insert(1); map.insert(5); map.insert(9); map.insert(12); logger.info("数据结构：{}", map); }
17:10:10.363 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 数据结构：HashMap{tab=[null,{"element":1,"hope":"11000000","isActive":true},{"element":9,"hope":"00000000","isActive":true},null,{"element":12,"hope":"10000000","isActive":true},{"element":5,"hope":"10000000","isActive":true},null,null]} Process finished with exit code 0 说明：罗宾汉哈希是一种基于开放寻址的冲突解决算法；冲突是通过偏向从其“原始位置”（即项目被散列到的存储桶）最远或最长探测序列长度（PSL）的元素的位移来解决的。
public void put(K key, V value) { Entry entry = new Entry(key, value); int idx = hash(key); // 元素碰撞检测 while (table[idx] != null) { if (entry.offset > table[idx].offset) { // 当前偏移量不止一个，则查看条目交换位置，entry 是正在查看的条目，增加现在搜索的事物的偏移量和 idx Entry garbage = table[idx]; table[idx] = entry; entry = garbage; idx = increment(idx); entry.offset++; } else if (entry.offset == table[idx].offset) { // 当前偏移量与正在查看的检查键是否相同，如果是则它们交换值，如果不是，则增加 idx 和偏移量并继续 if (table[idx].key.equals(key)) { // 发现相同值 V oldVal = table[idx].value; table[idx].value = value; } else { idx = increment(idx); entry.offset++; } } else { // 当前偏移量小于我们正在查看的我们增加 idx 和偏移量并继续 idx = increment(idx); entry.offset++; } } // 已经到达了 null 所在的 idx，将新/移动的放在这里 table[idx] = entry; size++; // 超过负载因子扩容 if (size >= loadFactor * table.length) { rehash(table.length * 2); } }
测试
public void test_hashMap07() { Map<String, String> map = new HashMap07ByRobinHoodHashing<>(); 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("12")); logger.info("数据结构：{}", map); }
07:34:32.593 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：花花 09 1 12 1 01 1 09 9 12 1 05 5 07:35:07.419 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 碰撞前 key：01 value：苗苗 07:35:07.420 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 数据结构：HashMap{tab=[null,{"key":"01","offset":0,"value":"花花"},{"key":"12","offset":1,"value":"苗苗"},null,null,{"key":"05","offset":0,"value":"豆豆"},null,null,null,{"key":"09","offset":0,"value":"蛋蛋"},null,null,null,null,null,null]} Process finished with exit code 0 评论已关闭。
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/2.jpg&w=218&h=124&zc=1)
