C++使用哈希表

主要介绍map和unordered_map的使用和区别

map

底层实现是 红黑树（自平衡的二叉查找树）。
因为使用了红黑树，std::map 的元素总是 按键的顺序（升序或降序）排列。
每次插入、删除和查找元素时，红黑树会保持自平衡，以确保查找的时间复杂度为 O(log n)。

unordered_map

底层实现是 哈希表（Hash Table）。
哈希表并不保证元素按任何顺序排列，因此插入顺序和查找顺序可能是不可预测的。
插入、删除和查找元素的平均时间复杂度是 O(1)，但在最坏情况下，可能会退化到 O(n)，例如哈希冲突过多时。

使用语法

map<string, int> use_map;
unordered_map<string, int> use_unordered;

int main() {
    use_map["second"] = 2;
    use_map["first"] = 1;
    use_map["third"] = 3;
    use_map["forth"] = 4;
    use_map["fifth"] = 5;

    use_unordered["second"] = 2;
	use_unordered["first"] = 1;
    use_unordered["third"] = 3;
    use_unordered["forth"] = 4;
    use_unordered["fifth"] = 5;
	
    for (auto p : use_map) {
        cout << p.first << " ";
    } // 总是输出fifth first forth second third 
    cout << endl;
    
    for (auto p : use_unordered) {
        cout << p.first << " ";
    } // 输出不一定是有序的
    cout << endl;
}

总结

特性	`std::map`	`std::unordered_map`
查找、插入、删除的复杂度	O(log n)	O(1) 平均，O(n) 最坏
是否保证顺序	按键排序，保证顺序，默认升序	不保证顺序
内存消耗	相对较高，保持树的结构	较高，依赖于哈希表和桶的数量
使用场景	需要顺序、排序、定制比较函数	高效查找、插入、删除，无需排序