Map、Dictionary、Hash Table 有哪些异同？
dictionary 跟 map 其实是同一个东西，只是在不同场合叫法不同。

dictionary 的中文是字典，map在中文是映射，也有地图的意思。查字典，查地图，都是通过某个信息，去找到另一个信息。比如通过单词的拼写找到单词的具体含义。

类比查字典过程，单词的拼写为 key, 单词的具体含义为 value。dictionary 就是通过key，找到value，有时也将 dictionary说成是 key-value 结构。只要达到查找目的，都可以叫做 dictionary。具体怎么找，可以有不同实现。

比如，最简单是将 key，value 放在一起，线性排。

```
k1, k2, k3, k4, k4 ....
v1, v2, v3, v4, v5 ....
```

当需要从 key 找到对应的 value 时，就从头到尾遍历过去。依次判断 k1, k2, k3, k4 是不是等于key, 当等于的时候，就找到 key的具体位置，从而也就找到了value。

  

但这样从头到尾遍历，速度就太慢了，时间复杂度为 O(N)。N为数据的大小。

为了快速从key找到value。dictionary(或者说map)的通常有两种实现方式。

1. 二叉树
2. 哈希(hash)表

二叉树查找的时间复杂度为 O(logN)，哈希表的时间复杂度大致为 O(1)。二叉树也分红黑树，AVL树等。哈希表的速度很快，很多语言内置的dictionary 都使用哈希表来实现，但它通常会浪费一些存储空间。这部分有兴趣去看数据结构的书。

hash_map 其实就是使用 hash 表实现的 map。注意，二叉树，哈希表仅仅是 dictionary 的实现方式，不能说 hash 就等于dictionary，实现方式可以有多种多样。

比如上面线性存储的实现，可以调整一下。当数据都放进来之后，先根据 key 来排序，再使用二分查找，就可以很快速地从 key 找到 value,这种实现简单快速，并省内存，有时会比 hash 的实现更好。适合于一些数据不会经常变动的情况。

C++ 11 的标准库中有个 unordered_map，就是采用哈希表使用的 map。在C++11之前，没有标准的哈希实现，很多第三方库实现了哈希字典，基本都叫做 hash_map, 并应用广泛。所以C++11的实现就不能叫hash_map了，因为会造成很多现存的程序名字冲突。哈希实现的字典是无序，也就取了个不算太好的名字，unordered_map。