64位整数转短字符串算法是否存在碰撞？能否实现唯一可逆？

问题背景 #

抱歉误用了“hash function”一词。我正尝试以紧凑但明文的方式序列化游戏状态——我可以将大部分所需数据打包进一个64位整数，但让玩家复制长达20位的数字串过于繁琐。我认为若将其映射到信息密度更高的字符集，就能减少玩家需要复制粘贴的内容。

原问题 #

我想要编写一个将64位整数转换为更短字符串且可反向转换的算法：要求完全可逆且无碰撞。我的思路是，这类整数的最大值为18,446,744,073,709,551,615（十进制20位）。若转换为基数64（非通用编码方案！），则仅需13个字符即可表示该值（64^13=302,231,454,903,657,293,676,544）。我编写了以下将十进制整数转换为基数64字符串的函数，但不确定是否遗漏了边缘情况：

const HASH : Array # Contains 64 characters: 0-9, a-z, A-Z, '?', and '!'
const HASH_MASK : int = int(pow(2, 6) - 1)
const HIGH_MASK : int = int(pow(2, 64)) # 0b10000000...

func to_hash(value : int) -> String:
    var string : String = ""
    while true:
        string = HASH[value & HASH_MASK] + string
        # Shift bits without preserving high bit.
        for _i in range(6): # 2 ^ 6 = 64, the number of hash characters available.
            value = (value >> 1) & (~HIGH_MASK)
        if value == 0:
            break
    return string

func from_hash(string : String) -> int:
    var value : int = 0
    for character in string:
        var bits : int = HASH.find(character)
        assert(bits != -1, "Invalid hash character: " + character)
        value = (value << 6) | bits
    return value

请问该算法是否存在碰撞？能否满足我的需求——每个唯一的64位整数都生成唯一且可唯一反向转换的字符串？

解答 #

你的算法不会产生碰撞，只要确保HASH数组中的64个字符完全唯一，就能满足“每个64位整数对应唯一可反向转换字符串”的需求。具体分析如下：

核心逻辑的可逆性 #

to_hash和from_hash的逻辑是严格互逆的：

• to_hash每次提取当前整数的低6位，映射为HASH数组中的对应字符并拼接到结果头部，随后将整数右移6位（等价于除以64取整）；
• from_hash则遍历字符串的每个字符，将当前结果左移6位（等价于乘以64），再加上字符对应的6位数值。

由于每个6位值（0-63）都对应HASH中唯一的字符，且反向转换时每个字符也能唯一映射回对应的6位值，整个过程是一一对应的，不存在碰撞的可能。

边缘情况验证 #

• 输入值为0：to_hash会提取0的低6位（即0），拼接HASH[0]后将值右移6位变为0，循环终止，返回单个字符；from_hash处理该字符时会正确还原为0，逻辑无误。
• 最大值处理：64位无符号整数的最大值（18446744073709551615）需要13个字符表示，你的算法会完整提取所有6位段，生成对应的13字符字符串，反向转换也能准确还原最大值。

可优化的细节 #

原代码中的移位逻辑可以简化：

# 替换原循环6次右移的代码
value = value >> 6

因为64位无符号整数右移6位会自动高位补0，和循环6次右移1位的结果完全一致，且& (~HIGH_MASK)操作是多余的——HIGH_MASK是2^64，对应64位整数范围外的位，对实际存储的64位数值没有影响。

内容的提问来源于stack exchange，提问作者Hammer Bro.