数据结构中散列表+哈希表经典之冲突处理

前言

散列表（Hash Table）是一种常用的数据结构，它通过将关键字映射到固定长度的数组中来实现高效的数据存储和查找。然而，在实际应用中，由于散列函数可能存在冲突，不同的关键字可能会映射到同一个数组位置上，这就需要采用冲突处理技术来解决。

1. 开放定址法

开放定址法是解决散列表冲突的一种方法。当发生冲突时，该方法会找到下一个可用的位置来存储冲突的关键字。下面是一种常见的开放定址法：线性探测：

class HashTable {
    // ...

    // 线性探测法解决冲突
    int linearProbe(int key) {
        int index = hashFunc(key); // 获取散列值
        while (table[index].occupied) {
            if (table[index].key == key) {
                return index; // 关键字已存在
            }
            index = (index + 1) % size; // 根据探测函数获取下一个位置
        }
        return index; // 返回可用位置的索引
    }

    // ...
}

线性探测法通过不断地顺序查找下一个位置，直到找到一个未占用的位置，来解决冲突。然而，线性探测法可能会引发聚集问题，即多个关键字倾向于聚集在同一个区域，导致查找效率降低。因此，还有其他的开放定址法，如二次探测、双重散列等。

2. 链表法

链表法是解决散列表冲突的另一种常用方法。在链表法中，散列数组的每个位置都是一个链表的头指针，当发生冲突时，将关键字添加到对应位置的链表中。下面是一个简单的链表法实现：

class HashTable {
    class Node {
        int key;
        Node next;
    }

    // 散列表使用一个数组来存放链表的头节点
    Node[] table;

    // ...

    // 链表法解决冲突
    void chaining(int key) {
        int index = hashFunc(key); // 获取散列值
        Node newNode = new Node();
        newNode.key = key;
        if (table[index] == null) {
            // 该位置对应的链表为空，直接插入头节点
            table[index] = newNode;
        } else {
            // 遍历链表，找到最后一个节点
            Node cur = table[index];
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode; // 将新节点插入链表
        }
    }

    // ...
}

链表法通过将具有相同散列值的关键字组织在一条链表中，来解决冲突。这样，当发生冲突时，只需在对应位置的链表上进行插入和查找操作，不会修改其他位置的链表，能够保持较好的查找性能。

3. 第三种冲突处理方法

除了开放定址法和链表法外，还有一些其他的冲突处理方法。例如，可以使用再散列法，即使用不同的散列函数来解决冲突。以下是再散列法的一个示例：

class HashTable {
    // ...

    // 再散列法解决冲突
    int rehash(int key) {
        int h1 = hashFunc1(key); // 第一个散列函数
        int h2 = hashFunc2(key); // 第二个散列函数
        int index = h1;
        int i = 1;
        while (table[index].occupied) {
            index = (h1 + i * h2) % size; // 根据再散列函数获取下一个位置
            i++;
        }
        return index; // 返回可用位置的索引
    }

    // ...
}

再散列法通过使用多个散列函数来减少冲突的概率。当发生冲突时，根据再散列函数计算下一个位置，直到找到一个未占用的位置或遍历完所有位置。再散列法在实际应用中具有较好的效果，并且可以根据实际情况选择不同的散列函数。

总结

散列表的冲突处理是解决数据结构中的关键问题之一。本文介绍了散列表中两种常用的冲突处理方法：开放定址法和链表法，并针对每种方法进行了代码实现和解释。此外，还提到了再散列法作为第三种冲突处理方法的示例。根据实际需求和数据特点，选择合适的冲突处理方法可以提高散列表的性能和效率。