C++ STL中，哈希表对应的容器是unordered_map（since C++ 11）。

STL中，map 对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map 对应 哈希表，哈希表的特点就是查找效率高，时间复杂度为常数级别 O(1)， 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况，使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话，则可以用 map 容器。

说明

  • unordered_map 是一种关联容器，用于存储由关键值 (Key Value，以下称为Key 值) 和映射值 (Mapped Value，以下称为映射值) 组成的元素，并且允许根据其 Key 值快速检索各个元素。

  • 在 unordered_map 容器中，Key 值通常用来唯一标识元素，映射值是与该 Key 值关联内容的对象。Key 值与映射值的类型可能不同。

  • 在 unordered_map 内部，元素没有按照其 Key 值与映射值的任何顺序进行排序 ，而是根据它们的 Hash 值组织成桶，允许它们通过其 Key 值直接快速访问单个元素（通常具有常数等级的平均时间复杂度）。

  • unordered_map 容器与 map 容器相比，通过 Key 值访问各个元素的速度更快，然而通过其元素子集进行范围迭代的效率通常较低。

  • unordered_map 实现了直接访问操作符 (operator[])，它允许使用 Key 值作为输入参数，直接访问映射值。

  • 容器中的迭代器至少是前向迭代器。

使用

  • 引入头文件

  • unordered_map m;

  • m.size(); //元素数量

  • m.insert(x);

  • m.find(key);

    m.count(key);

  • m.erese(key);

  • m[key] → value

例子

  • 基本使用

    #include <iostream>
    #include <unordered_map>
    using namespace std;
    int main(){
    	unordered_map<char,int> m;
    	m['a'] = 9;
    	m['?'] = 5;
    	m['z'] = 99;
    	m['A'] = 50;
    	m['Z'] = -2;
    	m[' '] = 0;

        //输出元素个数
        cout << m.size() << endl;

        //查找' '元素是否存在，若存在，输出其对应的值；
        if(m.count(' ') == 1){
            cout << m[' '] << endl;
        }

        //输出内部所有元素，体现无序性
        for(auto it = m.begins(); it != m.end(); it++){
            cout << it->first << " " << it->second << endl;
        }
        return 0;
    }
    输出结果：
    6
    0
    Z -2
      0
    A 50
    ? 5
    z 99
    a 9

  • Leetcode 1. 两数之和

    #include <unordered_map>
    class Solution{
    public:
    	vector<int> twoSum(vector<int> &numbers, int target)
        {
            //Key is the number and value is its index in the vector
            unordered_map<int,int> hash;
            vector<int> result;
            for <int i = 0; i < numbers.size(); i++){
                int numberToFind = target - number[i];
                //if numberToFind is found in map, return them
                if (hash.find(numberToFind) != hash.end()){
                    result.push_back(hash[numberToFind);
                    result.push_back(i);
                    return result;
                }
                    hash[numbers[i]] = i;                      
            }
            return result;                              
        }
    };