散列查找 | Wiliyaya's blog

一、散列函数的构造

原数据的关键字key 通过散列函数 H(key) 映射到新的地址
用一个质数求余发生冲突的可能性更小

二、散列冲突的解决方案

1.开放地址法

这里的开放地址其实就是一个空位置
开放地址法就是如果发生冲突，就按照规则，寻找空位置；最先找到的空位置就是这个关键字的对应的存储位置

1	h[i]=(H(key)+d[i])% table_size (i=1,2,...,table_size-1)

d[i] 一般有三种写法:

线性探测 d[i] =1,2,3,…,table_size (其实是d[i] = c* i ,但是c通常取1)
二次探测（平方探测再散列）：d[i]=1²,-1²,2²,-2²,…,k²,-k² (k<=table_size/2)
伪随机探测

（1）线性探测法

冲突后依次探测下一个位置，知道遇到空位置
构建散列表
查找成功和失败的AVL分别如何计算
*注意在教材中，和空位置的比较是不计入比较次数的
（但是有的地方认为空位置其实是NULL类型，也是一次比较

删除元素时，不能直接把该位置换成空位置的标记（会造成后面的数被误认为不存在），应该设一个删除标记。
增加新的元素时，删除标记和空标记都可以插入新元素，而查找时遇到空位置就代表结束，遇到删除标记则继续查找

（2）平方探测

d[i]=1²,-1²,2²,-2²,…,k²,-k² (k<=table_size/2)
缺点是不一定能探测到所有散列表位置
但是研究表明，表长如果是某个4k+3的质数（7，11…），那么一定能探测到所有的位置

删除也是设删除标记

（3）随机

2.再散列法

1	h[i]=RH(key); (i=1,2,3...,n)

就是有n个不同的散列函数，当第一个有冲突时，就用第二个散列函数计算的结果，以此类推

3.链地址法

把所有映射到同一个位置的关键字用一个链表串起来

ASL(成功)= ∑(每一层元素的个数 * 这一层相应的比较次数）/元素个数
ASL(失败)= ∑每个链表找到空位置时需要的比较个数（每个槽中的元素个数） / 链表的个数（槽的个数）

删除的话就直接删。

相关代码

这是deepseek帮我翻译的代码，我还没仔细读，先放在这存着

以下是伪代码转换后的C++代码，包含详细注释：

#include <vector>
using namespace std;

// 散列表项的状态：活跃、空、已删除（用于懒惰删除）
enum EntryStatus { ACTIVE, EMPTY, DELETED };

// 散列表项结构体
template <typename K, typename V>
struct HashEntry {
    K key;          // 键
    V value;        // 值
    EntryStatus status; // 状态
    HashEntry() : status(EMPTY) {} // 初始化状态为空
};

// 开放地址法散列表类
template <typename K, typename V>
class HashTable {
private:
    vector<HashEntry<K, V>> table; // 散列表存储数组
    int table_size;                // 散列表总大小
    int current_size;              // 当前已存储的元素数量

    // 散列函数示例（可根据需求替换）
    int hashFunction(const K& key) const {
        return hash<K>{}(key) % table_size;
    }

    // 解决冲突的函数（示例：线性探测，返回固定步长1）
    int solveCollision(const K& key, int count, int hash_v) const {
        return 1; // 线性探测：每次步长+1
        // 若使用二次探测，可返回 count * count;
    }

public:
    HashTable(int size) : table(size), table_size(size), current_size(0) {}

    // 查找函数：返回键的位置或第一个空位
    int searchHash(const K& key) {
        int hash_v = hashFunction(key); // 计算初始散列地址
        int p = hash_v;
        int count = 0; // 冲突次数

        while (table[p].status != EMPTY && table[p].key != key) {
            count++;
            // 计算下一个探查地址
            p = hash_v + solveCollision(key, count, hash_v);
            p %= table_size; // 确保不越界
            if (p < 0) p += table_size; // 处理负数情况
        }
        return p; // 返回找到的位置或空位
    }

    // 插入函数
    bool insertHash(const K& key, const V& value) {
        if (current_size >= table_size) {
            return false; // 表已满（可根据需求扩展表大小）
        }

        int p = searchHash(key); // 查找插入位置

        // 如果当前位置为空或已删除，则插入新元素
        if (table[p].status != ACTIVE) {
            table[p].key = key;
            table[p].value = value;
            table[p].status = ACTIVE;
            current_size++;
            return true;
        }

        // 如果键已存在，可根据需求更新值
        // 此处直接返回false表示不覆盖已有键
        return false;
    }
};

代码说明：

数据结构：
- HashEntry 结构体表示散列表中的每个项，包含键、值和状态。
- HashTable 类封装了开放地址法的核心逻辑，使用 vector 存储表项。
关键函数：
- searchHash：根据键查找位置，处理冲突直到找到目标键或空位。
- insertHash：调用 searchHash 找到合适位置，仅在状态非 ACTIVE 时插入新元素。
冲突解决：
- solveCollision 示例为线性探测（步长+1），可根据需求改为二次探测（如返回 count * count）。
扩展性：
- 可修改 hashFunction 和 solveCollision 实现不同的散列函数和冲突策略。
- 插入时若表满，可添加扩容逻辑（如重新散列到更大的表）。

使用示例：

int main() {
    HashTable<int, string> ht(10);
    ht.insertHash(42, "Alice");
    ht.insertHash(15, "Bob");
    return 0;
}