128 位哈希保证无冲突

Question

是否有保证不会发生冲突的 128 散列算法（无论是加密还是非加密散列）？

如果可以保证我的字符串不会超过特定长度（是否有这样的长度？ - 我可以保证长度小于 100 个字符）

Answer 1

不，你不能做出这样的算法。如果你有一个100 个字符的字符串，你有（让字符在1..255范围内）

256**100 == (2**8)**100 == 2**800

不同的字符串（潜在冲突）；128位哈希函数只有2**128 不同的值，因为

2**128 < 2**800

碰撞是不可避免的：鸽子洞原理

编辑：想象我们有128-bit 函数；可以无碰撞的字符串的最大长度是多少？

   256**length = 2**128
(2**8)**length = 2**128
    8 * length = 128
        length = 16

所以最大长度是16（为了简单起见，我假设字符串不包含'\0'）。如果字符串是 unicode 一个（即在1..65535范围内有字符）

     65536**length = 2**128
   (2**16)**length = 2**128
       16 * length = 128
            length = 8