如何生成自定义字符集、长度且碰撞率最低的字符串哈希？

一、最优实现方式 #

你提到的截断SHA-1十六进制输出的方法虽然简单，但确实没充分利用目标字符集的全部空间——比如如果字符集包含a-zA-Z0-9!?-=（共66个字符），每个字符能表示约6.04位（log2(66)≈6.04），10个字符就能承载约60.4位的信息；而十六进制每个字符仅4位，10个字符只有40位，空间利用率差距明显。

最优的做法是先获取哈希算法输出的二进制原始数据，再将这些二进制位编码为目标字符集中的字符，最大化利用字符集的哈希空间。具体步骤如下：

1. 用密码学哈希算法（如SHA-1、SHA-256）生成二进制哈希值；
2. 定义目标字符集并计算其长度M；
3. 将二进制哈希值转为大整数，通过不断对M取余得到字符索引，从字符集中取出对应字符，直到得到N个字符。

以下是JavaScript示例（目标字符集为a-zA-Z0-9!?-=，N=10）：

const crypto = require('crypto');

// 定义目标字符集
const charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!?-=';
const charsetLength = charset.length;
const targetLength = 10;

function generateOptimizedHash(input) {
    // 生成SHA-256二进制哈希（更长的输出能提供更多位用于转换）
    const hashBuffer = crypto.createHash('sha256').update(input).digest();
    // 将Buffer转为BigInt
    const hashBigInt = BigInt('0x' + hashBuffer.toString('hex'));
    let result = '';
    let remaining = hashBigInt;
    
    for (let i = 0; i < targetLength; i++) {
        // 取余得到字符索引
        const index = Number(remaining % BigInt(charsetLength));
        result = charset[index] + result;
        // 整除缩小数值
        remaining = remaining / BigInt(charsetLength);
    }
    
    return result;
}

// 示例调用
console.log(generateOptimizedHash('foo'));

这种方式能把哈希的二进制位充分映射到目标字符集，让N个字符的哈希空间达到M^N，是理论上的最优利用方式。

二、截断SHA-1哈希的碰撞概率问题 #

截断SHA-1后的碰撞概率增量近似与哈希空间的缩减成正比，不会因为内部位关联而显著升高。

原因在于：SHA-1作为密码学哈希算法，其输出的各个位近似独立且均匀分布——截断后的前k位（对应十六进制的k/4个字符）依然符合均匀随机分布的特征。对于理想的k位哈希，碰撞概率近似为n²/(2^(k+1))（n为哈希的数量）；截断SHA-1得到的k位哈希，碰撞概率和这个理想值几乎一致，不会因原哈希的内部结构出现明显更高的碰撞概率。

当然，无论哪种方式，缩短哈希长度都会提升碰撞概率，但在非安全关键场景下，这种近似完全可以接受。

内容的提问来源于stack exchange，提问作者Marco Ancona