chapter_hashing/hash_algorithm/

[giscus[bot]]

chapter_hashing/hash_algorithm/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_hashing/hash_algorithm/

[Desperado1001]

Mark

[Ak5mai]

看不明白，如果整数的哈希值就是本身的话，不就没有映射了吗？求解答 orz

[krahets]

是的，index = hash(key) % capacity 最后还要对 capacity 取余

[Hyrmm]

我的理解是,数值本身就具备单项性，是唯一的

[is-liu]

大佬们这个上一页和下一页能把不能挪到评论区上面，或者是映射个快捷键，总是去点目录感觉有些不舒服

[krahets]

好的收到，已移动至评论区上方～

[malone6]

• 上一页用 P 键 (previous page) 或者 , 键 (也是键盘符号<)
• 下一页用 N 键 (next page) 或者 . 键 (也是键盘符号>)

[zoujia]

我更习惯使用左、右方向键来切换上一页、下一页😅👍

[zzzpppy]

mac m2 快捷键貌似无效

[insomnia-city]

也就是说完备的哈希算法可以广泛运用于数据安全验证中，防篡改

[TechnologyK]

现在政府项目开始使用SM3了。

[52coder]

// hash example
#include <iostream>
#include <functional>
#include <string>

int main ()
{
  int num = 3;
  size_t hashNum = std::hash<int>()(num);
  bool bol = true;
  size_t hashBol = std::hash<bool>()(bol);
  double dec = 3.14159;
  size_t hashDec = std::hash<double>()(dec);
  std::string str = "Hello 算法";
  size_t hashStr = std::hash<std::string>()(str);

  std::cout << "hash(num):" << hashNum <<'\n';
  std::cout << "hash(bol):" << hashBol <<'\n';
  std::cout << "hash(dec):" << hashDec <<'\n';
  std::cout << "hash(str):" << hashStr <<'\n';

  return 0;
}
root@52coder:~/workspace/cpp# ./a.out
hash(num):3
hash(bol):1
hash(dec):17027819519382460022
hash(str):12677847606289151974

为什么我用c++代码跑出来的hash值和文章中的不一致？
g++ --version g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
编译命令:
g++ hash.cc && ./a.out

[krahets]

std::hash 在不同的平台和编译器中可能采用不同的哈希算法实现，因此无法保证哈希值相同

[zzqshishui]

hash(num):2613195814
hash(bol):67918732
hash(dec):2064320989
hash(str):1853464
请问为什么我的值是这样的？

[zengcheng123]

在C++中，整数和布尔值（true和false）在某些情况下可能会直接被用作哈希值，尤其是对于那些简单的数据类型，因为编译器或实现可能会选择直接使用它们的内存地址作为哈希。然而，这并不是一种通用的做法，也不是语言标准规定的行为。

通常，哈希函数的设计目的是生成一个数据的唯一标识，而不仅仅是原始值。对于整数和布尔值，更常见的做法是通过某种算法将这些值转换为一个范围内的整数，这个整数作为哈希值，这样可以确保即使两个相同的原始值也会得到不同的哈希结果，有助于在哈希表中快速查找。

如果是在自定义哈希函数或者使用标准库提供的哈希容器（如unordered_map或unordered_set）时，程序员通常会手动定义一个哈希函数来处理这些基本类型，而不是依赖于它们的内存地址。

[fancyop]

我使用g++跟楼主的结果一致（gcc version 8.3.0 (x86_64-posix-seh, Built by strawberryperl.com project)）

3
1
17027819519382460022
12677847606289151974

另外 Visual Studio 2022 (v143) 的结果为：

17086694953553481862
12638152016183539244
4418545003319772381
2313268924304215928

[daifee]

细心的你可能发现在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（Salt）值。

hash算法其中一个重要原则是“确定性”，与上面“随机盐”就矛盾了

[pycat13]

我对“随机盐”的加入也不是很理解，大佬能解释下吗？

[Claw-some]

这并不矛盾，所谓的确定性，只需要在这个哈希表的生命周期内就行。加盐就是加入随机数，不同的盐可以让同样的key通过hash算法后得到不同的值，当然，在new 一个 HashMap的时候这个盐必须是确定的。

[kubawell]

这里说的“输出的哈希值是不同的” 这句话有歧义，这里应该不能叫哈希值了，哈希在任何时间输出的值都是确定的，不然不可能做完整性校验，只是Python 解释器启动过程中利用到了Hash，再加了随机盐，并不是说Hash值每次随着Python 解释器启动都会变。

[tineline]

大佬可以推荐几个相应的练习题网站或者leecode题库吗

[krahets]

Hi～可以看看这里

[Curyain]

讲得很透彻，对于入门级来说，是一个不可多得学习资料，谢谢大佬

[Roy-rb2]

关于哈希函数，推荐一篇文章，可以配合着看
https://samwho.dev/hashing/

[HangSeven]

打不开啊哥哥

[Roy-rb2]

链接是正常的，可能需要翻个墙

[Purdre]

书中说加法哈希无法区分内容相同但顺序不同的字符串，是不是内容不同加法哈希也可能产生哈希冲突，比如“ad"和"cb"，"cam"和"nab"

[krahets]

Hi，对于所有哈希算法，不同的内容都可能产生哈希冲突。没有哈希算法可以做到 0% 的冲突概率

[Purdre]

好的，谢谢！

[louis100]

请问大佬，旋转哈希中的这个旋转(hash << 4) ^ (hash >> 28)，是什么原理呀？

/* 旋转哈希 */
function rotHash(key) {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash = ((hash << 4) ^ (hash >> 28) ^ c.charCodeAt(0)) % MODULUS;
    }
    return hash;
}

[lonelychinaday]

(hash << 4) ^ (hash >> 28) 是 MurmurHash3 算法的一部分。MurmurHash3 是一种快速的非加密哈希函数，它在性能和质量方面都表现良好。它被广泛用于数据库、文件系统和其他需要高性能哈希函数的应用程序。

MurmurHash3 算法使用 32 位整数作为输入，并生成 32 位整数作为输出。它使用一个 128 位初始化向量和一个 32 位随机数作为种子。

MurmurHash3 算法的工作原理如下：

1. 将输入整数转换为 128 位二进制字符串。
2. 将 128 位二进制字符串分成 16 个 8 位字节。
3. 对每个 8 位字节执行以下操作：
   1. 将字节左移 4 位。
   2. 将字节右移 28 位。
   3. 对这两个结果进行异或运算。
4. 将所有 16 个结果异或在一起，得到 32 位哈希值。

MurmurHash3 算法是快速、高效且安全的。它在性能和质量方面都表现良好，并且在许多应用程序中都得到了广泛使用。

[Hyrmm]

如果说数值的hash值是本身，那么意味着存在某个字符串和某个数值的key， 映射冲突吗？

[bnufw]

这一节的哈希算法是对上两节的value做key吧。也就是对要存的字符串赋予编号

[bnufw]

是做key还是做index呀？

[Gipsyfine]

我的理解是通过哈希算法计算数据（也就是key）对应的哈希值，然后对桶数量（数组长度）capacity 取模，从而得到index，也就是index = hash(key) % capacity

[bnufw]

数据结构的哈希值中，是不是将数据看成value,其哈希值看成是key?

[krahets]

Hi，这里没有 key-value 的概念。我们只是用哈希算法计算得到数据对应的哈希值（可以把数据看作 key ）

[zhuzilv]

所以JS/TS 的hash算法为什么没暴露出来？还要去v8里去看

[shinehhht]

hash & mod ,mod不应该是二进制数吗？感谢

[krahets]

Hi，应为 hash % mod ，这里的 mod 是一个数字，它可以表示为十进制、二进制等任何进制类型

[Fulin-Gao]

python里面 hash(-1)=-2，hash(-2)=-2，这是咋回事啊

[krahets]

Hi，在 Python 中，哈希值 -1 为保留值（因为在 Python 的内部实现中，-1 通常被用作错误标记或特殊情况的标志），Python 的设计者决定让 hash(-1) = -2

[f820602h]

在許多程式語言中，只有不可變對象才可作為雜湊表的 key
請問可以舉個例子嗎？就我所知 js 或 python 若是以對象或陣列作為 key 時，都會以其「引用」作為 key 而非其本身，應該就沒有該變其值就無法查詢的問題。

[krahets]

这个具体要看对象的 hash value 是如何实现的，举个例子：

• Python 中的元组 tuple 不可变，可以用作字典的 key ；
• Python 中的列表 list 可变，因此不可用作字典的 key ，因为当列表元素变化时，它的 hash value 也会改变。

[kang-int]

数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整。
如果发送方发送的哈希值在传输过程中发生了改变，而数据是完整的，接收方再用这个错的哈希值去比较，不是会误报吗

[krahets]

如果发送方发送的哈希值在传输过程中发生了改变

这个几率极低，因为哈希值很短（还不如有些网址长），和文件内容大小完全不是一个量级

[1435646097]

也不是完全没有道理，所以软件都是除了给软件的下载链接外，边上还会对应一个hash码（不用下载，直接看就可以了），方便你下载玩后去校验软件的完整性

[1i9htning]

作者您好，在C++中，std::vector的底层实现为迭代器。也就是说动态数组中的元素并不是其成员。那么一个std::vector对象是否为可哈希的呢？因为其成员的内存地址不变，只是其存放元素的地址在变化（即成员迭代器的值变化了）

[Xinkun666]

作者你好
/* 异或哈希 */
int xorHash(string key) {
int hash = 0;
const int MODULUS = 1000000007;
for (unsigned char c : key) {
hash ^= (int)c;
}
return hash & MODULUS;
}
这段代码里，最后将总的哈希与大质数进行“与”运算，请问这里本来是取模操作，还是就是进行“与”运算，如果进行与运算那么这个质数有很多位是0，进行取与后也势必使最终的哈希值对应位置为0，那么这样就不符合哈希函数要尽量满足均匀分布这一条件了，所以我猜测这里大概率是进行取模操作。

[wangx77]

同问这个问题，这个“与”操作的含义是什么？

[selfboot]

感觉缺少一致性 hash 的介绍。包括 hashring 环法，或者 jumphash 这些。这些在负载均衡领域很通用。
我这里做了个一致性 hash，hash 环的可视化演示，支持影子节点的演示，可以配合理解。

[izip-aTLa2]

打卡

[huih99]

哈希表章节看完了，但还是没有明白这个哈希表到底起什么用，容量如何设计的。如果哈希表是一个数组存储，那么这个章节中讲的hash算法计算key，这个key怎么确保是数组长度内的索引呢？如果哈希表不是数组存储，那么上一章节讲到的线性探测、平方探测等如何能实现呢

[huih99]

实在是无法理解哈希表的作用

[huih99]

什么情况下，需要将大的输入空间映射到小的输出空间呢？为什么哈希表采用数组结构，而不是直降将key作为字符串索引存储到对象中呢

[gfzum]

输入空间总是会大于输出空间，用户可以输入的数字、字符串是无限的。使用哈希表映射后的好处是可以在 O(1) 内实现查找、添加、删除，而这是基于数组 index 的方式实现的，连续内存空间的地址访问不需要像字符串那样遍历比较查找。