开放寻址法、链式哈希数据结构详细解读

一、开放寻址法（Open Addressing）

1. 定义

开放寻址法是一种哈希冲突解决策略，所有元素都存储在哈希表中。当发生冲突时，即两个键计算出的哈希值相同时，会按照一定的探查序列查找下一个可用的位置来存储新元素。

2. 工作原理

开放寻址法中，每个元素都在表内的一个固定位置。探查序列用于寻找下一个可用插入位置，常见的方法包括：

• 线性探查（Linear Probing）：依次检查下一个位置，如 ，其中 i 是步数。
• 二次探查（Quadratic Probing）：检查位置按二次函数递增，如 
• 双重散列（Double Hashing）：使用第二个哈希函数来确定步数，如 ((h(k)+i⋅h′(k))mod  m。

3. 特点

• 单一存储：所有元素都存储在哈希表内，不需要额外的空间来存储链表或链节点。
• 探查序列：用于在发生冲突时寻找新的存储位置。
• 删除标记：删除元素时，通常标记为“已删除”，以避免破坏探查序列。

4. 优缺点

• 优点：

  • 节省空间：不需要额外的结构来存储冲突元素。
  • 简单实现：易于理解和实现。

• 缺点：

  • 负载因子：性能受负载因子的影响，负载因子越大，探查越长，效率越低。
  • 探查冲突：线性探查容易出现聚集问题（大量元素集中在一起）。
  • 删除复杂：删除操作需要特殊标记，处理不当会影响查找效率。

5. 应用场景

• 内存有限：适合内存有限的场景，不需要额外的存储空间。
• 中等负载：适用于负载因子较低的情况，以保持性能。

6. 示例代码（Java 实现线性探查）

public class OpenAddressingHashTable {
    private String[] table;
    private int size;

    public OpenAddressingHashTable(int capacity) {
        this.table = new String[capacity];
        this.size = 0;
    }

    private int hash(String key) {
        return key.hashCode() % table.length;
    }

    public void insert(String key) {
        int hash = hash(key);
        int i = 0;
        while (table[(hash + i) % table.length] != null) {
            i++;
        }
        table[(hash + i) % table.length] = key;
        size++;
    }

    public boolean search(String key) {
        int hash = hash(key);
        int i = 0;
        while (table[(hash + i) % table.length] != null) {
            if (table[(hash + i) % table.length].equals(key)) {
                return true;
            }
            i++;
        }
        return false;
    }
}

二、链式哈希（Chaining）

1. 定义

链式哈希是一种使用链表来解决哈希冲突的方法。在链式哈希中，每个哈希表的桶（bucket）中存储一个链表。当两个或多个键映射到同一哈希值时，这些键被存储在对应桶的链表中。

2. 工作原理

当元素被插入时，哈希函数计算出其哈希值，并将元素插入到对应桶的链表中。如果桶为空，创建新的链表并将元素加入其中。查找时，哈希值定位桶，然后遍历链表寻找元素。

3. 特点

• 桶与链表结合：哈希表的每个桶可以存储多个元素，冲突的元素以链表的形式链接。
• 动态增长：链表的长度不限，可以动态增长以存储任意数量的冲突元素。
• 负载因子：哈希表性能受负载因子影响，合理的哈希函数和扩展策略有助于保持效率。

4. 优缺点

• 优点：

  • 简单删除：删除操作相对简单，只需从链表中删除节点，不影响整体结构。
  • 负载平衡：对于高负载因子，链表能有效处理大量冲突。

• 缺点：

  • 内存开销：每个链表节点需要额外存储指针，会增加内存消耗。
  • 查找时间：最坏情况下（所有元素哈希到同一个桶），查找时间为 O(n)。

5. 应用场景

• 动态数据存储：适用于插入和删除频繁的场景。
• 高负载因子：在负载较高时，链式哈希能更好地维持性能。

6. 示例代码（Java 实现链式哈希）

import java.util.LinkedList;

public class ChainingHashTable {
    private LinkedList<String>[] table;

    public ChainingHashTable(int capacity) {
        table = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hash(String key) {
        return key.hashCode() % table.length;
    }

    public void insert(String key) {
        int index = hash(key);
        table[index].add(key);
    }

    public boolean search(String key) {
        int index = hash(key);
        return table[index].contains(key);
    }

    public void delete(String key) {
        int index = hash(key);
        table[index].remove(key);
    }
}

总结比较