详细版:哈希表（Hash Table)哈希冲突及其解决方法

哈希冲突的来源

哈希冲突是指不同的键（Key）经过哈希函数计算后，映射到相同的索引（Index）位置。由于哈希表的大小是有限的，而键的集合通常是无限的，因此冲突是不可避免的。例如，如果哈希表的大小为10，而两个不同的键 key1 和 key2 经过哈希函数计算后都得到相同的哈希值 hash(key1) = hash(key2) = 3，那么它们都会被存储在索引为3的位置。

解决哈希冲突的方法

下面详细介绍两种主要的哈希冲突解决方法：链地址法（Chaining）和开放地址法（Open Addressing），并通过图表进行更直观的说明。

链地址法（Chaining）

在链地址法中，哈希表的每个索引位置（也称为“桶”或“槽”）存储一个链表（或其他数据结构，如数组、树），所有映射到该位置的键值对都被存储在这个链表中。这种方法简单直观，适合冲突较多的情况。

链地址法的示意图：

+-----------------+
|      索引0      |
|    (key1, v1)   |
+-----------------+
|      索引1      |
|    (key2, v2)   |
+-----------------+
|      索引2      |
|    (key3, v3) ->|
|    (key4, v4)   |
+-----------------+
|      索引3      |
|    (key5, v5)   |
+-----------------+

链地址法的优点：

实现简单：直接使用链表即可。
内存利用率高：只有在冲突时才需要额外的存储空间。
动态大小：链表的长度可以动态调整，不会因为冲突而影响性能。

链地址法的缺点：

链表遍历开销：在最坏情况下（所有元素都映射到同一个索引），查找操作的时间复杂度会退化为 O(n)。
空间复杂度：每个链表节点需要额外的指针空间。

链地址法的实现示例（Java）：

class HashNode<K, V> {K key;  // 键V value;  // 值HashNode<K, V> next;  // 指向下一个节点的指针// 构造函数public HashNode(K key, V value) {this.key = key;this.value = value;this.next = null;  // 初始时，下一个节点为空}
}class HashTable<K, V> {private int size;  // 当前元素数量private int capacity;  // 哈希表容量private HashNode<K, V>[] buckets;  // 存储桶的数组// 构造函数，初始化哈希表public HashTable(int capacity) {this.size = 0;this.capacity = capacity;this.buckets = new HashNode[capacity];  // 初始化桶数组}// 获取键的哈希值并计算对应的桶索引private int getBucketIndex(K key) {int hashCode = key.hashCode();  // 获取键的哈希值return Math.abs(hashCode) % capacity;  // 取绝对值并取模，得到桶索引}// 插入键值对public void insert(K key, V value) {int index = getBucketIndex(key);  // 获取键对应的桶索引HashNode<K, V> head = buckets[index];  // 获取该桶的头节点while (head != null) {if (head.key.equals(key)) {head.value = value;  // 如果键已存在，更新值return;}head = head.next;  // 遍历链表}size++;  // 增加元素数量head = buckets[index];  // 重新获取头节点HashNode<K, V> newNode = new HashNode<>(key, value);  // 创建新节点newNode.next = head;  // 将新节点插入链表头部buckets[index] = newNode;  // 更新桶的头节点}// 获取键对应的值public V get(K key) {int index = getBucketIndex(key);  // 获取键对应的桶索引HashNode<K, V> head = buckets[index];  // 获取该桶的头节点while (head != null) {if (head.key.equals(key)) {return head.value;  // 找到键，返回对应的值}head = head.next;  // 遍历链表}return null;  // 未找到键，返回null}// 删除键值对public void remove(K key) {int index = getBucketIndex(key);  // 获取键对应的桶索引HashNode<K, V> head = buckets[index];  // 获取该桶的头节点HashNode<K, V> prev = null;  // 初始化前一个节点while (head != null) {if (head.key.equals(key)) {break;  // 找到键，跳出循环}prev = head;  // 更新前一个节点head = head.next;  // 遍历链表}if (head == null) return;  // 未找到键，直接返回size--;  // 减少元素数量if (prev != null) {prev.next = head.next;  // 前一个节点的指针指向后一个节点} else {buckets[index] = head.next;  // 如果删除的是头节点，直接更新桶的头节点}}
}

开放地址法（Open Addressing）

在开放地址法中，所有元素都存储在哈希表的数组中，当发生冲突时，通过某种探测策略（如线性探测、二次探测、双重散列等）寻找下一个可用位置。

开放地址法的示意图：

+-----------------+
|      索引0      |
|    (key1, v1)   |
+-----------------+
|      索引1      |
|    (key2, v2)   |
+-----------------+
|      索引2      |
|    (key3, v3)   |
+-----------------+
|      索引3      |
|    (key4, v4)   |
+-----------------+
|      索引4      |
|    (key5, v5)   |
+-----------------+

开放地址法的优点：

内存连续：所有元素存储在连续的内存空间中，访问速度快。
无额外空间：不需要额外的链表或其他数据结构。

开放地址法的缺点：

探测开销：当冲突较多时，需要多次探测才能找到空闲位置，性能下降。
删除操作复杂：需要标记删除位置或者移动元素，增加了操作的复杂性。

开放地址法的实现示例（Java）：

class HashTable<K, V> {private int size;  // 当前元素数量private int capacity;  // 哈希表容量private K[] keys;  // 存储键的数组private V[] values;  // 存储值的数组// 构造函数，初始化哈希表public HashTable(int capacity) {this.size = 0;this.capacity = capacity;this.keys = (K[]) new Object[capacity];  // 初始化键数组this.values = (V[]) new Object[capacity];  // 初始化值数组}// 获取键的哈希值并计算对应的桶索引private int getBucketIndex(K key) {int hashCode = key.hashCode();  // 获取键的哈希值return Math.abs(hashCode) % capacity;  // 取绝对值并取模，得到桶索引}// 线性探测函数private int linearProbe(int index, int i) {return (index + i) % capacity;  // 线性探测，返回下一个索引}// 插入键值对public void insert(K key, V value) {int index = getBucketIndex(key);  // 获取键对应的桶索引for (int i = 0; i < capacity; i++) {int probeIndex = linearProbe(index, i);  // 获取探测索引if (keys[probeIndex] == null || keys[probeIndex].equals(key)) {if (keys[probeIndex] == null) {size++;  // 如果该位置为空，增加元素数量}keys[probeIndex] = key;  // 插入键values[probeIndex] = value;  // 插入值return;}}throw new RuntimeException("HashTable is full");  // 哈希表已满，抛出异常}// 获取键对应的值public V get(K key) {int index = getBucketIndex(key);  // 获取键对应的桶索引for (int i = 0; i < capacity; i++) {int probeIndex = linearProbe(index, i);  // 获取探测索引if (keys[probeIndex] == null) {return null;  // 如果该位置为空，未找到键，返回null}if (keys[probeIndex].equals(key)) {return values[probeIndex];  // 找到键，返回对应的值}}return null;  // 未找到键，返回null}// 删除键值对public void remove(K key) {int index = getBucketIndex(key);  // 获取键对应的桶索引for (int i = 0; i < capacity; i++) {int probeIndex = linearProbe(index, i);  // 获取探测索引if (keys[probeIndex] == null) {return;  // 如果该位置为空，未找到键，直接返回}if (keys[probeIndex].equals(key)) {keys[probeIndex] = null;  // 删除键values[probeIndex] = null;  // 删除值size--;  // 减少元素数量return;}}}
}