聊聊你所理解的散列、哈希、散列表、哈希表到底是什么？

[BearCookie]

如题，每次看到这个都感觉解释非常的抽象

看着看着把自己都看懵了，这到底是是个啥？？？

[fengxuejuan]

我最早用这玩意是在 perl 里，所以我天然的把这玩意当单射的字典。

[marcong95]

set = (key, value) => table[hash(key)] = value

就是这么一个东西

[BearCookie]

@marcong95 大佬的意思我明白 T^T，我的意思是文字解释很抽象，不好理解

[raaaaaar]

通过计算代替比较的查找方式，典型的空间换时间，查表法的电信应用，借鉴了数组的随机存取特性。

[blackshow]

哈希不就是散列吗？

[hoyixi]

很晕吧，一个重要原因是翻译，专有名词翻译很多花样，而且有些根本不该翻译。
不如看英文原版。

[luckyrayyy]

哈希和散列是同一个意思吧

[jimmyismagic]

因为 key 值不确定，比如有些整数非常大，如果按位置存储，则要开辟很大的空间，用 hash 的好处是把 key 值压缩到一个小的存储空间，这样虽然会出现碰撞，但查找的效率并不会下降多少。

[ztxcccc]

表->键值关系映射
哈希 /散列->压缩摘要
哈希表->用值的压缩摘要作为键的键值关系映射

[Pastsong]

Hash, 就是取一个对象的部分特征，通过某个 Hash 函数生成一个更简单的更易操作的值（字符串，整型等）。
把生成的 Hash 和原对象存在一个映射表里，这就是 Hash Table 。

[BearCookie]

@hoyixi 是的，翻译的味道怎么感觉都不对，哈希和散列是一个东西我知道，但是解释哈希是什么，就讲不出个真正的含义出来，总感觉很别扭

[caiji11]

有点忘了 数据结构书上有 随便找一本看看

[GBdG6clg2Jy17ua5]

哈希是 hash 的音译。本质是通过一个函数，将其转换成另外一个适合使用的值

[NotFoundEgg]

我认为 hash 可以理解为 通过特定规则得到的一个特征值

不同的对象有一定概率具有相同的特征值（ hash 碰撞）

所以需要设计这个规则（ hash 算法）来减少碰撞

[NotFoundEgg]

@NotFoundEgg 这应该是相对容易理解的说法了吧

[NotFoundEgg]

@NotFoundEgg
在同一规则下
不同的对象有概率具有相同的特征值（小概率）
但不同的特征值一定对应不同的对象

这样可以高效地对比两个对象是否相同

[BiteTheDust]

举一个比较简单的例子
你有若干对(k,v) key 的范围在[-2^32,2^32]
现在你要把它们存起来 快速通过 key 查询 value
你可以设计一个 hash 函数 比如 hash(x)=abs(x mod 1e5) 然后直接把它们存到一个 1e5 大小的数组 a 中 a[hash(k)]=v
然后再深入一点会涉及到 hash 函数的设计 和碰撞的处理 这些就是效率方面的问题了

[ysc3839]

我自己理解 hash function 是一个接受任意输入，输出固定长度数据的函数。

[2828kakafa]

我理解哈希表就是一个字典一样的东西，怎么快速查找，通过 key 来来找到 value，然后为了保证一个 key 对应一个 value，必须构造一个 hash 函数，但是 key 和 hash 函数算出来可能会出现有多个 value，然后又要解决 hash 冲突，又把 value 那个指向一个地址链表。前几天看了 redis 的设计与实现，貌似 redis 就是这么解决 hash 冲突的。而且我所了解到短链接的设计貌似也是通过 hash 的方式实现的。反正我理解每一种数据结构应该放到实际的例子中去理解。