Hash 函数常见使用场景

Hash 算法在软件开发中的应用极为普遍,这里稍作总结,列举一些 Hash 函数的使用场景。

文件完整性校验

Hash 算法本身可以被用来校验文件的完整性,比如 Linux 发行版内置的 md5sum, sha1sum, sha256sum 等命令,用 Node 的 crypto 模块可以很方便的封装一个 JS 版:

const { readFile } = require('fs/promises');
const { createHash } = require('crypto');

async function checkhash(filename) {
  const hash = createHash('md4');
  const buffer = await readFile(filename);
  hash.update(buffer);
  const checksum = hash.digest('hex');
  console.log(`${checksum} ${filename}`);
}

checkhash(process.argv[2]);
$ node checkhash.js checkhash.js
e98662d5d0a8fa2c5561b8a834f41ae7 checkhash.js

hashCode

Java 中的 hashCode 使用是 djb2 算法,JS 版代码如下:

// https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript
String.prototype.hashCode = function () {
  var hash = 0,
    i,
    chr;
  if (this.length === 0) return hash;
  for (i = 0; i < this.length; i++) {
    chr = this.charCodeAt(i);
    hash = (hash << 5) - hash + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
};

在 Git 中的应用

使用 Git 的时候总会看到一些命令需要指定 <commit> 参数,例如:

  • git revert <commit>
  • git cherry-pick <commit>
  • git tag <commit>

这里的 commit,也被称为 commit id/revision/version,是对提交对象(commit object)的内容使用 SHA-1 算法计算后生成的唯一标识,用于区分单次提交。

可以通过 git log 查看提交记录的散列值(commit hash):

$ git log -2 --pretty=format:%H
66d138b8dc3b989468ace59342ecf98bd7ef25d6
66c43371371c281a245e496daaca5a24c22ed7ba

$ git log -2 --pretty=format:%h
66d138b
66c4337

比起完整的 commit hash,7 位的散列值缩写(abbreviated commit hash)更为常见,在 SourceTree 的 Commit 列显示便是缩写。

HTTP ETag

HTTP 响应头 ETag 一般也是使用内容的散列值、时间戳的散列值表示,比如 MDN 上的示例:

ETag: "33a64df551425fcc55e4d42a148795d9f25f89d4"
ETag: W/"0815"

HTTP 标准并没有明确指定生成 ETag 值的方法,比如 nginx 默认使用的就不是常见的 MD5、SHA 算法:

etag: "60f55c60-169"
etag: W/"60f55d70-1e02"

CSS Modules

CSS Modules 允许我们像引入 ES Modules 一样引入 CSS。

/* style.module.css */
.foo {
  color: green;
}

:global(.foo) {
  font-size: 14px;
}
import styles from './style.module.css';

const element = document.createElement('div');
element.innerHTML = '<div class="' + styles.foo + '">CSS Modules</div>';
document.body.appendChild(element);

和普通 CSS 不同,CSS Module 中的样式拥有局部作用域,也就是 Scoped CSS,可以避免全局样式污染。严格来说 CSS Modules 不涉及 Hash 算法,但是由于该提案尚未成为正式标准,需要借助第三方库实现,比如 webpack 的 css-loader 或者 PostCSS 的 postcss-modules 插件,这些第三方库在实现 CSS 局部作用域时往往使用 Hash 算法生成 CSS 类名。

css-loader

前文的 style.module.css,经 webpack 打包后会生成如下样式:

.W2bbHY3B6Xwz3MeKV2dn {
  color: green;
}

.foo {
  font-size: 14px;
}

.foo 被处理成 .W2bbHY3B6Xwz3MeKV2dn。结合 css-loader 默认配置看:

// https://webpack.js.org/loaders/css-loader/#localidentname
// https://webpack.js.org/configuration/output/#outputhashdigest
module.exports = {
  module: {
    rules: [
      {
        test: /\.css$/i,
        loader: 'css-loader',
        options: {
          modules: {
            auto: true,
            mode: 'local',
            localIdentName: '[hash:base64]',
            localIdentHashFunction: 'md4',
            localIdentHashDigest: 'hex',
            localIdentHashDigestLength: 20
          }
        }
      }
    ]
  }
};

使用 MD4 算法计算 Hash,再进行 Base64 编码,最后截取前 20 位作为类名。

postcss-modules

postcss-modules 中的 generateScopedName() 函数使用 string-hash 包来计算 CSS Hash。

string-hash 源码如下:

function hash(str) {
  var hash = 5381,
    i = str.length;

  while (i) {
    hash = (hash * 33) ^ str.charCodeAt(--i);
  }

  /* JavaScript does bitwise operations (like XOR, above) on 32-bit signed
   * integers. Since we want the results to be always positive, convert the
   * signed int to an unsigned by doing an unsigned bitshift. */
  return hash >>> 0;
}

module.exports = hash;

实现了一个类似 djb2 的 Hash 算法,返回 [0, 4294967295] 区间的整数。

CSS-in-JS

除了 CSS Modules,各种 CSS-in-JS 方案也是 Hash 算法的重度使用者,比如 styled-componentsemotion,它们都是通过 Hash 函数生成 CSS 唯一类名。

styled-components

styled-componentsstring-hash 一样使用了 djb2 算法:

// https://github.com/styled-components/styled-components/blob/main/packages/styled-components/src/utils/hash.ts

export const SEED = 5381;

// When we have separate strings it's useful to run a progressive
// version of djb2 where we pretend that we're still looping over
// the same string
export const phash = (h: number, x: string) => {
  let i = x.length;

  while (i) {
    h = (h * 33) ^ x.charCodeAt(--i);
  }

  return h;
};

// This is a djb2 hashing function
export const hash = (x: string) => {
  return phash(SEED, x);
};

emotion

emotion 使用的 Hash 函数已经单独发布成 @emotion/hash 包,实现了 MurmurHash2 算法。

在打包工具中的应用

webpackrollup 等模块打包构建工具通过 Hash 函数生成资源文件名。

webpack

见识过无聊的面试官考察 webpack 中的 hashchunkhashcontenthash 有什么区别,私以为意义不大,毕竟它们的名字就是它们的含义,而模棱两可的 hash 则需要结合具体上下文分析。

在 webpack 的文档中,这些字面量被称为 Template strings,包括 4 个级别:

  • Compilation-level
    • [fullhash] The full hash of compilation
    • [hash] deprecated
  • Chunk-level
    • [chunkhash] The hash of the chunk, including all elements of the chunk
    • [contenthash] The hash of the chunk, including only elements of this content type (affected by optimization.realContentHash)
  • Module-level
    • [hash] The hash of the module
    • [modulehash] deprecated
    • [contenthash] The hash of the content of the module
  • File-level

这些 Template strings 可以在以下配置项中使用:

  • output.assetModuleFilename
  • output.chunkFilename
  • output.filename

用于定制输出的文件名。其内部实现和 css-loader 一样都是基于 crypto 模块,默认 Hash 算法为 MD4

rollup

rollup 的 Hash 函数基于 crypto 模块,默认使用 SHA-256 算法,见 https://github.com/rollup/rollup/blob/master/src/utils/crypto.ts 代码。

短网址服务(URL Shortener)

诸如 Google 的 goo.gl,新浪微博的 t.cn,微软的 aka.ms,以及 Twitter 使用的 bit.ly,它们都是短网址服务,短网址实现的主流方法包括自增 ID 进行 62 进制转换,还有计算 Hash。可以参考知乎问题 短链接、短网址使用的是什么算法?

简单汇总

除了 SHA 家族和 MD4/MD5 家族以外,很多非密码学安全的 Hash 算法因为效率高、速度快也被广泛使用。

  • CRC16, CRC32: 校验码(比如 PNG 图片文件头)
  • DJB2: Java hashCode, styled-components
  • SDBM
  • FNV-1, FNV-1a: Go 标准库
  • xxHash: Parcel 2(基于 xxhash-wasm
  • MurmurHash2: emotion
  • MurmurHash3: Redis, FingerprintJS
  • SipHash: Redis

相关链接