如何设计将短字符串哈希为0-15整数的算法 用于Redis分库降低碰撞率

优先选成熟工业级哈希，无需自研 #

• 首推MurmurHash3 32位版本，计算完成后直接取低4位（hash_val & 0xF）即可得到0-15的结果。该算法专门针对短输入做了优化，比特分布均匀度经过海量工业场景验证，绝大多数编程语言都有现成的实现可以直接调用，不需要自己写核心逻辑。
• 若输入字符串普遍短于8字节，也可以选择CityHash 16位变体，同样取低4位使用，性能和分布表现都优于绝大多数自研哈希。

必须自研时的设计要点 #

如果场景不允许引入外部依赖必须自研，遵循以下规则可以把碰撞概率降到最低：

• 保证输入字符串的每一位字符都参与哈希运算，不要只取头部/尾部几位字符计算。
• 初始哈希值选择经过验证的经典魔数，比如5381、0x9e3779b9，不要用0、1这类简单值，避免初始偏斜。
• 运算过程中加入移位操作，把高位信息扩散到低位，确保最终取的低4位受所有输入字符影响。参考实现如下：

def hash_to_0_15(input_str: str) -> int:
    h = 5381
    for char in input_str:
        h = (h << 5 + h) + ord(char) # 等价于 h = h * 33 + 字符ASCII码，移位运算效率更高
    return h & 0xF # 位运算等价于对16取模，结果范围0-15

特别注意：不要直接对所有字符的ASCII码求和后取模，这类方法对短字符串的分布偏斜非常严重，碰撞概率是通用哈希的3~5倍

进一步降低碰撞的优化手段 #

• 如果你能拿到所有需要映射的测试任务ID全集，可以先离线做分布校验：把所有ID跑一遍哈希算法，统计0-15每个值的命中次数，若不同值的命中数差超过20%，可以调整哈希的初始魔数，直到分布均匀。
• 如果存在必须规避的特定碰撞场景，可以给输入字符串加固定的盐值前缀，不同的盐值会完全改变哈希结果，测试找到一个让你当前业务集合碰撞最少的盐值固定使用即可。

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