如何将由{A,C,G,T}组成的长度k的字符串转换为0到4^k之间的哈希整数

转换方法 #

本质是把字符串视为一个四进制数，每个位置的字符映射值对应四进制的一位，最终转成十进制整数即可，取值范围刚好是0到4^k -1，完全符合你要求的0到4^k区间。

• 第一步：按规则映射每个字符为对应数字：A→0，C→1，G→2，T→3
• 第二步：从字符串的最左端到最右端，依次作为四进制的最高位到最低位，按位计算十进制值，公式为：

最终整数 = d₀ * 4^(k-1) + d₁ * 4^(k-2) + ... + d₍k₋₂₎ *4¹ + d₍k₋₁₎ *4⁰
其中d₀是第一个字符的映射值，d₁是第二个，以此类推，k为字符串总长度

示例：转换字符串"ACT" #

1. 逐字符映射：A→0，C→1，T→3，得到数字序列[0,1,3]
2. 代入公式计算：
   0 * 4² + 1 * 4¹ + 3 *4⁰ = 0*16 +1*4 +3*1 =7
   得到的结果7完全在0~63（也就是4³-1）的范围内，符合要求。

参考实现代码（Python） #

def acgt_to_int(s: str) -> int:
    char_map = {'A':0, 'C':1, 'G':2, 'T':3}
    result = 0
    for c in s:
        result = result * 4 + char_map[c]
    return result

# 测试用例
print(acgt_to_int("ACT")) # 输出7

这个迭代写法不用手动计算幂次，效率更高，每读入一个字符就把当前结果乘4（相当于四进制左移一位）再加当前位的数值，逻辑和上述公式完全等价。

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