最多只有4个字符的唯一哈希？

Question

什么是创建字符串哈希的最佳方法，如果哈希不能超过4个字符，并且这4个字符只能是小写字母或数字？

我想要哈希的字符串有1-255个字符。我知道可能不可能创建一个没有冲突的4个字符哈希。但是，如果我有一个好的哈希，其中可能的冲突被最小化，那就足够了。

我尝试的是来自此处的CRC16CCITT：http://introcs.cs.princeton.edu/java/61data/CRC16CCITT.java

public class CRC16CCITT { 

    public static void main(String[] args) { 
        int crc = 0xFFFF;          // initial value
        int polynomial = 0x1021;   // 0001 0000 0010 0001  (0, 5, 12) 

        // byte[] testBytes = "123456789".getBytes("ASCII");

        byte[] bytes = args[0].getBytes();

        for (byte b : bytes) {
            for (int i = 0; i < 8; i++) {
                boolean bit = ((b   >> (7-i) & 1) == 1);
                boolean c15 = ((crc >> 15    & 1) == 1);
                crc <<= 1;
                if (c15 ^ bit) crc ^= polynomial;
            }
        }

        crc &= 0xffff;
        StdOut.println("CRC16-CCITT = " + Integer.toHexString(crc));
    }

}

但这样会导致过多的碰撞。是否有更好的算法？

- membersound

---

小写字母和数字意味着只有36^4种不同的哈希值，因此，即使使用生成均匀分布哈希的哈希函数，一旦你拥有了约 1296 个值（使用生日悖论），你很可能会发生碰撞。你需要在哈希空间中拥有更多的可能值。 - Andy Turner

为了测评你目前的哈希函数，可以使用一个随机数生成器，将输出限制在0到36^4-1之间，并将其作为哈希函数应用于一组不同的字符串，并比较碰撞数量。一种最优的哈希函数应该在一组不同的输入上表现得像一个随机数生成器；你可能会发现你的哈希函数已经非常接近最优了。 - tom

标题几乎指向相反的方向：限制在哈希值，而不在字符串上。定义“太多”，给出你观察到的数字（有多少个不同的字符串，有多少个冲突）。 （使用快速散列函数生成“大”整数（String.hashCode()？），使用来自 .toString(hash, 36) 的四个字符。） - greybeard

您的哈希使用数字0-9和字母'a'-'f'，而不是全部的36个字符。您需要更多的CRC位来利用整个哈希空间（36^4=1679616可用哈希值，因此至少需要21位）。 - tom

个人偏好，清晰度，代码长度，以及如何处理填充等方面。 - tom

Answer 1

你把“十六进制数字”和“字符”混淆了：

    int crc = 0xFFFF;          // initial value

那只有2个字节（0xFF 只占1个字节）。对于一个由4个ANSI字符组成的CRC，你需要4个字节（0xFFFFFFFF）。
你需要调整其余代码使之适应双倍长度，如不知道如何操作，请在评论中说明。

_{附：你可以用少于4个字节来实现这个功能，但这会让问题变得比必要更加复杂。}

- walen

---

我对CRC算法或字节编码并不熟悉。我只是使用了我问题中链接的示例类。如果您能根据4个ANSI字符提供一个适应的算法，那就太好了。 - membersound

请查看32位（4字节）版本，"直接计算"部分在末尾：http://introcs.cs.princeton.edu/java/61data/CRC32.java.html - walen