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

[zwpaper]

刷到 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 学习一下我考虑的不周的地方

[enenaaa]

人家问的是 hash table 和 map 对比吧。 这不是面试常识？

[0x11901]

其实我觉得楼主答得不错，知识面也挺广的……
面试官应该就如楼上所说就想问问红黑树实现的 map 和哈希表实现的 hash_map 区别……

[congeec]

面试不是把问题答出来就行。多沟通，弄清人家的意图，掌握主动权啊

[leotso]

@congeec 嗯，有道理，越来越觉得面试中的沟通很重要

[seeker]

根据楼主的描述，是面试官沟通能力欠佳，或者是不愿沟通。

[across]

感觉面试 unordered_map 和 map 成必考题了

[zwpaper]

@enenaaa 我理解的 hash table 也是 map 的一种吧，毕竟 hash table 也叫 hash map ……

[zwpaper]

@congeec 有沟通的，没写太细致，聊完 hash table 和树的区别，面试官也认可了，只是我还是觉得不应该把 map 单一地认为就是树

[fireapp]

hash 是算法，map 是数据结构

[wingyiu]

java: Map HashMap TreeMap

[ssynhtn]

hash 可以实现 map, 但是 map 有其它类型的, 比如 TreeMap

[zwpaper]

@across 主要我面的是非 c++ 岗，考我 unordered_map 真可能把我考住的…而且面试官强调的是通用的 map，非 c++。

而且，作为一名 gopher，map 是 hash table 实现的…真差点尴尬了

[ChristopherWu]

@zwpaper 除了 C++, python 也是有 OrderedDict 的，也是有序 map。

怎么说呢，知道 map 有『有序』与『无序』两种不同的实现方式，也是挺重要的。

[d18]

hash 特指哈希表？
map 的话，tree 和 hash 是常见的实现方式，但是单从字面理解，只要是实现了 mapping 的功能就行，甚至可以是比如一个数组，然后分别用连续两个元素保存键值对。

[20015jjw]

奇怪的题目..