散列冲突处理策略：避免性能瓶颈，保障系统稳定

# 1. 散列冲突概述

散列冲突是指在散列表中，不同的键值映射到相同的散列值的情况。冲突的发生会降低散列表的查找效率，并可能导致错误。

散列冲突的产生有两种主要原因：

- **散列函数不完美：**散列函数无法保证将所有键值映射到不同的散列值。
- **数据分布不均匀：**键值在散列表中的分布不均匀，导致某些散列值被大量键值占用。

# 2. 散列冲突处理策略

在散列表中，冲突是不可避免的。当多个键映射到同一个散列值时，就会发生冲突。为了解决冲突，需要采用有效的冲突处理策略。常用的冲突处理策略包括：

### 2.1 开放寻址法

开放寻址法将所有元素存储在散列表中，并使用探测函数来查找冲突元素的下一个可用位置。

#### 2.1.1 线性探查

线性探查是最简单的开放寻址法。当发生冲突时，它从冲突位置开始，依次探查散列表中的下一个位置，直到找到一个空位置。

def linear_probe(table, key):
    """
    线性探查冲突处理策略

    Args:
        table: 散列表
        key: 要查找的键

    Returns:
        键值对的索引，如果找不到则返回 -1
    """
    index = hash(key) % len(table)
    while table[index] != None:
        if table[index][0] == key:
            return index
        index = (index + 1) % len(table)
    return -1

**逻辑分析：**

* `index` 变量存储散列表中键的初始索引。
* 循环遍历散列表，直到找到一个空位置或找到要查找的键。
* 如果找到要查找的键，则返回其索引。
* 如果未找到键，则返回 -1。

#### 2.1.2 二次探查

二次探查是一种改进的开放寻址法，它通过使用二次探测序列来减少冲突。

def quadratic_probe(table, key):
    """
    二次探查冲突处理策略

    Args:
        table: 散列表
        key: 要查找的键

    Returns:
        键值对的索引，如果找不到则返回 -1
    """
    index = hash(key) % len(table)
    step = 1
    while table[index] != None:
        if table[index][0] == key:
            return index
        index = (index + step**2) % len(table)
        step += 1
    return -1

**逻辑分析：**

* `index` 变量存储散列表中键的初始索引。
* `step` 变量存储二次探测序列的步长。
* 循环遍历散列表，直到找到一个空位置或找到要查找的键。
* 如果找到要查找的键，则返回其索引。
* 如果未找到键，则返回 -1。

#### 2.1.3 双重散列

双重散列使用两个不同的散列函数来生成探测序列。

def double_hashing(table, key):
    """
    双重散列冲突处理策略

    Args:
        table: 散列表
        key: 要查找的键

    Returns:
        键值对的索引，如果找不到则返回 -1
    """
    index1 = hash(key) % len(table)
    index2 = hash(key, 2) % len(table)
    step = 1
    while table[index1] != None:
        if table[index1][0] == key:
            return index1
        index1 = (index1 + step * index2) % len(table)
        step += 1
    return -1

**逻辑分析：**

* `index1` 变量存储散列表中键的初始索引，由第一个散列函数生成。
* `index2` 变量存储第二个散列函数生成的探测序列的步长。
* 循环遍历散列表，直到找到一个空位置或找到要查找的键。
* 如果找到要查找的键，则返回其索引。
* 如果未找到键，则返回 -1。

### 2.2 链地址法

链地址法将冲突元素存储在散列表中，每个散列表位置指向一个链表，其中包含与该位置冲突的所有元素。

#### 2.2.1 链表法

链表法是最简单的链地址法。它使用一个单链表来存储冲突元素。

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class ChainedHashTable:
    def __init__(self):
        self.table = [None] * 100

    def insert(self, key, value):
        index = hash(key) % len(self.table)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            node = self.table[index]
            while node.next is not None:
                node = node.next
            node.next = Node(key, value)

    def search(self, key):
        index = hash(key) % len(self.table)
        node = self.table[ind