冲突处理方法（链地址法与开放地址法）

哈希表数组（大小M）
+------+   +------+   +------+   +------+
| 0    |   | 1    |   | 2    |   | 3    |
+------+   +------+   +------+   +------+
   |           |           |          |
   v           v           v          v
 [节点]      [节点]      [节点]     [节点]
  / \         / \         / \        / \
 ...         ...         ...        ...

#include <iostream>
#include <vector>
#include <list>   // 使用标准库链表
using namespace std;

class ChainedHashTable {
private:
    int bucket_count;            // 桶的个数
    vector<list<int>> buckets;   // 每个桶是一个链表

    int hashFunction(int key) {
        return key % bucket_count;
    }

public:
    ChainedHashTable(int size) : bucket_count(size) {
        buckets.resize(bucket_count);
    }

    // 插入一个键
    void insert(int key) {
        int idx = hashFunction(key);
        // 检查是否已存在（链表遍历）
        for (int val : buckets[idx]) {
            if (val == key) return;   // 已存在，不重复插入
        }
        buckets[idx].push_back(key);  // 插到链表末尾
    }

    // 查找键是否存在
    bool search(int key) {
        int idx = hashFunction(key);
        for (int val : buckets[idx]) {
            if (val == key) return true;
        }
        return false;
    }

    // 删除键
    bool remove(int key) {
        int idx = hashFunction(key);
        // list的remove方法会删除所有匹配的元素，这里只删一个
        auto it = buckets[idx].begin();
        while (it != buckets[idx].end()) {
            if (*it == key) {
                buckets[idx].erase(it);
                return true;
            }
            ++it;
        }
        return false;
    }

    void print() {
        for (int i = 0; i < bucket_count; ++i) {
            cout << i << ": ";
            for (int val : buckets[i]) cout << val << " -> ";
            cout << "空" << endl;
        }
    }
};

int main() {
    ChainedHashTable ht(5);          // 5个桶
    ht.insert(10);                   // 10 % 5 = 0 => 桶0
    ht.insert(15);                   // 15 % 5 = 0 => 桶0（冲突，放在链表里）
    ht.insert(22);                   // 22 % 5 = 2 => 桶2
    ht.insert(3);                    // 3 % 5 = 3 => 桶3

    cout << "链地址法哈希表：" << endl;
    ht.print();

    cout << "查找15: " << (ht.search(15) ? "找到" : "未找到") << endl;
    ht.remove(15);
    cout << "删除15后查找15: " << (ht.search(15) ? "找到" : "未找到") << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

enum State { EMPTY, ACTIVE, DELETED };  // 状态：空、有效、已删除

class OpenHashTable {
private:
    struct Node {
        int key;
        State state;
        Node() : key(0), state(EMPTY) {}
    };
    vector<Node> table;
    int capacity;               // 表大小

    int hashFunction(int key) {
        return key % capacity;
    }

public:
    OpenHashTable(int size) : capacity(size) {
        table.resize(capacity);
    }

    // 插入键（如果已存在则返回false）
    bool insert(int key) {
        int index = hashFunction(key);
        int start = index;
        while (table[index].state == ACTIVE) {
            if (table[index].key == key) {
                return false;   // 已存在
            }
            index = (index + 1) % capacity;
            if (index == start) {
                return false;   // 表满了
            }
        }
        table[index].key = key;
        table[index].state = ACTIVE;
        return true;
    }

    // 查找键
    bool search(int key) {
        int index = hashFunction(key);
        int start = index;
        while (table[index].state != EMPTY) {
            if (table[index].state == ACTIVE && table[index].key == key) {
                return true;
            }
            index = (index + 1) % capacity;
            if (index == start) break;
        }
        return false;
    }

    // 删除键（标记为DELETED）
    bool remove(int key) {
        int index = hashFunction(key);
        int start = index;
        while (table[index].state != EMPTY) {
            if (table[index].state == ACTIVE && table[index].key == key) {
                table[index].state = DELETED;
                return true;
            }
            index = (index + 1) % capacity;
            if (index == start) break;
        }
        return false;
    }

    void print() {
        for (int i = 0; i < capacity; ++i) {
            cout << i << ": ";
            if (table[i].state == EMPTY) cout << "空";
            else if (table[i].state == DELETED) cout << "已删除";
            else cout << table[i].key;
            cout << endl;
        }
    }
};

int main() {
    OpenHashTable ht(7);
    ht.insert(10);   // 10%7=3
    ht.insert(22);   // 22%7=1
    ht.insert(31);   // 31%7=3 -> 冲突，线性探测到4
    ht.insert(4);    // 4%7=4 -> 冲突（被31占了），探测到5
    ht.insert(15);   // 15%7=1 -> 冲突，探测到2
    ht.insert(28);   // 28%7=0
    ht.insert(17);   // 17%7=3 -> 冲突，探测到4（已占）->5（已占）->6

    cout << "开放地址法（线性探测）表：" << endl;
    ht.print();

    cout << "查找22: " << (ht.search(22) ? "找到" : "未找到") << endl;
    ht.remove(22);
    cout << "删除22后查找22: " << (ht.search(22) ? "找到" : "未找到") << endl;

    // 再插入一个新键，验证惰性删除不影响
    ht.insert(35);   // 35%7=0 -> 冲突（0已有28），探测到1（已删除）->插入1
    cout << "插入35后：" << endl;
    ht.print();
    return 0;
}