首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

面试题, hash 和 map 的区别???

  •  
  •   zwpaper · 240 天前用 iPhone 发布 · 2799 次点击
    这是一个创建于 240 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    15 回复  |  直到 2018-09-29 00:45:40 +08:00
        1
    enenaaa   240 天前
    人家问的是 hash table 和 map 对比吧。 这不是面试常识?
        2
    0x11901   240 天前
    其实我觉得楼主答得不错,知识面也挺广的……
    面试官应该就如楼上所说就想问问红黑树实现的 map 和哈希表实现的 hash_map 区别……
        3
    congeec   240 天前 via iPhone
    面试不是把问题答出来就行。多沟通,弄清人家的意图,掌握主动权啊
        4
    leotso   240 天前 via iPhone
    @congeec 嗯,有道理,越来越觉得面试中的沟通很重要
        5
    seeker   240 天前
    根据楼主的描述,是面试官沟通能力欠佳,或者是不愿沟通。
        6
    across   240 天前 via iPhone
    感觉面试 unordered_map 和 map 成必考题了
        7
    zwpaper   240 天前 via iPhone
    @enenaaa 我理解的 hash table 也是 map 的一种吧,毕竟 hash table 也叫 hash map ……
        8
    zwpaper   240 天前 via iPhone
    @congeec 有沟通的,没写太细致,聊完 hash table 和树的区别,面试官也认可了,只是我还是觉得不应该把 map 单一地认为就是树
        9
    fireapp   240 天前 via iPhone
    hash 是算法,map 是数据结构
        10
    wingyiu   240 天前   ♥ 1
    java: Map HashMap TreeMap
        11
    ssynhtn   240 天前
    hash 可以实现 map, 但是 map 有其它类型的, 比如 TreeMap
        12
    zwpaper   240 天前 via iPhone
    @across 主要我面的是非 c++ 岗,考我 unordered_map 真可能把我考住的…而且面试官强调的是通用的 map,非 c++。

    而且,作为一名 gopher,map 是 hash table 实现的…真差点尴尬了
        13
    ChristopherWu   240 天前   ♥ 1
    @zwpaper 除了 C++, python 也是有 OrderedDict 的,也是有序 map。

    怎么说呢,知道 map 有『有序』与『无序』两种不同的实现方式,也是挺重要的。
        14
    d18   240 天前
    hash 特指哈希表?
    map 的话,tree 和 hash 是常见的实现方式,但是单从字面理解,只要是实现了 mapping 的功能就行,甚至可以是比如一个数组,然后分别用连续两个元素保存键值对。
        15
    20015jjw   240 天前 via Android
    奇怪的题目..
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   728 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 20ms · UTC 20:27 · PVG 04:27 · LAX 13:27 · JFK 16:27
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1