MinMPHash & MinMPLookup & MinMPHFilter

Mini Minimal Perfect Hash & Mini Minimal Perfect Lookup

English README

TypeScript/JavaScript 平台上的最小完美哈希与查找工具实现。如果只使用哈希函数包体积小于 3KB(Gzip)。

MinMPHash 可以把一组数量为 n 的字符串映射到 [0, n-1] 的整数范围内，且不会有冲突。

MinMPLookup 则是在 MinMPHash 的基础上实现的最小完美查找表工具。

它可以把形如 { key1: [value1, value2, ...], key2: [value3, value4, ...] } 的映射表最小化存储，从而实现根据 value 查找对应 key 的需求。

相比原样存储，最小化的查找表可以将体积缩小到原来的 10% 以下（具体压缩率取决于数据集中 values 的信息熵，熵越大压缩效果越好）。

什么是最小完美哈希？

哈希函数可以把数据映射到一个范围内，生成固定长度的“指纹”。但普通哈希函数有两个常见问题：

• 稀疏性导致的空间浪费：哈希值域通常远大于实际数据量，哈希表会非常稀疏。
• 不同输入可能产生冲突：不同的输入可能映射到相同的哈希值，为了降低冲突率通常需要更长的哈希值，从而浪费空间。

最小完美哈希函数（Minimal Perfect Hash Function，MPHF）是一类特殊哈希函数：

• 它对给定的 n 个不同输入保证无冲突；
• 输出范围恰好为 [0, n-1]，使得空间利用达到最优。

换句话说，如果你有 n 个不同的字符串，MPHF 会把它们一一映射到 [0, n-1] 的整数范围内，每个字符串对应一个唯一索引。

    text set               Hash              Hash Table (Sparse)
  +----------+        +------------+        +-------------------+
  |  Apple   | ---->  |    h(x)    | ---->  | 0: [ Apple ]      |
  |  Banana  |        +------------+        | 1:                | <--- Gap
  |  Cherry  |                              | 2: [ Banana ]     |
  +----------+                              | 3:                | <--- Gap
                                            |       ...         | <--- Gap
                                            | 9: [ Cherry ]     |
                                            +-------------------+
                                              (Waste of Space)


    text set      🤩 Minimal Perfect Hash      Hash Table (Compact)
  +----------+        +--------------+        +-------------------+
  |  Apple   | ---->  |   mmph(x)    | ---->  | 0: [ Apple ]      |
  |  Banana  |        +--------------+        | 1: [ Banana ]     |
  |  Cherry  |                                | 2: [ Cherry ]     |
  +----------+                                +-------------------+
                                             ( 100% Space Utilization )

什么时候使用最小完美哈希？

最小完美哈希适用于需要将一组确定性的键（Key）映射为紧凑整数索引的场景。与普通映射表相比，使用 MPHF 可以省去存储完整键的开销：只需存储键对应的整数索引即可实现相同的映射功能。

换言之，只要键在数据集中是确定的（不会变化），无论键本身有多长，都可以用一个基于数据集大小的 number 存储并唯一标识该键，而不会产生冲突。

这正是常见哈希（如 MD5、SHA-1）做不到的：它们产生的哈希值较长（如 MD5 为 16 字节、SHA-1 为 20 字节），而 MPHF 能根据数据集大小选择最小的整数范围，从而达到更高的空间利用率。

举一个例子，有一组字体名称列表，要从根据字体名映射到字体的系列名 一般的方法是通过一个映射表来完成这一切：

let FontMap = {
  "Source Sans": "Source Sans",
  "Source Sans Black": "Source Sans",
  "Source Sans Bold": "Source Sans",
  "思源黑体 CN ExtraLight": "Source Sans",
  "思源黑体 TW Light": "Source Sans",
  // ... 6000+
};

let query = "思源黑体 TW Light";
let found = FontMap[query]; // 'Source Sans'

这样的映射表需要存储所有的键（如字体名称），当键数量较多时会非常占空间。使用最小完美哈希后，我们可以只存储字体名称对应的索引（哈希值），而不是完整名称：

// 创建包含所有字体名称的集合
let values = [
  "Source Sans",
  "Source Sans Black",
  "Source Sans Bold",
  "思源黑体 CN ExtraLight",
  "思源黑体 TW Light",
  // ... 6000+
];

// 根据 values 创建最小完美哈希字典
let dict = createMinMPHashDict(values);
// 根据字典创建哈希函数实例
let minHash = new MinMPHash(dict);

// 然后我们使用哈希值来代替完整的字体名称：
let FontMapWithHash = {
  "Source Sans": [1, 2, 3, 21 /* ... */],
  Heiti: [12, 12 /* ... */],
  "JetBrains Mono": [32, 112 /* ... */],
  // ...
};

// 查询时，先计算哈希值，再通过哈希值查找对应的字体系列名
let query = "思源黑体 TW Light";
let query_hash = minHash.hash(query, dict); // e.g. 42

let found = Object.entries(FontMapWithHash).find(([family, hashes]) =>
  hashes.includes(query_hash)
)[0]; // 'Source Sans'

这样可以显著减少存储空间，因为不再需要保存完整的键文本，只需保存更短的整数索引。

你可能会想到 MD5 或 SHA-1 之类的哈希函数也能生成标识，但它们的哈希值较长（如 MD5 为 16 字节、SHA-1 为 20 字节）。FNV-1a 在某些场景下可用到最少 4 字节，但其冲突率较高。最小完美哈希可根据数据集大小选择最小范围，保证无冲突并实现极致的空间利用。

使用方法

安装

npm install min-mphash

此包仅提供 ESM，使用构建工具可以很的进行 tree-shaking 以减小体积。

// hash build & hush function
min-mphash/index.js         34.7 kB
min-mphash/index.min.js     14.6 kB   4.9 kB（Gzip）


// hush function only
min-mphash/runtime.js       18.3 kB
min-mphash/runtime.min.js   7.9 kB    2.8 kB（Gzip）

MinMPHash 最小完美哈希的使用

这是最核心的功能，用于将一组字符串映射到 [0, n-1] 的整数。

步骤 1: 创建字典 (构建时)

在你的构建脚本或服务端代码中，生成哈希字典。

import { createMinMPHashDict } from "min-mphash";
import * as fs from "fs";

// 示例字符串集合
const mySet = ["Apple", "Banana", "Cherry", "Date", "Elderberry"];

// 创建字典二进制数据
// outputBinary: true 返回 Uint8Array，适合存储或网络传输
const dictBuffer = createMinMPHashDict(mySet, {
  outputBinary: true,
  level: 5, // 优化级别 [1-10]，越高体积越小但构建越慢
});

fs.writeFileSync("mph-dict.bin", dictBuffer);

步骤 2: 使用字典生成哈希值 (运行时)

在你的应用（如浏览器端）加载字典并进行哈希查询。

import { MinMPHash } from "min-mphash";

// 假设你已经加载了二进制数据
const dictBuffer = await fetch("mph-dict.bin").then((res) => res.arrayBuffer());
const dict = new Uint8Array(dictBuffer);

const mph = new MinMPHash(dict);

console.log(mph.hash("Apple")); // 0 (或其他 0-4 之间的唯一值)
console.log(mph.hash("Banana")); // 2
console.log(mph.hash("Cherry")); // 4

// 注意：对于不在集合中的字符串，它也会返回一个 [0, n-1] 的值（这是 MPHF 的特性），
// 除非你启用了**校验模式**（见下文）。
console.log(mph.hash("sdfsd94jx#*")); // 可能返回 1

校验模式 onlySet

标准的最小完美哈希函数对于不在集合中的输入也会返回一个 [0, n-1] 范围内的索引（这属于 MPHF 的性质）。如果你的应用需要把集合外的查询识别为“未命中”，可以在创建字典时启用校验模式 onlySet。

onlySet 会以额外空间为代价存储每个键的指纹（fingerprint），查询时会校验指纹：若校验失败则返回 -1 表示未命中。

let dict = createMinMPHashDict(mySet, { onlySet: "8" });

| onlySet | 空间占用（每 key） | 误判率 | | ------- | ------------------ | ------------ | | 2 | 0.25 byte | ~25% | | 4 | 0.5 byte | ~6.25% | | 8 | 1 byte | ~0.39% | | 16 | 2 bytes | ~0.0015% | | 32 | 4 bytes | ~0.00000002% |

注：表中“误判率”指的是对于不在集合中的输入，被错误判定为在集合中的概率；如果键确实在集合中，校验总是成功。

字典格式：JSON/CBOR/CBOR.Gzip

createMinMPHashDict 可以输出多种格式的字典：

• 二进制
  { outputBinary: true }
  返回 CBOR Uint8Array
• 压缩二进制
  { outputBinary: true, enableCompression: true}
  Gzip 压缩后的 CBOR Uint8Array
• JSON
  默认
  JavaScript 对象，适合调试和查看。

通常来说，推荐使用压缩二进制格式，体积最小， 但 JSON 开发时比较方便，如果服务器/CDN 支持透明压缩， 可以直接使用 JSON 格式，最终体积相差不大。

MinMPLookup 最小完美查找表的使用

如果你有一个 Value -> Key 的查找需求（例如：根据字体文件名查找字体家族名，或者根据城市查找国家），且数据量较大，可以使用 MinMPLookup。它利用 MPHF 和差分编码极大地压缩了映射关系。

场景

假设你有以下映射：

const lookupMap = {
  China: ["Beijing", "Shanghai", "Guangzhou"],
  USA: ["New York", "Los Angeles"],
  Japan: ["Tokyo"],
};
// 目标：输入 "Shanghai" -> 得到 "China"

创建查找字典

import { createMinMPLookupDict } from "min-mphash";

const lookupMap = {
  China: ["Beijing", "Shanghai", "Guangzhou"],
  USA: ["New York", "Los Angeles"],
  Japan: ["Tokyo"],
};

// 生成压缩后的二进制字典
const lookupDictBin = createMinMPLookupDict(lookupMap, {
  outputBinary: true,
  enableCompression: true, // 启用内置 Gzip 压缩 (仅 Node/Bun 环境或支持 CompressionStream 的浏览器)
});

// 保存到文件
// fs.writeFileSync("lookup.bin", lookupDictBin);

查询

import { MinMPLookup } from "min-mphash";

// 加载字典
const lookup = await MinMPLookup.fromCompressed(lookupDictBin);
// 如果没有开启 enableCompression，使用 MinMPLookup.fromBinary(bin)

console.log(lookup.query("Shanghai")); // "China"
console.log(lookup.queryAll("New York")); // ["USA"]
console.log(lookup.query("Unknown City")); // null
console.log(lookup.keys()); // ["China", "USA", "Japan"]

校验模式 onlySet

标准的最小完美哈希函数对于不在集合中的输入，也会返回一个范围内的索引。为了解决这个问题，MinMPHash 支持内置校验模式，确保让集合外的查找返回 null。

const lookupDictBin = createMinMPLookupDict(lookupMap, {
  onlySet: "8", // 启用 8-bit 校验模式
});

MinMPHFilter 最小完美过滤器的使用

MinMPHFilter 是一个类似布隆过滤器的静态集合查询工具， 可以高效地判断一个元素是否在集合中，且具有可配置的误判率。

背景

如果你有个一个字符串集合，需要查询某个字符串是否在集合中，并且集合不需要经常更改（每次更改需要重新生成字典文件），就可以使用 MinMPHFilter，它让你存储这个集合时尽可能的节省空间，它的存储尺寸几乎是信息论上限。

它的工作原理类似布隆过滤器，但使用 GCS 算法实现，具有更高的空间效率和可配置的误判率。

使用方法

import { createMinMPHFilterDict, MinMPHFilter } from "min-mphash";
// 创建过滤器字典
const filterDict = createMinMPHFilterDict(mySet, {
  //  误判率：
  //  *  - 6 : ~1.56%
  //  *  - 7 : ~0.78%
  //  *  - 8 : ~0.39%
  //  *  - 9 : ~0.20%
  //  *  - 10 : ~0.10%
  //  *  - 11 : ~0.05%
  //  *  - 12 : ~0.02%
  //  *  - 13 : ~0.01%
  //  *  - 14 : ~0.005%
  //  *  - 15 : ~0.0025%
  //  *  - 16 : ~0.0012%
  bitKey: "8",
  outputBinary: true, // 由于生成的二级制数据熵非常高，基本不需要压缩
});

// 使用过滤器
const filter = new MinMPHFilter(filterDict);
console.log(filter.has("Apple")); // true

Benchmark

MinMPHash 字典体积测试结果

=== MinMPHash Big Dataset Size Benchmark ===
Generating dataset of size 1000000...
Dataset size: 1000000 items

Dataset json size: 41836.25 KB
Dataset json gzip size: 6473.48 KB

➤ Optimization Level 5
┌──────────┬──────────────┬──────────────────────┬──────────────────────┬──────────────┬──────────────┐
│ OnlySet │ JSON Size │ Binary Size (Ratio) │ Gzip Size (Ratio) │ vs None │ Build Time │
├──────────┼──────────────┼──────────────────────┼──────────────────────┼──────────────┼──────────────┤
│ none │ 979.18 KB │ 341.37 KB ( 35%) │ 268.36 KB ( 27%) │ 100.0 % │ 2502.35 ms │
│ 2 │ 1849.51 KB │ 585.38 KB ( 32%) │ 512.86 KB ( 28%) │ 171.5 % │ 2981.46 ms │
│ 4 │ 2721.75 KB │ 829.94 KB ( 30%) │ 757.49 KB ( 28%) │ 243.1 % │ 3109.38 ms │
│ 8 │ 4465.27 KB │ 1318.06 KB ( 30%) │ 1245.64 KB ( 28%) │ 386.1 % │ 3132.11 ms │
│ 16 │ 6672.22 KB │ 2293.96 KB ( 34%) │ 2222.43 KB ( 33%) │ 672.0 % │ 3559.02 ms │
│ 32 │ 11468.63 KB │ 4247.06 KB ( 37%) │ 4176.07 KB ( 36%) │ 1244.1 % │ 2900.32 ms │
└──────────┴──────────────┴──────────────────────┴──────────────────────┴──────────────┴──────────────┘

MinMPLookup 字典体积测试结果

=== MinMPLookup Big Dataset Size Benchmark ===
Generating dataset of size 100000 values...
Dataset stats: 5000 keys, 100000 values

Dataset json size: 7577.04 KB
Dataset json gzip size: 5141.74 KB

➤ Optimization Level 5
┌──────────┬──────────────┬──────────────────────┬──────────────────────┬──────────────┬──────────────┐
│ OnlySet │ JSON Size │ Binary Size (Ratio) │ Gzip Size (Ratio) │ vs None │ Build Time │
├──────────┼──────────────┼──────────────────────┼──────────────────────┼──────────────┼──────────────┤
│ none │ 709.67 KB │ 254.85 KB ( 36%) │ 199.59 KB ( 28%) │ 100.0 % │ 412.65 ms │
│ 2 │ 797.00 KB │ 279.23 KB ( 35%) │ 225.14 KB ( 28%) │ 109.6 % │ 393.94 ms │
│ 4 │ 884.32 KB │ 303.63 KB ( 34%) │ 248.92 KB ( 28%) │ 119.1 % │ 408.93 ms │
│ 8 │ 1058.92 KB │ 352.48 KB ( 33%) │ 297.58 KB ( 28%) │ 138.3 % │ 477.32 ms │
│ 16 │ 1406.98 KB │ 450.21 KB ( 32%) │ 395.21 KB ( 28%) │ 176.7 % │ 421.70 ms │
│ 32 │ 2104.73 KB │ 645.45 KB ( 31%) │ 591.02 KB ( 28%) │ 253.3 % │ 374.06 ms │
└──────────┴──────────────┴──────────────────────┴──────────────────────┴──────────────┴──────────────┘