Lecture 14: 散列与哈希表（Hashing & Hash Tables）（对应课程真实讲座 L24）

#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>
using namespace std;

class ChainedHashSet {
public:
    explicit ChainedHashSet(size_t bucketCount = 8)
        : buckets_(bucketCount), size_(0) {}

    // 插入：重复键返回 false；否则头插并视负载因子决定是否扩容
    bool insert(const string& key) {
        size_t idx = hashIndex(key);
        for (const string& s : buckets_[idx]) {
            if (s == key) return false;            // 哈希集合不允许重复
        }
        buckets_[idx].push_front(key);             // 头插：O(1)
        ++size_;
        if (size_ > buckets_.size() * 0.75) rehash();   // 负载 > 0.75 → 扩容
        return true;
    }

    bool contains(const string& key) const {
        for (const string& s : buckets_[hashIndex(key)]) {
            if (s == key) return true;             // 链很短时近似 O(1)
        }
        return false;
    }

    bool erase(const string& key) {
        auto& chain = buckets_[hashIndex(key)];
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if (*it == key) { chain.erase(it); --size_; return true; }
        }
        return false;
    }

    size_t size() const { return size_; }

    void dump() const {
        for (size_t i = 0; i < buckets_.size(); ++i) {
            cout << "桶[" << i << "]:";
            for (const string& s : buckets_[i]) cout << " -> " << s;
            cout << "\n";
        }
    }

private:
    // 经典的“乘 31 累加”字符串哈希（类似 Java String.hashCode 的思路）
    size_t hashIndex(const string& key) const {
        size_t h = 0;
        for (char c : key) h = h * 31 + static_cast<unsigned char>(c);
        return h % buckets_.size();                // 取模落桶
    }

    void rehash() {
        vector<list<string>> old = std::move(buckets_);
        buckets_.assign(old.size() * 2, list<string>());  // 桶数翻倍
        size_ = 0;                                 // 计数清零后整体重插
        for (auto& chain : old)
            for (auto& s : chain) insert(s);
    }

    vector<list<string>> buckets_;   // 桶数组：每桶一条链表
    size_t size_;                    // 元素总数
};

int main() {
    ChainedHashSet s;
    for (const string& w : {"apple", "banana", "pear", "grape",
                            "plum", "peach", "kiwi", "melon",
                            "fig", "date"}) {      // 第 9 个元素会触发 rehash
        cout << "插入 " << w << (s.insert(w) ? " 成功" : " 重复") << "\n";
    }
    cout << "再次插入 apple -> " << (s.insert("apple") ? "成功" : "拒绝重复") << "\n";
    cout << "contains(pear) = " << s.contains("pear") << "\n";
    cout << "contains(kiwi) = " << s.contains("kiwi") << "\n";
    cout << "erase(pear)    = " << s.erase("pear") << "\n";
    cout << "erase(pear)    = " << s.erase("pear") << "（第二次已删不到）\n";
    cout << "当前 size = " << s.size() << "\n\n";
    s.dump();
    return 0;
}

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

// 槽位三种状态：EMPTY 从未用过 / USED 在用 / TOMBSTONE 已删但曾用过
enum class Slot { EMPTY, USED, TOMBSTONE };

class LinearHashSet {
public:
    explicit LinearHashSet(size_t cap = 7)
        : status_(cap, Slot::EMPTY), values_(cap, 0), size_(0) {}

    bool insert(int key) {
        if (contains(key)) return false;           // 先查重
        int tomb = -1;                             // 探测途中遇到的最靠前墓碑
        size_t start = hashIndex(key);
        for (size_t step = 0; step < status_.size(); ++step) {
            size_t pos = (start + step) % status_.size();   // 环形探测
            if (status_[pos] == Slot::TOMBSTONE && tomb < 0) tomb = (int)pos;
            if (status_[pos] == Slot::EMPTY) {     // 探测链终点
                size_t target = tomb < 0 ? pos : (size_t)tomb; // 优先复用墓碑
                status_[target] = Slot::USED; values_[target] = key;
                ++size_;
                return true;
            }
        }
        return false;                              // 表满（本例容量大于元素数）
    }

    bool contains(int key) const {
        size_t start = hashIndex(key);
        for (size_t step = 0; step < status_.size(); ++step) {
            size_t pos = (start + step) % status_.size();
            if (status_[pos] == Slot::EMPTY) return false;  // 空位 = 探测链尽头
            if (status_[pos] == Slot::USED && values_[pos] == key) return true;
            // TOMBSTONE：绝不能停，必须继续向后探测
        }
        return false;
    }

    bool erase(int key) {
        size_t start = hashIndex(key);
        for (size_t step = 0; step < status_.size(); ++step) {
            size_t pos = (start + step) % status_.size();
            if (status_[pos] == Slot::EMPTY) return false;
            if (status_[pos] == Slot::USED && values_[pos] == key) {
                status_[pos] = Slot::TOMBSTONE;    // 打墓碑，而不是置 EMPTY！
                --size_;
                return true;
            }
        }
        return false;
    }

    size_t size() const { return size_; }

    void dump() const {
        for (size_t i = 0; i < status_.size(); ++i) {
            char tag = status_[i] == Slot::USED ? 'U'
                     : status_[i] == Slot::TOMBSTONE ? 'T' : 'E';
            cout << "下标 " << i << " [" << tag << "]";
            if (status_[i] == Slot::USED) cout << "  值=" << values_[i];
            cout << "\n";
        }
    }

private:
    size_t hashIndex(int key) const {
        size_t h = static_cast<size_t>(key);  // 先转无符号再取模，杜绝负下标
        return h % status_.size();
    }
    vector<Slot> status_;
    vector<int>  values_;
    size_t size_;
};

int main() {
    LinearHashSet t(7);
    // 5、12、19、26 对 7 取模都等于 5 —— 故意制造连环冲突
    for (int k : {5, 12, 19, 26, 3, 0})
        cout << "插入 " << k << (t.insert(k) ? " 成功" : " 失败") << "\n";
    cout << "\n删除 12 后：\n";
    t.erase(12);
    t.dump();
    cout << "\ncontains(19) = " << t.contains(19)
         << "  ← 跨过墓碑 T 仍能找到\n";
    cout << "contains(12) = " << t.contains(12)
         << "  ← 已删，找不到\n";
    return 0;
}

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

// 判断数组中是否存在两个不同位置的数，其和等于 target
bool twoSum(const vector<int>& v, int target) {
    unordered_set<int> seen;             // 记录已扫描过的值
    for (int x : v) {
        if (seen.count(target - x)) return true;  // 补数已在前面出现过？
        seen.insert(x);                  // 先查后插：避免把 x 自己当配对
    }
    return false;
}

int main() {
    vector<int> v = {5, 1, 3, 1, 9};
    cout << "target=8  -> " << twoSum(v, 8) << "  (5+3)\n";
    cout << "target=2  -> " << twoSum(v, 2) << "  (两个 1)\n";
    cout << "target=9  -> " << twoSum(v, 9) << "  (不能只用单个 9)\n";
    cout << "target=18 -> " << twoSum(v, 18) << " (只有一个 9)\n";
    return 0;
}