背景

在做国际化翻译工具时，为了保证生成key值唯一性和长度不要太长，我们需要采用一种哈希算法，但考虑到计算key值需要在运行时进行，担心影响性能，所以准备调研一下性能效果。
先说下结论：最后我们采用了blueimp-md5的包，性能和重复率都能满足需求。

在开始前，我们需要明确几个问题：

  1. 有哪些算法可以选
  2. 算法原理是啥，理论上存在哪些性能问题
  3. 如何测试，采用什么样的数据测试

  4. 测试结果如何衡量，达到多少指标算合格

    哈希算法调研

    调研了一下，市面上常见的算法可以分为3类：

  5. CRC（Cyclic Redundancy Check，循环冗余校验），包括：CRC8、CRC16、CRC32

  6. MD5（Message-Digest Algorithm 5，消息摘要算法版本5），包括：MD2 、MD4、MD5
  7. SHA（Secure Hash Algorithm，NIST机构制定的密码算法），包括：SHA1、SHA256、SHA384、SHA512

还有一些不常见的优化算法，比如：RIPEMD、PANAMA、TIGER、ADLER32等，这些比较小众暂时不考虑。

选择算法：
虽然算法很多，但适用场景都有所差异，回到我们的需求：

  1. 要求一定的唯一性，避免冲突
  2. 要求高性能
  3. 长度不能太长（最初目的）
  4. 在JS中使用，市面上有较成熟稳定的工具

按上述要求筛选下来，从几类算法中选择比较有代表性的，就只有 CRC32、MD5 2种算法可选了，SHA-256太长，其他的则比较小众难以维护。

CRC算法分析：

循环冗余校验算法，主要用于校验数据的完整性，速度极快，像winrar/winzip等压缩工具以及一些通讯领域有用到，但缺点是冲突概率相对高一些。
成熟的算法网上有不少人测试，我们找一些相对官方的文章看来参考即可：
摘自：http://www.backplane.com/matt/crc64.html

Summary, 18.2 million sample test dataset, number of collisions. output.16 Count 18134464/18200000 output.17 Count 18068928/18200000 output.18 Count 17937856/18200000 output.19 Count 17675712/18200000 output.20 Count 17151424/18200000 output.21 Count 16103198/18200000 output.22 Count 14061250/18200000 output.23 Count 10770169/18200000 output.24 Count 7092360/18200000 output.25 Count 4153742/18200000 output.26 Count 2259269/18200000 output.27 Count 1179721/18200000 output.28 Count 603421/18200000 output.29 Count 305089/18200000 output.30 Count 153722/18200000 output.31 Count 77254/18200000 output.32 Count 38638/18200000 output.33 Count 19232/18200000

可以看到CRC 32中182万条有38638个冲突，也就是冲突率大概为0.21%
而整个系统的翻译数据有上千条很正常，这概率还是有些高了，所以不打算考虑CRC。

众所周知的CRC32冲突的2个字符串“plumless”和“buckeroo”，会生成相同的值：

扩展研究：

如果用有序的整形数字测试重复率（从1开是累加）测试CRC 32冲突，直到累加2000w依然没有出现重复的结果，这是因为CRC算法本质上是除模取余，除数越大偏移越大，而除数也会导致连续数值之间不太容易重复。
正式因为这个算法特性，CRC的重复率会随着数据范围增大，比较官方的测试数据：
摘自：https://preshing.com/20110504/hash-collision-probabilities/

表中当哈希数为 77163 时，有 50% 的机会发生冲突。
那么在我们常用的英文语句作为数据集时，冲突概率有多少呢？这个值得研究一下，但我们这里先看看MD5是否更合适。

MD5算法分析：

Message-Digest Algorithm系列的最具有代表性的就是MD5了，虽然MD4目前也还在用，但我们这里选择一种进行分析就足够了。
一张图说明原理：

总结MD5加密流程就是将信息分块后，逐个填充到512位分组数据，每次填充都会加上一轮的128位再进行填充，最终完成所有分块数据计算得出一个128位的数据。
我们假设它的计算结果是足够随机和足够分散的。则一个MD5码有2的128次方（即2e128）个可能，理论上随意找出来的2个MD5码相等的可能性是2e128分之一，这已经是非常小的一个概率，由此可见MD5在防止冲突方面是非常安全的，不然也不会直到2004年才被证明存在冲突。
目前已知的MD5冲突有：

#强网杯某大牛wp $Param1=”\x4d\xc9\x68\xff\x0e\xe3\x5c\x20\x95\x72\xd4\x77\x7b\x72\x15\x87\xd3\x6f\xa7\xb2\x1b\xdc\x56\xb7\x4a\x3d\xc0\x78\x3e\x7b\x95\x18\xaf\xbf\xa2\x00\xa8\x28\x4b\xf3\x6e\x8e\x4b\x55\xb3\x5f\x42\x75\x93\xd8\x49\x67\x6d\xa0\xd1\x55\x5d\x83\x60\xfb\x5f\x07\xfe\xa2”; $Param2=”\x4d\xc9\x68\xff\x0e\xe3\x5c\x20\x95\x72\xd4\x77\x7b\x72\x15\x87\xd3\x6f\xa7\xb2\x1b\xdc\x56\xb7\x4a\x3d\xc0\x78\x3e\x7b\x95\x18\xaf\xbf\xa2\x02\xa8\x28\x4b\xf3\x6e\x8e\x4b\x55\xb3\x5f\x42\x75\x93\xd8\x49\x67\x6d\xa0\xd1\xd5\x5d\x83\x60\xfb\x5f\x07\xfe\xa2”; #008ee33a9d58b51cfeb425b0959121c9 #知乎Belleve $data1=”\xd1\x31\xdd\x02\xc5\xe6\xee\xc4\x69\x3d\x9a\x06\x98\xaf\xf9\x5c\x2f\xca\xb5\x07\x12\x46\x7e\xab\x40\x04\x58\x3e\xb8\xfb\x7f\x89\x55\xad\x34\x06\x09\xf4\xb3\x02\x83\xe4\x88\x83\x25\xf1\x41\x5a\x08\x51\x25\xe8\xf7\xcd\xc9\x9f\xd9\x1d\xbd\x72\x80\x37\x3c\x5b\xd8\x82\x3e\x31\x56\x34\x8f\x5b\xae\x6d\xac\xd4\x36\xc9\x19\xc6\xdd\x53\xe2\x34\x87\xda\x03\xfd\x02\x39\x63\x06\xd2\x48\xcd\xa0\xe9\x9f\x33\x42\x0f\x57\x7e\xe8\xce\x54\xb6\x70\x80\x28\x0d\x1e\xc6\x98\x21\xbc\xb6\xa8\x83\x93\x96\xf9\x65\xab\x6f\xf7\x2a\x70”; $data2=”\xd1\x31\xdd\x02\xc5\xe6\xee\xc4\x69\x3d\x9a\x06\x98\xaf\xf9\x5c\x2f\xca\xb5\x87\x12\x46\x7e\xab\x40\x04\x58\x3e\xb8\xfb\x7f\x89\x55\xad\x34\x06\x09\xf4\xb3\x02\x83\xe4\x88\x83\x25\x71\x41\x5a\x08\x51\x25\xe8\xf7\xcd\xc9\x9f\xd9\x1d\xbd\xf2\x80\x37\x3c\x5b\xd8\x82\x3e\x31\x56\x34\x8f\x5b\xae\x6d\xac\xd4\x36\xc9\x19\xc6\xdd\x53\xe2\xb4\x87\xda\x03\xfd\x02\x39\x63\x06\xd2\x48\xcd\xa0\xe9\x9f\x33\x42\x0f\x57\x7e\xe8\xce\x54\xb6\x70\x80\xa8\x0d\x1e\xc6\x98\x21\xbc\xb6\xa8\x83\x93\x96\xf9\x65\x2b\x6f\xf7\x2a\x70”; #79054025255fb1a26e4bc422aef54eb4

冲突概率基本够用，我们需要再考虑一下性能问题，调研到一个比较可靠的性能测试对比：

这是不同算法在A、B2台机器上使用.Net测试的结果，结果比较有参考价值。由此可以看出，MD5性能处于一流的水平。既然性能和重复率都能够满足要求，那我们就以MD5为基础进行下一步调研：在JS中使用是否合适。

最后在长度需求上，我们可以选择截取MD5结果的中间16位，保证唯一性的同时缩短key值长度。

工具包调研：

经过筛选找到一个比较好评的NPM包：blueimp-md5
包地址：https://github.com/blueimp/JavaScript-MD5
看了一下源代码，书写质量还是可圈可点的，start和issue状况也良好，但实际在浏览器端使用情况如何，我们还需要实测一下。

测试报告

结论：

该库采用最简单的RSA 128位的算法，且代码质量较好，性能优秀！

测试对象：

采用md5 取中间16位，代码如下：

import md5 from ‘blueimp-md5’; // 生成key export function generateKey({ label, project, namespace }: TransifyKeyParams): string { if (!project || !label) return ‘’; const computedKey = [project, namespace, label] .filter((key) => !!key) .join(‘‘) .replace(/\s/g, ‘‘); return md5(computedKey).slice(8, 24); }

测试设计：

数据源：使用srm产品现有的翻译录入作为基础数据
衡量单位：千条(k)/ms

指标及结果：
实际场景速率：18.7 k/ms
加权平均字数速率：6k/ms（23字/条）
最大字数速率：13k/ms（260字/条）

结果记录：

测试源码：

https://git.garena.com/liang.xie/performance-testing-md5

总结：

我一直都相信只有最合适的才是最好的，无论是技术选型还是生活工作中的决策，在当下条件下符合需求很重要。
哈希算法虽然有很多并且发展越来越成熟，但在日常工作中，我们常用的其实不多：

  • CRC32 适合用来做数据校验，据说错误率仅为0.0047%
  • MD5 适合用于加密和校验等大多数场景
  • SHA-256 结果较长，适合用于一些安全性要求很高的场景，比如安全密钥等

希望这篇文章能给你带来帮助。

相关资料

一文读懂 MD5 算法
JS-MD5设计
哈希算法测试对比