我正在寻找一种创建任意字母数字字符串的int\long表示的方法。哈希码不适用，因为我不能承受哈希冲突，即表示必须是唯一且可重复的。
数值表示将用于执行高效（希望如此）的比较。创建数值键将需要一些时间，但它只需要发生一次，而我需要使用它执行大量的比较 - 这将希望比比较原始字符串要快得多。
欢迎提供任何其他更快的字符串比较想法...
14个回答
12
如果你的字符串长度没有限制，你就无法避免碰撞。
一个整数有4294967296种可能的值（2 ^ 32）。如果你有一个超过4个ASCII字符或两个Unicode字符以上的字符串，那么可能的字符串值就比可能的整数值多。每个可能的5个字符字符串都不能拥有一个唯一的整数值。长值具有更多的可能值，但它们只能为每个可能的8个ASCII字符的字符串提供一个唯一的值。
哈希码在两步处理中非常有用：首先检查哈希码是否匹配，然后再检查整个字符串。对于大多数不匹配的字符串，你只需要进行第一步操作，速度非常快。
- Don Kirkby
10
您是否可以先使用哈希码，如果哈希码匹配，则进行逐个字符比较？
- Patrick McElhaney
6
如果字符串很短，那么可以将字符视为36进制（26个字母+10个数字）中的数字，形成一个n位数（n为字符串长度），从而生成唯一ID。另一方面，如果字符串足够短，则直接比较不会成为问题。
否则，您需要生成无冲突哈希值，这只有在预先知道完整问题空间时才能完成（即如果您知道可能出现的所有字符串）。您将想要查看perfect hashing，尽管我所知道的找到完美哈希函数的唯一可行算法是概率性的，因此在理论上仍然可能发生碰撞。
可能还有其他方法来找到这样的函数。Knuth在TAoCP中称其为“相当有趣的...难题”，但他也没有给出算法。
总的来说，您提供的信息太少了，无法找到不需要以某种方式探测整个问题空间的算法。这不可避免地意味着该问题具有指数运行时间，但可以使用机器学习启发式算法来解决。我不确定在您的情况下是否建议这样做。
否则，您需要生成无冲突哈希值，这只有在预先知道完整问题空间时才能完成（即如果您知道可能出现的所有字符串）。您将想要查看perfect hashing，尽管我所知道的找到完美哈希函数的唯一可行算法是概率性的，因此在理论上仍然可能发生碰撞。
可能还有其他方法来找到这样的函数。Knuth在TAoCP中称其为“相当有趣的...难题”，但他也没有给出算法。
总的来说，您提供的信息太少了，无法找到不需要以某种方式探测整个问题空间的算法。这不可避免地意味着该问题具有指数运行时间，但可以使用机器学习启发式算法来解决。我不确定在您的情况下是否建议这样做。
- Konrad Rudolph
2
也许：
String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);
- toolkit
2
在一天结束时，单个字母数字至少有36种可能的值。如果包括标点符号、小写等，则可以轻松达到72个可能值。
允许您快速比较字符串的非冲突数字必须随着字符串长度呈指数增长。
因此，您首先必须确定您要比较的最长字符串。假设它是N个字符的长度，并且假设您仅需要大写字母和数字0-9，则需要具有高达36 ^ N的整数表示形式。
对于长度为25的字符串（常用名称字段），则需要具有130位的二进制数。
如果将其组成32位数字，则需要4个数字。然后，您可以比较每个数字（与遍历字符串相比，四个整数比较应该不需要时间）。我建议使用一个大数字库，但对于这种特殊情况，我相信您可以编写自己的代码并获得更好的性能。
如果您想处理每个字符的72个可能值（大写、小写、数字、标点符号...），并且需要10个字符，则需要62位 - 两个32位整数（或者如果您在支持64位计算的系统上，则需要一个64位）。
然而，如果无法限制字符串中的数字（即可能是256个字母/数字/字符等中的任何一个）并且无法定义字符串的大小，则直接比较字符串是唯一的方法，但有一种捷径。
将字符串的指针转换为32位无符号整数数组，并每次比较4个字节的字符串（或在64位处理器上每次比较64位/8字节）。这意味着100个字符的字符串最多只需要25次比较即可找到哪个更大。
您可能需要重新定义字符集（并转换字符串），以使具有更高优先级的字符分配更接近0的值，而具有较低优先级的值则更接近255（或反之亦然，具体取决于您如何进行比较）。
祝你好运！
-Adam
允许您快速比较字符串的非冲突数字必须随着字符串长度呈指数增长。
因此，您首先必须确定您要比较的最长字符串。假设它是N个字符的长度，并且假设您仅需要大写字母和数字0-9，则需要具有高达36 ^ N的整数表示形式。
对于长度为25的字符串（常用名称字段），则需要具有130位的二进制数。
如果将其组成32位数字，则需要4个数字。然后，您可以比较每个数字（与遍历字符串相比，四个整数比较应该不需要时间）。我建议使用一个大数字库，但对于这种特殊情况，我相信您可以编写自己的代码并获得更好的性能。
如果您想处理每个字符的72个可能值（大写、小写、数字、标点符号...），并且需要10个字符，则需要62位 - 两个32位整数（或者如果您在支持64位计算的系统上，则需要一个64位）。
然而，如果无法限制字符串中的数字（即可能是256个字母/数字/字符等中的任何一个）并且无法定义字符串的大小，则直接比较字符串是唯一的方法，但有一种捷径。
将字符串的指针转换为32位无符号整数数组，并每次比较4个字节的字符串（或在64位处理器上每次比较64位/8字节）。这意味着100个字符的字符串最多只需要25次比较即可找到哪个更大。
您可能需要重新定义字符集（并转换字符串），以使具有更高优先级的字符分配更接近0的值，而具有较低优先级的值则更接近255（或反之亦然，具体取决于您如何进行比较）。
祝你好运！
-Adam
- Adam Davis
2
只要是散列函数，无论是String.hashCode()、MD5还是SHA1，除非对字符串的长度有限制，否则无法避免冲突。从一个无限组到一个有限组中实现一一映射在数学上不可能实现。
退一步说，避免冲突是绝对必要的吗？
退一步说，避免冲突是绝对必要的吗？
- sundae1888
1
如果字符串长度固定，为什么会避免不了碰撞？你能解释一下吗？ - Swamy
1
开始时有几个问题：
- 你测试过简单的字符串比较很慢吗？
- 比较是什么样子的（'ABC' == 'abc' 还是 'ABC' != 'abc'）？
- 你需要比较多少个字符串？
- 你需要做多少次比较？
- 你的字符串长什么样子（长度，大小写等）？
据我所知，在Java中String是一个对象，两个相同的字符串指向同一个对象。
因此，可能只需比较对象（可能已经以这种方式实现了字符串比较）。
如果这不起作用，您可以尝试使用Pascal实现的字符串对象，其中第一个元素是长度，如果您的字符串具有不同的长度，则应该可以节省一些CPU时间。
- ggierlik
0
你的字符串有多长？除非你选择的整数表示比字符串更长，否则无论使用什么转换，冲突总是可能发生的。因此，如果你使用32位整数，你只能唯一地表示长度不超过4个字节的字符串。
- Chris Upchurch
0
你的字符串有多长？任意长的字符串无法压缩成32/64位格式。
- Pramod
0
如果你不想发生碰撞，可以尝试像 SHA-512 这样的疯狂算法。虽然我不能保证不会出现碰撞，但我认为目前还没有人发现过。
- Thomas Owens
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接