面试题， hash 和 map 的区别？？？

刷到 v2 在讨论鹅厂的技术水平
https://www.v2ex.com/t/492998?p=1

刚好昨天面试，和鹅厂面试官聊了一下，有个问题耿耿于怀，想来 v2 学习一下

问题就是标题，hash 和 map 的区别

我第一反应是这俩不是一个对比范畴的吧，hash 是算法，map 是数据结构？和面试官提了一嘴，貌似不能这么对比吧？

然后想起来 c++ 中 map 是用红黑树实现的，又问了一下，是讨论 c++ 吗？回答是不是，就是讨论数据结构……

没办法，强行回答，hash 一般是用数组实现，O(1)，map 是用树，O(log n)

---
### 事后搜索

map
> In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

hash 有两个结果
hash function

这是我理解的 hash 函数

> A hash function is any function that can be used to map data of arbitrary size to data of a fixed size.


hash table

hash 表，我理解这是不是也是一种 map ？

> In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.



---
### 最后

就算 c++ 里，std 里的 hash 是 c++11 加进去的函数模版
最常用的 hash 数据结构是 unordered_map ……


来 v2 学习一下我考虑的不周的地方