leikooo头像
你每天用几十次的 hash,到底是什么?从 HashMap 到网盘秒传一次讲透封面图

你每天用几十次的 hash,到底是什么?从 HashMap 到网盘秒传一次讲透

大家今天大概已经用过几十次 hash 了,只是没注意到:

  • git log 里那串 e3d1fbf…,是 hash;
  • Java 里随手 new HashMap<>(),名字里就带着 hash;
  • 登录网站时,服务器存的不是密码本身,而是密码的 hash;
  • 下载一个 Linux ISO,旁边写着 SHA256: …,那也是 hash;
  • 网盘几个 G 的文件「秒传」成功、搜索引擎「以图搜图」,背后还是 hash。

hash 用得这么多,可真要问起来,大家可能也说不太清:它到底是什么(what)?HashMap 里怎么用它的(how)?hashCode() 为什么要写成 37 * result + c 这种奇怪的样子(why)?有没有一个「最好」的 hash 算法?这篇文章就顺着「是什么、怎么做、为什么」这三个问题,把这几件事一次讲清楚。

hash 是什么,为什么需要它

先说是什么。一句话:hash 函数把任意大小的数据,压成一个固定长度的「指纹」。

5 个字节的 "hello" 进去,出来 256 bit;4 GB 的电影进去,出来也是 256 bit。这个输出就叫 hash 值(也叫摘要、散列值、指纹)。举个真实的例子,"hello" 的 SHA-256 是:

2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

64 个十六进制字符,正好 256 bit。不管大家喂进去的是 5 个字节还是 4 GB,出来的都是这么长一串。

hash:把任意大小的数据压成固定长度的指纹

一个能用的 hash 函数,至少要满足这几点:

  • 确定性:同样的输入,什么时候算、在哪台机器上算,结果都一样。大家在自己电脑上算出的 "hello" 的 SHA-256,一定和上面这串一模一样,否则就没法拿来比对了。
  • 算得快:hash 的价值在于「用一个小东西代替大东西」,如果算 hash 比直接比较原数据还慢,那就没意义了。
  • 分布均匀:不同的输入应该尽量均匀地散落在输出空间里,而不是扎堆。

还有一个绕不开的事实:碰撞一定存在。输出只有 256 bit,输入却是无限的,按抽屉原理,必然有两个不同的输入得到同样的输出。好的 hash 不是没有碰撞,而是让碰撞极难发生,或者极难被人故意造出来。

再说为什么需要它。先别急着看 hash 的用途,换个角度想:我们真正想要的东西是什么?

是给数据一个编号。一个 4 GB 的文件、一个 20 个字符的字符串 key、一次 git 提交,这些东西都太「大」、太「不规则」,没法直接拿来当下标、当名字、当凭证。我们想要的是一个小小的、固定长度的数字,能代表它。问题是:这个编号从哪来?大家可以把能想到的办法都过一遍,看看每个卡在哪。

  1. 办法一:不编号,每次直接比原数据。 100 万个字符串 key 里找一个,平均要比 50 万次,每次比较都要从头读那个 key。两个 4 GB 的文件判等,要读满 8 GB。能用,但慢得离谱,而且数据越大越慢。
  2. 办法二:排好序,用树或二分查找。 TreeMap 就是这么干的,100 万个 key 只要比大约 20 次。好多了,但每一次比较仍然要读整个 key,而且 20 次毕竟不是 1 次。
  3. 办法三:直接拿 key 当数组下标。 这是最快的,一步到位,arr[key]。但 key 是字符串的时候数组根本开不下:光是 10 个小写字母组成的字符串就有 26 的 10 次方、也就是 1.4 × 10^14 种,一个 int 下标才 42 亿。
  4. 办法四:找一个中心统一发自增 id。 数据库主键就是这样。可这有个先后顺序的死结:要知道一条数据的 id,得先找到这条数据,而找到它正是我们想解决的问题。而且两台从没通信过的机器,对同一份内容不可能发出同一个 id,网盘秒传、Git 这种场景就没法做了。
  5. 办法五:随机抽一个数当编号。 分布倒是均匀了,不会扎堆。但随机数和内容没关系,第二次见到同一份内容,大家没法再「抽」出同一个数,只能靠一张表记住「内容 → 编号」,又绕回办法一了。
  6. 办法六:取内容的前 32 个字节当编号。 能从内容重算,长度也固定,看起来很完美。可现实里的数据是扎堆的:所有 JPEG 文件开头都是 FF D8 FF,所有 PNG 开头都是 89 50 4E 47,业务里的 key 一大半是 user_1、user_2、order_2026…,前几个字节几乎全一样。拿它们当编号,全部撞在一起。

六个办法摆在一起,我们想要的东西就清楚了,一个编号需要同时满足:

  • 固定长度、很小,好当下标、好存、好比;
  • 从内容本身算出来,谁都能独立重算,不需要中心,不需要通信,不需要「先找到」;
  • 分布均匀,像随机数一样不扎堆,哪怕输入扎堆也要把它们打散。

hash 就是同时满足这三条的那个东西。它的精髓可以压成四个字:确定性的随机。它的输出看起来像随机数,"hello" 变成 2cf24dba…,看不出任何规律,相邻的输入也会散到老远;但它又是完全确定的,任何人在任何机器上算 "hello",都得到同一串。一个「谁都能重算出来的随机数」,这就是 hash 和其它所有办法的本质区别。

想通这一点,hash 的三大用途就都是推论了:

  1. 快速查找。 编号固定长度又均匀,就能直接当数组下标,这正是办法三想做而做不到的事。HashMap 把 key 算成一个 int,& (n - 1) 后直接定位到桶,比 1 次而不是 20 次或 50 万次。下一节细讲。
  2. 快速判等、去重。 编号能从内容独立重算,两台机器就可以各算各的再比编号。网盘秒传就是这样:大家上传一个几 G 的电影,客户端先在本地算出文件的 hash 发给服务器,服务器一查「这个 hash 我库里已经有了」,直接给大家的账号挂一个链接,几秒钟「传」完,其实一个字节都没传。两边从没交换过文件本身,却对「这是不是同一个文件」达成了一致,办法四和办法五做不到这一点。
  3. 防篡改。 编号由内容决定,内容变了编号就变,而且算一遍只要几毫秒。下载的 ISO 自己算一遍 SHA-256 和官网对一下就知道有没被动过。Git 也一样:每个 commit 的 id 就是它内容(包括父 commit 的 id)的 hash。大家如果用 git rebase 改过历史,会发现从改动的那个 commit 开始,后面所有 commit 的 id 全变了,就是因为每一个 id 都「包含」了它前面所有内容的指纹。

还有一个藏在三条用途背后的共同点:hash 把「读一遍完整内容」这件贵的事只做一次,之后每次查找、比较、校验,都只碰那个小小的编号。一次付费,终身复用,这是它快的根本原因。

HashMap 是怎么用 hash 的

这一节讲怎么做。HashMap 的底层是一个数组,每个格子叫一个「桶」。put(key, value) 的时候:

  1. 调用 key.hashCode() 得到一个 int;
  2. 做一次「扰动」:h ^ (h >>> 16);
  3. 用 hash & (n - 1) 算出桶下标(n 是数组长度,总是 2 的幂);
  4. 把键值对放进那个桶。

HashMap 用 hash 定位桶,apple 和 cherry 发生碰撞

查找时也一样:算一次 hash,直接跳到对应的桶,所以平均是 O(1)。

图里的数字都是真实算出来的:"apple".hashCode() 是 93029210,"cherry".hashCode() 是 -1361513063,两个数完全不同,但在容量 16 的数组里,经过扰动和 & 15 之后都落进了 1 号桶,这就是碰撞。HashMap 的处理方式是把它们挂成一个链表,查找时在桶里再逐个 equals()。Java 8 之后,一个桶里的链表超过 8 个节点(且数组长度不小于 64)就会转成红黑树,防止退化得太厉害。

上面四步里有两步看起来很别扭,这就该问为什么了。

为什么用 & (n - 1) 而不是 % n? 大家可以拿 37 这个数试一下,容量 n = 16:

37 % 16 = 5

   37 = 0b100101
   15 = 0b001111
37 & 15 = 0b000101 = 5

结果一样。原因是 16 - 1 = 15 的二进制是 1111,& 15 的效果就是「只保留最低 4 位」,而一个数的最低 4 位,恰好就是它除以 16 的余数。所以只要 n 是 2 的幂,& (n - 1) 和 % n 完全等价。

那为什么不直接写 % n?两个原因。一是快:CPU 做一次整数除法要几十个时钟周期,做一次按位与只要 1 个,HashMap 每次 put、get 都要算一次下标,省下的时间是实打实的。二是负数:Java 里 "HashMap".hashCode() 是 -1932803762,用 % 16 算出来是 -2,拿去当数组下标直接越界;用 & 15 算出来是 14,天然就是非负数,不用再额外处理。

这也解释了 HashMap 容量为什么总是 2 的幂:大家 new HashMap<>(10),它内部实际开的是 16,因为只有 2 的幂,& (n - 1) 这个替代才成立。要是容量真的是 10,37 & 9 算出来是 1,而 37 % 10 是 7,结果就错了。

为什么要 h ^ (h >>> 16)? 因为 & (n - 1) 只看得到 hashCode 的低几位。容量 16 时只用最低 4 位,高 28 位白算了。如果一批 key 的 hashCode 恰好只在高位不同,它们就会全部挤进同一个桶。

这不是杞人忧天,JDK 源码的注释里就举了一个真实的例子:用 Float 做 key。Float.hashCode() 返回的是浮点数在内存里的二进制表示,而 1.0f、2.0f、3.0f 这些整数值的浮点数,低 16 位全是 0:

1.0f  →  0x3f800000
2.0f  →  0x40000000
3.0f  →  0x40400000
4.0f  →  0x40800000

不扰动的话,& 15 一算全是 0,整个 Map 退化成一条挂在 0 号桶上的链表。

再看一组更直观的数字,8 个 Integer key:65536、131072、196608……也就是 65536 的 1 到 8 倍。它们的二进制是 1 0000 0000 0000 0000、10 0000 0000 0000 0000……低 16 位全是 0,差别只在高位:

key不扰动,& 15扰动后,& 15
65536 × 101
65536 × 202
65536 × 303
…0…
65536 × 808

不扰动,8 个 key 全在 0 号桶;把高 16 位异或到低 16 位上,8 个 key 整整齐齐分进了 8 个桶。这就是 h ^ (h >>> 16) 干的事:让高位也「参与投票」,一次位运算换来更均匀的分布,很划算。

一个好的 hashCode 该怎么写

HashMap 再聪明,也得靠大家的 hashCode() 给出一个「像样」的数字。如果写了个这样的类:

@Override
public int hashCode() {
    return 42;
}

它完全合法:相等的对象 hashCode 也相等,契约没违反。但所有对象都会挤进同一个桶,HashMap 退化成一个链表(或者一棵树),O(1) 变成 O(n)(或 O(log n))。

那什么样才算好?Stack Overflow 上有个高赞回答说得很实在:

The best implementation? That is a hard question because it depends on the usage pattern.

然后它推荐了 Josh Bloch 在《Effective Java》里给出的一个「绝大多数情况下都够好」的方法。先看怎么做:

  1. 创建一个 int result,赋一个非零的初始值(比如 17);
  2. 对 equals() 里参与比较的每个字段 f,算出一个 int c:
    • boolean:f ? 1 : 0
    • byte、char、short、int:(int) f
    • long:(int) (f ^ (f >>> 32))
    • float:Float.floatToIntBits(f)
    • double:Double.doubleToLongBits(f),再按 long 处理
    • 对象引用:调用它的 hashCode(),null 就取 0
    • 数组:把每个元素当成单独的字段,逐个算、逐个合并
  3. 合并:result = 37 * result + c
  4. 返回 result

Effective Java 的 hashCode 配方,一步步算出 Point(3, 4, "cat") 的 hash

这个配方看着像一堆规矩,其实每一条都有道理。下面逐条讲为什么,每一条都配一个能自己跑出来的例子。

为什么初始值要非零? 假设 result 从 0 开始,第一个字段的 c 也是 0,那么 37 * 0 + 0 还是 0。开头那些值为 0 的字段对结果毫无贡献,等于被吞掉了。Java 自己就有一个现成的反面例子:String.hashCode() 的初始值是 0,于是:

"".hashCode()         // 0
"\u0000".hashCode()   // 0
"\u0000\u0000".hashCode()  // 0

空串和一个、两个、任意多个 \0 组成的字符串,hashCode 全是 0。再对比 Arrays.hashCode(),它的初始值是 1,[0, 0, 7]、[0, 7]、[7] 三个数组算出来分别是 29798、968、38,三个都不同;如果初始值换成 0,三个全都是 7。用一个非零初始值,每个字段都至少会被「乘一下」,位置信息就保住了。

为什么 long 要 f ^ (f >>> 32)? long 有 64 位,hashCode 只能返回 32 位。如果直接 (int) f,就只留下了低 32 位,高 32 位的信息全丢。大家在业务里经常会拼这种复合 key:(userId << 32) | itemId,用户 id 放高 32 位,商品 id 放低 32 位。那么用户 1、2、3 对同一件商品 5 的三条记录:

key(int) f(int) (f ^ (f >>> 32))
(1 << 32) | 554
(2 << 32) | 557
(3 << 32) | 556

直接截断,三个 key 的 hash 全是 5,有多少个用户就撞多少次;先把高 32 位异或到低 32 位再截断,三个就分开了。这跟上一节 HashMap 的扰动是同一个思路:别浪费高位。

为什么 float / double 要转成 bits? 直接 (int) f 会把小数部分抹掉:0.1f 到 0.9f 这九个数全变成 0,1.1f 和 1.9f 都变成 1。要是大家拿商品价格当 key,9.99、9.5、9.01 全撞在一起。floatToIntBits 拿的是浮点数在内存里的完整二进制表示,0.1f 是 0x3c23d70a,0.2f 是 0x3ca3d70a,每一位都用上了,自然不撞。

还有一个更隐蔽的原因:要和 equals() 保持一致。Float.equals() 本身就是用 floatToIntBits 来比较的,所以 0.0f 和 -0.0f 不相等、NaN 等于 NaN。hashCode 用同一套规则,才不会出现「equals 相等但 hashCode 不同」的情况。

为什么是「乘 37 再加」,而不是直接加起来? 如果只是把每个字段的 c 加起来,Point(3, 4) 和 Point(4, 3) 的 hash 会一模一样,因为加法不关心顺序。而 37 * result + c 相当于把之前的结果「往左挪一挪」再加新字段,字段的位置也成了 hash 的一部分。上图里,Point(3, 4, "cat") 得到 963618,换个顺序 Point(4, 3, "cat") 得到 964950,不一样了。

那为什么偏偏是 37? 关键在于它是奇数。乘以偶数等于左移,int 只有 32 位,左移出去的位就直接丢了。假设大家把 String.hashCode() 的乘数从 31 改成 32,32 是 2 的 5 次方,每多一个字符就左移 5 位,7 个字符之后前面的内容就全部移出了 32 位。后果是任何字符串的 hash 只由最后 7 个字符决定:

"user_1234567"   →  -1488266505
"admin_1234567"  →  -1488266505
"order_1234567"  →  -1488266505

前缀不管是什么,全撞。换回奇数 31,这三个的 hashCode 分别是 -751149632、-1295273660、1838073411,各不相同。至于选素数,更多是个传统,没有严格的数学证明说它一定更好。

JDK 自己用的是 31(String.hashCode()、Arrays.hashCode()、Objects.hash() 都是),也是奇数,而且 31 * i 可以被 JIT 优化成 (i << 5) - i,一次移位加一次减法,比乘法还快。

顺便一提,String 用 31 也会碰撞,而且很容易造出来:"Aa".hashCode() 和 "BB".hashCode() 都是 2112。更麻烦的是这种碰撞可以「拼接」:"AaAa"、"AaBB"、"BBAa"、"BBBB" 四个的 hashCode 全是 2031744,拼 10 段就能造出 2 的 10 次方、也就是 1024 个 hashCode 完全相同的字符串。这在正常业务里没什么问题(equals() 会兜底),但如果攻击者用这个办法生成几万个 key,一股脑作为 HTTP 参数名发给大家的服务,服务端一解析,HashMap 就退化成一条长链表,CPU 被打满,这就是 HashDoS 攻击,2011 年很多 Web 框架都中过招。

最后是底线。 不管怎么写,都要守住这条底线:

  • a.equals(b) 为 true,那么 a.hashCode() == b.hashCode() 必须成立;
  • 反过来不要求:hashCode 相同,对象不一定相等(这就是碰撞)。

大家应该都踩过或者见别人踩过这个坑:只重写了 equals(),忘了 hashCode(),两个「相等」的对象落进不同的桶,map.get() 死活找不到,set.contains() 永远返回 false。

现在其实很少需要手写了:Objects.hash(x, y, name) 一行搞定,Java 16 的 record 会自动生成 equals/hashCode,IDE 和 Lombok 也能代劳。但知道它们为什么这么写,大家才能在出问题时看懂发生了什么。

hash 不止一种,图片也有 hash

hashCode() 只是 hash 家族里最朴素的一员。按用途分,常见的大概有这几类:

类别代表算法追求什么
哈希表用MurmurHash3、xxHash、wyhash极快、分布均匀
抗 HashDoSSipHash带密钥,攻击者造不出碰撞
校验和CRC32发现传输、存储中的意外损坏
密码学 hashSHA-256、SHA-3、BLAKE3无法反推、无法人为造碰撞
密码存储bcrypt、scrypt、Argon2故意慢,加盐,拖垮暴力破解
感知 hashaHash、dHash、pHash、SimHash内容相似,hash 也相似

其中密码学 hash 有个很重要的性质,叫雪崩效应:输入哪怕只改 1 个 bit,输出也会有大约一半的 bit 翻转。

雪崩效应:hello 和 hellp 的 SHA-256 几乎完全不同

"hello" 和 "hellp" 只差最后一个字母(o 和 p 的 ASCII 码只差 1,二进制只差 1 个 bit),SHA-256 的 64 个十六进制字符里有 63 个不同,256 个 bit 里翻转了 131 个,非常接近理想的 50%。正因为输出和输入之间看不出任何关联,大家才没法从 hash「猜」回原文,也没法微调输入去凑出一个指定的 hash。

这也是为什么 MD5 和 SHA-1 已经不能用于安全场景:MD5 的碰撞在 2004 年就被构造出来了,SHA-1 在 2017 年被 Google 的 SHAttered 攻击攻破,有人做出了两份内容不同、SHA-1 完全相同的 PDF。拿它们做文件去重还行,做签名、防篡改就不行了。Git 现在也在往 SHA-256 迁移。

存密码又是另一回事。SHA-256 太快了,一张消费级显卡每秒能算几十亿次 SHA-256,攻击者拿到数据库后,几小时就能试遍所有常见密码。所以密码要用 bcrypt、Argon2 这种专门设计得很慢、很吃内存的算法,让每次尝试从纳秒级变成几百毫秒,再给每个用户加一段随机的盐,让同一个密码在不同用户那里 hash 也不同,彩虹表和批量破解就都失效了。

反过来还有一类 hash,追求的恰恰是「改一点,几乎不变」。想象一下:大家在网上看到一张图,怀疑是盗的自己的图,对方把图调亮了一点,右上角还加了个水印。用 SHA-256 比对?没戏,雪崩效应保证了改一个像素 hash 就面目全非。这种场景需要的是图片长得像,hash 也要像,这就是感知哈希(perceptual hash)。

最简单的一种叫平均哈希(aHash),只要四步:

  1. 缩小:把图缩成 8×8,一共 64 个像素。细节、尺寸、长宽比全扔掉,只留大致的明暗结构;
  2. 转灰度:去掉颜色,每个像素只剩一个亮度值;
  3. 比平均值:算出 64 个像素的平均亮度,比平均值亮的记 1,暗的记 0;
  4. 拼起来:64 个 0/1 拼成一个 64 bit 的数,就是这张图的指纹。

平均哈希 aHash 的四个步骤,以及两张相似图片的汉明距离

比较两张图时,不看 hash 是否相等,而是数一数两个 64 bit 里有几位不同,这叫汉明距离。上图里调亮加水印后,64 位里只有 3 位变了。一般来说,距离在 5 以内基本是同一张图,超过 10 就是不同的图了。

为什么这么简单的办法有效?因为调亮、压缩、缩放、加个小水印,改变的都是细节和整体亮度,而「哪块比平均亮、哪块比平均暗」这种结构基本不变。aHash 正好只保留了结构。它也有更讲究的兄弟:dHash 不跟平均值比,而是跟相邻像素比,对整体调亮调暗更不敏感;pHash 先做一次 DCT(离散余弦变换,JPEG 压缩也用它),只保留低频部分再比较,对压缩、轻微裁剪更稳。

同样的思路还能用在文本上:SimHash 能给一篇文章算出一个指纹,内容相近的文章指纹的汉明距离也小,搜索引擎就是用它来给海量网页去重的。更一般化的叫局部敏感哈希(LSH),现在的向量数据库做近似最近邻搜索,很多也是这个思想。

那么,最优的 hash 算法是哪个

回到那个 Stack Overflow 回答的第一句话:

That is a hard question because it depends on the usage pattern.

这句话不是在打太极。看完上面这些大家会发现,不同场景对 hash 的要求互相矛盾:

  • HashMap 要快,密码存储偏偏要慢;
  • 密码学 hash 要「改一点就全变」,感知 hash 偏偏要「改一点几乎不变」;
  • 内存哈希表不需要安全,可一旦 key 来自外部用户,就得防着有人故意造碰撞。

所以不存在一个「最优」的 hash,只有最适合当前用途的 hash:

按用途选择 hash 算法的决策图

  • 内存里的哈希表、分库分表:xxHash、wyhash、MurmurHash3。要的是快和均匀,碰撞了有 equals() 兜底。
  • key 来自外部、可能被人构造:SipHash,带一个启动时随机生成的密钥,攻击者不知道密钥就造不出碰撞。Python 的 str hash 和 Rust 的 HashMap 默认用的都是它,就是为了防前面说的 HashDoS。
  • 文件校验、去重、秒传:只防意外损坏用 CRC32 或 xxHash3 就够了;要防有人恶意伪造,就上 BLAKE3 或 SHA-256。
  • 签名、防篡改、区块链、Git:SHA-256、SHA-3、BLAKE3,别再用 MD5 和 SHA-1。
  • 存用户密码:Argon2id 首选,bcrypt、scrypt 也可以,记得加盐。
  • 找相似的图片、文本:pHash、dHash、SimHash。

至于 Java 里的 hashCode(),用 Objects.hash() 或者 record 就是那个「几乎所有场景都够好」的答案,而它的原理,就是上面那份 37 * result + c 的配方。

最后回到开头的三个问题。hash 是什么:用一个小而固定的指纹,代表一个大而任意的东西。为什么是它而不是别的办法:因为它是「确定性的随机」,一个谁都能从内容独立重算出来、又像随机数一样不扎堆的编号,遍历、排序、中心发号、随机数、取前几个字节,每一个都缺其中一条。它怎么做:算一个数,用这个数定位、比对、校验,贵的事只做一次。至于为什么有这么多种:因为不同场景要的东西互相矛盾,要快、要慢、要均匀、要抗碰撞、要相似的东西指纹也相似,于是每一种需求背后都长出了一类算法。

下次再看到 git log 里那串 commit id、HashMap 里的 hashCode()、网盘的秒传,大家大概就知道它们背后在发生什么了

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/baihuaeryue/article/details/170858575

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--