C++的unordered_map

C++

unordered_map的底层数据结构

C++的unordered_map是基于开放寻址法或链地址法实现的哈希表结构

链地址法

unordered_map 通常采用链地址法解决哈希冲突。通过将哈希表的每个桶（bucket）设计为一个链表，所有哈希值相同的元素都被放置在同一个链表中。

开放地址法

开放寻址法不使用链表，而是通过在哈希表中寻找下一个可用的位置来插入冲突的元素。

下一个位置可能就是下一个bucket。当然，也有可能是使用第二个哈希函数，重新计算得到下一个位置。

当然，这只是最简单的两种哈希方式。这种在rehash的时候的开销非常大。所以还有其他一些常见的哈希方式。这些一般会在一些对数据读写有更高要求的应用中有需求。比如关系型数据库的哈希索引之类的。

可扩展哈希

如果发现某个bucket超过容量了，只会把一个bucket变成两个bucket。不会触发其他bucket的reash。（主要可以参看cmu15445 bustub实现的extendible hash）

cuckoo哈希（布谷鸟哈希）

Cuckoo Hashing保证了最坏情况下O(1)的查找时间。他主要使用了两个哈希函数，一个key会放置到其中某一个哈希函数空闲的bucket。如果两个bucket都满了，就会选择pop其中一个bucket。

遍历时删除

遍历时一般都会使用自带的迭代器。但是如果在迭代中有删除操作，不能使用迭代器++的方式。erase会返回下一个可用的迭代器。所以直接选用这一迭代器作为下一个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void correct_deletion_with_iterator() {
    std::cout << "\n=== ✅ 方法1: 使用erase返回的迭代器 ===\n";
    
    std::unordered_map<std::string, int> map = {
        {"apple", 1}, {"banana", 2}, {"cherry", 3}, 
        {"date", 4}, {"elderberry", 5}, {"fig", 6}
    };
    
    std::cout << "删除前: ";
    for (const auto& [key, value] : map) {
        std::cout << key << "(" << value << ") ";
    }
    std::cout << "\n";
    
    std::cout << "删除所有偶数值的元素...\n";
    
    // 关键：使用erase返回的迭代器
    for (auto it = map.begin(); it != map.end(); ) {
        if (it->second % 2 == 0) {
            std::cout << "  删除: " << it->first << " -> " << it->second << "\n";
            it = map.erase(it);  // ✅ erase返回下一个有效迭代器
        } else {
            ++it;  // ✅ 只有不删除时才递增迭代器
        }
    }
    
    std::cout << "删除后: ";
    for (const auto& [key, value] : map) {
        std::cout << key << "(" << value << ") ";
    }
    std::cout << "\n";
}