c++中如何实现开放寻址法_c++开放寻址法实现方法-C++-PHP中文网

c++中如何实现开放寻址法_c++开放寻址法实现方法

裘德小鎮的故事

发布： 2025-09-29 09:13:01

原创

672人浏览过

答案：C++中开放寻址法通过线性探测、二次探测和双重哈希在冲突时寻找空位，需标记删除状态并控制负载因子以维持性能。

c++中如何实现开放寻址法_c++开放寻址法实现方法

在C++中实现开放寻址法（Open Addressing）解决哈希冲突，核心思路是当发生冲突时，在哈希表中寻找下一个可用的位置来存储数据，而不是使用链表等外部结构。常见的探测方式包括线性探测、二次探测和双重哈希。

1. 线性探测（Linear Probing）

线性探测是最简单的开放寻址策略：当哈希位置被占用时，依次检查下一个位置，直到找到空位。

关键点：

哈希函数：hash(key) % table_size
探测序列：(hash(key) + i) % table_size，其中 i 从 0 开始递增
删除操作需标记“已删除”状态，避免查找中断

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;
<p>enum State { EMPTY, OCCUPIED, DELETED };</p><p>struct HashEntry {
int key;
int value;
State state;</p><pre class='brush:php;toolbar:false;'>HashEntry() : key(0), value(0), state(EMPTY) {}

登录后复制

};

class HashTable { private: vector<HashEntry> table; int size;

<pre class="brush:php;toolbar:false;">int hash(int key) {
    return key % size;
}

int find_index(int key) {
    int index = hash(key);
    int i = 0;
    while (table[(index + i) % size].state != EMPTY &&
           table[(index + i) % size].key != key) {
        i++;
    }
    return (index + i) % size;
}

登录后复制

public: HashTable(int s) : size(s) { table.resize(size); }

void insert(int key, int value) {
    int index = hash(key);
    int i = 0;
    while (table[(index + i) % size].state == OCCUPIED &&
           table[(index + i) % size].key != key) {
        i++;
    }
    int pos = (index + i) % size;
    table[pos].key = key;
    table[pos].value = value;
    table[pos].state = OCCUPIED;
}

int search(int key) {
    int index = hash(key);
    int i = 0;
    while (table[(index + i) % size].state != EMPTY) {
        int pos = (index + i) % size;
        if (table[pos].state == OCCUPIED && table[pos].key == key) {
            return table[pos].value;
        }
        i++;
    }
    return -1; // not found
}

void remove(int key) {
    int index = find_index(key);
    if (table[index].state == OCCUPIED && table[index].key == key) {
        table[index].state = DELETED;
    }
}

登录后复制

};

2. 二次探测（Quadratic Probing）

为减少聚集现象，使用平方增量进行探测。

探测公式：(hash(key) + i²) % table_size

PhotoAid Image Upscaler

PhotoAid出品的免费在线AI图片放大工具

查看详情

注意：表大小应为质数，且负载因子控制在较低水平，以确保能找到空位。

修改插入部分示例：

    void insert(int key, int value) {
        int index = hash(key);
        int i = 0;
        while (i < size) {
            int pos = (index + i*i) % size;
            if (table[pos].state == EMPTY || table[pos].state == DELETED) {
                table[pos].key = key;
                table[pos].value = value;
                table[pos].state = OCCUPIED;
                return;
            } else if (table[pos].key == key && table[pos].state == OCCUPIED) {
                table[pos].value = value; // update
                return;
            }
            i++;
        }
    }

登录后复制

3. 双重哈希（Double Hashing）

使用第二个哈希函数计算步长，进一步分散探测路径。

探测公式：(h1(key) + i * h2(key)) % table_size

常用设计：
h1(key) = key % size
h2(key) = prime - (key % prime)，prime 为略小于 size 的质数

示例：

    int hash2(int key) {
        int prime = 7; // 小于 size 的质数
        return prime - (key % prime);
    }
<pre class='brush:php;toolbar:false;'>void insert(int key, int value) {
    int index1 = hash(key);
    int index2 = hash2(key);
    int i = 0;
    while (i < size) {
        int pos = (index1 + i * index2) % size;
        if (table[pos].state == EMPTY || table[pos].state == DELETED) {
            table[pos].key = key;
            table[pos].value = value;
            table[pos].state = OCCUPIED;
            return;
        }
        i++;
    }
}

登录后复制