1
template <typename Key, typename Value, typename Hash = std::hash<Key>>
2
class OpenAddressMap {
3
    enum class State : uint8_t { EMPTY, OCCUPIED, DELETED };
4

5
    struct Slot {
6
        Key    key;
7
        Value  value;
8
        State  state = State::EMPTY;
9
    };
10

11
    std::vector<Slot> _slots;
12
    std::size_t _size = 0;
13
    std::size_t _capacity;
14
    Hash _hasher;
15

16
    static constexpr float MAX_LOAD = 0.7f;  // 开放寻址必须 < 1
17

18
    std::size_t _probe(std::size_t hash) const {
19
        return hash % _capacity;
20
    }
21

22
    std::size_t _next(std::size_t idx) const {
23
        return (idx + 1) % _capacity;  // 线性探测
24
    }
25

26
public:
27
    OpenAddressMap(std::size_t cap = 16)
28
        : _slots(cap), _capacity(cap) {}
29

30
    // ========== 查找 ==========
31
    Value* find(const Key& key) {
32
        std::size_t idx = _probe(_hasher(key));
33

34
        for (std::size_t i = 0; i < _capacity; ++i) {
35
            if (_slots[idx].state == State::EMPTY) {
36
                return nullptr;  // 碰到空位，说明不存在
37
            }
38
            if (_slots[idx].state == State::OCCUPIED && _slots[idx].key == key) {
39
                return &_slots[idx].value;
40
            }
41
            idx = _next(idx);
42
        }
43
        return nullptr;
44
    }
45

46
    // ========== 插入 ==========
47
    void insert(const Key& key, const Value& value) {
48
        if (static_cast<float>(_size + 1) / _capacity >= MAX_LOAD) {
49
            _grow();
50
        }
51

52
        std::size_t idx = _probe(_hasher(key));
53

54
        while (true) {
55
            if (_slots[idx].state != State::OCCUPIED) {
56
                // 空位或已删除位 → 放这里
57
                _slots[idx] = {key, value, State::OCCUPIED};
58
                ++_size;
59
                return;
60
            }
61
            if (_slots[idx].key == key) {
62
                // 已存在 → 更新
63
                _slots[idx].value = value;
64
                return;
65
            }
66
            idx = _next(idx);
67
        }
68
    }
69

70
    // ========== 删除（标记删除）==========
71
    bool erase(const Key& key) {
72
        std::size_t idx = _probe(_hasher(key));
73

74
        for (std::size_t i = 0; i < _capacity; ++i) {
75
            if (_slots[idx].state == State::EMPTY) return false;
76
            if (_slots[idx].state == State::OCCUPIED && _slots[idx].key == key) {
77
                _slots[idx].state = State::DELETED;  // 不能置 EMPTY！
78
                --_size;
79
                return true;
80
            }
81
            idx = _next(idx);
82
        }
83
        return false;
84
    }
85

86
    // ========== 扩容 ==========
87
    void _grow() {
88
        std::size_t new_cap = _capacity * 2;
89
        std::vector<Slot> new_slots(new_cap);
90

91
        // 搬运所有 OCCUPIED 的元素
92
        for (auto& slot : _slots) {
93
            if (slot.state == State::OCCUPIED) {
94
                std::size_t idx = _hasher(slot.key) % new_cap;
95
                while (new_slots[idx].state == State::OCCUPIED) {
96
                    idx = (idx + 1) % new_cap;
97
                }
98
                new_slots[idx] = {std::move(slot.key),
99
                                   std::move(slot.value),
100
                                   State::OCCUPIED};
101
            }
102
        }
103

104
        _slots = std::move(new_slots);
105
        _capacity = new_cap;
106
        // 注意：DELETED 标记在 rehash 后全部消失 → 自动"清洗"
107
    }
108

109
    std::size_t size() const { return _size; }
110
    float load_factor() const { return static_cast<float>(_size) / _capacity; }
111
};

1
// Robin Hood 插入的核心逻辑（概念性伪代码）
2
void robin_hood_insert(Key key, Value value) {
3
    size_t idx = hash(key) % capacity;
4
    size_t dist = 0;  // 当前元素的探测距离
5

6
    while (true) {
7
        if (slots[idx].empty()) {
8
            // 空位：直接放
9
            slots[idx] = {key, value, dist};
10
            return;
11
        }
12

13
        if (dist > slots[idx].probe_distance) {
14
            // "劫富济贫"：新元素离家更远 → 抢占这个位置
15
            std::swap(key, slots[idx].key);
16
            std::swap(value, slots[idx].value);
17
            std::swap(dist, slots[idx].probe_distance);
18
        }
19

20
        idx = (idx + 1) % capacity;
21
        ++dist;
22
    }
23
}

1
// 什么时候用 map？
2
// 1. 需要有序遍历
3
for (auto& [key, value] : ordered_map) {
4
    // key 按字典序遍历 ✅
5
}
6

7
// 2. 需要范围查询
8
auto it_lo = ordered_map.lower_bound("banana");
9
auto it_hi = ordered_map.upper_bound("mango");
10
// 遍历 [banana, mango] 范围内的元素 ✅
11

12
// 3. 什么时候用 unordered_map？
13
// 绝大多数情况！只要不需要有序性和范围查询。
14
hash_map["key"] = 42;       // O(1) 插入
15
if (hash_map.count("key"))  // O(1) 查找

1
struct Point {
2
    int x, y;
3

4
    // unordered_map 需要 operator==
5
    bool operator==(const Point& o) const {
6
        return x == o.x && y == o.y;
7
    }
8
};
9

10
// 方案一：提供哈希函数对象
11
struct PointHash {
12
    std::size_t operator()(const Point& p) const {
13
        auto h1 = std::hash<int>{}(p.x);
14
        auto h2 = std::hash<int>{}(p.y);
15
        return h1 ^ (h2 * 2654435761ULL + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
16
    }
17
};
18

19
std::unordered_map<Point, std::string, PointHash> point_map;
20
std::unordered_set<Point, PointHash> point_set;
21

22
// 方案二：特化 std::hash（更优雅）
23
namespace std {
24
    template <>
25
    struct hash<Point> {
26
        std::size_t operator()(const Point& p) const {
27
            auto h1 = hash<int>{}(p.x);
28
            auto h2 = hash<int>{}(p.y);
29
            return h1 ^ (h2 * 2654435761ULL + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
30
        }
31
    };
32
}
33

34
// 特化后可以直接用，无需传第三个模板参数
35
std::unordered_map<Point, std::string> point_map2;  // ✅

1
std::vector<int> twoSum(std::vector<int>& nums, int target) {
2
    // key = 数值, value = 下标
3
    std::unordered_map<int, int> seen;
4

5
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
6
        int complement = target - nums[i];
7

8
        auto it = seen.find(complement);
9
        if (it != seen.end()) {
10
            return {it->second, i};  // 找到配对
11
        }
12

13
        seen[nums[i]] = i;  // 记录当前数
14
    }
15
    return {};
16
}
17
// 时间 O(n), 空间 O(n)

1
std::vector<std::vector<std::string>> groupAnagrams(
2
    std::vector<std::string>& strs)
3
{
4
    std::unordered_map<std::string, std::vector<std::string>> groups;
5

6
    for (auto& s : strs) {
7
        std::string key = s;
8
        std::sort(key.begin(), key.end());  // "eat" → "aet"
9
        groups[key].push_back(s);
10
    }
11

12
    std::vector<std::vector<std::string>> result;
13
    for (auto& [key, group] : groups) {
14
        result.push_back(std::move(group));
15
    }
16
    return result;
17
}
18
// 时间 O(n × k log k), k = 最长字符串长度
19
// 空间 O(n × k)

1
int lengthOfLongestSubstring(const std::string& s) {
2
    std::unordered_set<char> window;
3
    int left = 0, max_len = 0;
4

5
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
6
        // 收缩窗口直到没有重复
7
        while (window.count(s[right])) {
8
            window.erase(s[left]);
9
            ++left;
10
        }
11

12
        window.insert(s[right]);
13
        max_len = std::max(max_len, right - left + 1);
14
    }
15
    return max_len;
16
}
17
// 时间 O(n), 空间 O(min(n, charset))

1
int lengthOfLongestSubstring_v2(const std::string& s) {
2
    std::unordered_map<char, int> last_pos;  // 字符 → 最后出现的下标
3
    int left = 0, max_len = 0;
4

5
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
6
        if (last_pos.count(s[right]) && last_pos[s[right]] >= left) {
7
            left = last_pos[s[right]] + 1;  // 直接跳！
8
        }
9
        last_pos[s[right]] = right;
10
        max_len = std::max(max_len, right - left + 1);
11
    }
12
    return max_len;
13
}
14
// 时间 O(n), 空间 O(min(n, charset))
15
// 比 set 版本更快：left 只跳不走

1
int longestConsecutive(std::vector<int>& nums) {
2
    std::unordered_set<int> num_set(nums.begin(), nums.end());
3
    int max_len = 0;
4

5
    for (int num : num_set) {
6
        // 关键优化：只从序列起点开始计数
7
        // 如果 num-1 存在，说明 num 不是起点，跳过
8
        if (num_set.count(num - 1)) continue;
9

10
        // num 是某个连续序列的起点
11
        int length = 1;
12
        while (num_set.count(num + length)) {
13
            ++length;
14
        }
15

16
        max_len = std::max(max_len, length);
17
    }
18
    return max_len;
19
}
20
// 时间 O(n)：每个元素最多被访问两次（一次外层循环，一次内层 while）
21
// 空间 O(n)

1
bool isValidSudoku(std::vector<std::vector<char>>& board) {
2
    // 每行、每列、每个 3×3 宫各用一个 set
3
    std::array<std::unordered_set<char>, 9> rows, cols, boxes;
4

5
    for (int i = 0; i < 9; ++i) {
6
        for (int j = 0; j < 9; ++j) {
7
            char c = board[i][j];
8
            if (c == '.') continue;
9

10
            int box_idx = (i / 3) * 3 + (j / 3);  // 3×3 宫的编号
11

12
            // 任一集合中已存在 → 无效
13
            if (rows[i].count(c) || cols[j].count(c) || boxes[box_idx].count(c)) {
14
                return false;
15
            }
16

17
            rows[i].insert(c);
18
            cols[j].insert(c);
19
            boxes[box_idx].insert(c);
20
        }
21
    }
22
    return true;
23
}
24
// 时间 O(81) = O(1), 空间 O(81) = O(1)

1
#include <map>
2
#include <string>
3
#include <functional>
4

5
class ConsistentHash {
6
    // 用 std::map（有序！）存哈希环上的虚拟节点
7
    std::map<std::size_t, std::string> _ring;
8
    int _virtual_nodes;  // 每台机器的虚拟节点数
9

10
public:
11
    ConsistentHash(int virtual_nodes = 150,
12
                   std::vector<std::string> servers = {})
13
        : _virtual_nodes(virtual_nodes)
14
    {
15
        for (auto& srv : servers) add_server(srv);
16
    }
17

18
    void add_server(const std::string& server) {
19
        for (int i = 0; i < _virtual_nodes; ++i) {
20
            std::size_t h = std::hash<std::string>{}(
21
                server + "#" + std::to_string(i));
22
            _ring[h] = server;
23
        }
24
    }
25

26
    void remove_server(const std::string& server) {
27
        for (int i = 0; i < _virtual_nodes; ++i) {
28
            std::size_t h = std::hash<std::string>{}(
29
                server + "#" + std::to_string(i));
30
            _ring.erase(h);
31
        }
32
    }
33

34
    // 给定 key，找到负责它的机器
35
    std::string get_server(const std::string& key) const {
36
        if (_ring.empty()) return "";
37

38
        std::size_t h = std::hash<std::string>{}(key);
39
        // 在环上找到 >= h 的第一个节点
40
        auto it = _ring.lower_bound(h);
41
        if (it == _ring.end()) {
42
            it = _ring.begin();  // 环绕回环首
43
        }
44
        return it->second;
45
    }
46
};

1
#include <unordered_map>
2
#include <memory>
3
#include <string>
4
#include <functional>
5
#include <iostream>
6

7
// 资源基类
8
class Resource {
9
public:
10
    virtual ~Resource() = default;
11
    virtual std::size_t memory_size() const = 0;
12
    virtual const std::string& type_name() const = 0;
13
};
14

15
// 具体资源类型
16
class Texture : public Resource {
17
    int _width, _height;
18
    std::vector<uint8_t> _pixels;
19

20
public:
21
    Texture(int w, int h) : _width(w), _height(h), _pixels(w * h * 4) {}
22
    std::size_t memory_size() const override { return _pixels.size(); }
23
    const std::string& type_name() const override {
24
        static std::string name = "Texture";
25
        return name;
26
    }
27
};
28

29
class AudioClip : public Resource {
30
    std::vector<float> _samples;
31

32
public:
33
    AudioClip(std::size_t sample_count) : _samples(sample_count) {}
34
    std::size_t memory_size() const override { return _samples.size() * sizeof(float); }
35
    const std::string& type_name() const override {
36
        static std::string name = "AudioClip";
37
        return name;
38
    }
39
};
40

41
// ===== 资源管理器 =====
42
class ResourceManager {
43
    // 核心：路径 → 资源的哈希表
44
    std::unordered_map<std::string, std::shared_ptr<Resource>> _cache;
45

46
    // 资源加载工厂（按扩展名分发）
47
    using LoaderFunc = std::function<std::shared_ptr<Resource>(const std::string&)>;
48
    std::unordered_map<std::string, LoaderFunc> _loaders;
49

50
public:
51
    // 注册加载器
52
    void register_loader(const std::string& extension, LoaderFunc loader) {
53
        _loaders[extension] = std::move(loader);
54
    }
55

56
    // 获取资源（懒加载 + 缓存）
57
    template <typename T>
58
    std::shared_ptr<T> get(const std::string& path) {
59
        // 1. 缓存命中 → O(1) 返回
60
        auto it = _cache.find(path);
61
        if (it != _cache.end()) {
62
            return std::dynamic_pointer_cast<T>(it->second);
63
        }
64

65
        // 2. 缓存未命中 → 加载并缓存
66
        std::string ext = path.substr(path.rfind('.'));
67
        auto loader_it = _loaders.find(ext);
68
        if (loader_it == _loaders.end()) {
69
            return nullptr;  // 不支持的格式
70
        }
71

72
        auto resource = loader_it->second(path);
73
        _cache[path] = resource;  // 缓存
74
        return std::dynamic_pointer_cast<T>(resource);
75
    }
76

77
    // 卸载指定资源
78
    void unload(const std::string& path) {
79
        _cache.erase(path);
80
    }
81

82
    // 卸载所有无引用的资源
83
    void gc() {
84
        for (auto it = _cache.begin(); it != _cache.end(); ) {
85
            if (it->second.use_count() == 1) {  // 只有 cache 持有引用
86
                it = _cache.erase(it);
87
            } else {
88
                ++it;
89
            }
90
        }
91
    }
92

93
    // 预加载（提前 reserve 减少 rehash）
94
    void preload(const std::vector<std::string>& paths) {
95
        _cache.reserve(_cache.size() + paths.size());
96
        for (auto& path : paths) {
97
            get<Resource>(path);  // 触发加载
98
        }
99
    }
100

101
    std::size_t cached_count() const { return _cache.size(); }
102

103
    std::size_t total_memory() const {
104
        std::size_t total = 0;
105
        for (auto& [path, res] : _cache) {
106
            total += res->memory_size();
107
        }
108
        return total;
109
    }
110
};