c++语言二次探测散列法

C++语言中的二次探测散列法是一种常见的散列表实现方法，用于解决哈希冲突问题。其基本思想是，当哈希函数计算出的位置已经被占用时，按照一定的规则在散列表中查找下一个空闲位置，直到找到为止。

具体实现过程如下：

1. 对于给定的关键字，通过哈希函数计算出它在散列表中的位置。

2. 如果该位置已经被占用，则按照二次探测法的规则，在散列表中查找下一个空闲位置。具体规则为，从当前位置开始，依次查找 $(1^2, 2^2, 3^2, \ldots)$ 个位置，直到找到一个空闲位置为止。

3. 如果散列表已经满了，则无法插入新的关键字。

4. 在查找时，如果找到了与待查找关键字相等的关键字，则说明该关键字已经存在于散列表中。

下面是二次探测散列法的C++代码实现：

const int MAX_SIZE = 10007;

// 哈希表中的每个元素结构体
struct HashNode {
    int key;  // 关键字
    int value;  // 值
};

// 哈希表类
class HashTable {
public:
    HashTable();
    ~HashTable();
    void Insert(int key, int value);
    void Remove(int key);
    int Find(int key);
private:
    HashNode* data;  // 哈希表数据
    int size;  // 哈希表大小
    int count;  // 哈希表中元素个数
    int HashFunc(int key);  // 哈希函数
    int GetNextPos(int pos, int i);  // 获取下一个空闲位置
};

HashTable::HashTable() {
    size = MAX_SIZE;
    count = 0;
    data = new HashNode[size];
}

HashTable::~HashTable() {
    delete[] data;
}

void HashTable::Insert(int key, int value) {
    int pos = HashFunc(key);
    int i = 0;
    while (data[pos].key != -1 && i < size) {
        pos = GetNextPos(pos, i);
        i++;
    }
    if (i >= size) {
        cout << "HashTable is full." << endl;
        return;
    }
    data[pos].key = key;
    data[pos].value = value;
    count++;
}

void HashTable::Remove(int key) {
    int pos = HashFunc(key);
    int i = 0;
    while (data[pos].key != key && i < size) {
        pos = GetNextPos(pos, i);
        i++;
    }
    if (i >= size) {
        cout << "Key not found." << endl;
        return;
    }
    data[pos].key = -1;
    data[pos].value = -1;
    count--;
}

int HashTable::Find(int key) {
    int pos = HashFunc(key);
    int i = 0;
    while (data[pos].key != key && i < size) {
        pos = GetNextPos(pos, i);
        i++;
    }
    if (i >= size) {
        cout << "Key not found." << endl;
        return -1;
    }
    return data[pos].value;
}

int HashTable::HashFunc(int key) {
    return key % size;
}

int HashTable::GetNextPos(int pos, int i) {
    return (pos + i * i) % size;
}

在上面的代码中，`HashTable` 类封装了二次探测散列法的实现细节，提供了插入、删除和查找操作。其中，`data` 数组存储了哈希表中的元素，`size` 表示哈希表的大小，`count` 表示哈希表中元素的个数。`HashFunc` 函数实现了哈希函数，`GetNextPos` 函数实现了获取下一个空闲位置的规则。在插入、删除和查找操作中，都需要通过哈希函数计算出待操作关键字在哈希表中的位置，然后按照二次探测法的规则查找下一个空闲位置或者待操作关键字所在的位置。