哈希冲突处理策略：开放寻址与链地址法

# 第一章：引言
哈希冲突是指当两个或多个键被哈希函数映射到同一个存储桶时发生的情况。在哈希表中，每个键都应该映射到唯一的位置，但由于哈希函数的取值范围通常远小于键的取值范围，因此可能会出现多个键映射到同一个位置的情况，即哈希冲突。

哈希表是一种常用的数据结构，它通过将键映射到存储桶来实现高效的数据存储和检索。哈希冲突的处理策略直接影响了哈希表的性能和效率。

## 第二章：开放寻址法

在哈希表中，开放寻址法是一种处理哈希冲突的方法。当插入新键值对时，如果计算得到的哈希值已经被其他键占用，开放寻址法将会尝试寻找另一个空槽来存放该键值对。接下来，我们将深入探讨三种常见的开放寻址法：线性探测法、二次探测法和双重哈希法，以及这些方法各自的优缺点。

### 线性探测法

线性探测法是开放寻址法的一种简单形式。当发生哈希冲突时，线性探测法会依次检查哈希表中的下一个位置，直到找到一个空槽来存放新的键值对。

#### Python示例代码

class LinearProbeHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
            index = (index + 1) % self.size
        self.table[index] = (key, value)

### 二次探测法

与线性探测法类似，二次探测法在发生哈希冲突时会以二次方的增量寻找下一个空槽来存放键值对，这样可以更加均匀地分布键值对。

#### Java示例代码

public class QuadraticProbeHashTable {
    private int size;
    private Object[] table;

    public QuadraticProbeHashTable(int size) {
        this.size = size;
        this.table = new Object[size];
    }

    private int hashFunction(int key) {
        return key % size;
    }

    public void insert(int key, Object value) {
        int index = hashFunction(key);
        int i = 1;
        while (table[index] != null) {
            index = (index + i * i) % size;
            i++;
        }
        table[index] = value;
    }
}

### 双重哈希法

双重哈希法通过使用两个不同的哈希函数来计算增量，以解决线性探测法和二次探测法可能出现的聚集现象。

#### Go示例代码

type DoubleHashHashTable struct {
    size  int
    table []*Entry
}

type Entry struct {
    key   int
    value string
}

func (ht *DoubleHashHashTable) hashFunction1(key int) int {
    return key % ht.size
}

func (ht *DoubleHashHashTable) hashFunction2(key int) int {
    return 7 - (key % 7)
}

func (ht *DoubleHashHashTable) insert(key int, value string) {
    index := ht.hashFunc