8

我正在寻找一种方法来创建任意字母数字字符串的 int\long 表示。哈希码不会这样做，因为我不能承受哈希冲突，即表示必须是唯一且可重复的。

数字表示将用于执行有效的（希望）比较。数字键的创建需要一些时间，但它只需要发生一次，而我需要对其进行大量比较——希望这比比较原始字符串要快得多。

任何其他关于更快字符串比较的想法也将不胜感激......

4

14 回答 14

12

除非您的字符串长度有限，否则您无法避免冲突。

整数 (2^32) 有 4294967296 个可能的值。如果您有超过 4 个 ASCII 字符或两个以上 unicode 字符的字符串，则可能的字符串值比可能的整数值多。对于每个可能的 5 个字符串，您不能有一个唯一的整数值。长值具有更多可能的值，但它们只会为每个可能的 8 个 ASCII 字符字符串提供唯一值。

哈希码作为两步过程很有用：首先查看哈希码是否匹配，然后检查整个字符串。对于大部分不匹配的字符串，只需要做第一步，真的很快。

于 2008-09-05T16:23:00.000 回答
10

你不能从哈希码开始，如果哈希码匹配，就逐个字符进行比较吗？

于 2008-09-05T16:15:36.710 回答
6

琴弦有多长？如果它们非常短，则可以通过将字符视为基数为 36 (26 + 10) 的数字来生成唯一 ID，这些数字形成n位数字，其中n是字符串的长度。另一方面，如果字符串足够短以允许这样做，那么直接比较无论如何都不会成为问题。

否则，您将不得不生成一个无冲突的散列，而这只能在预先知道完整的问题空间时才能完成（即，如果您知道所有可能出现的字符串）。你会想看看完美散列，虽然我知道找到完美散列函数的唯一可行算法是概率性的，所以理论上仍然可能发生冲突。

可能还有其他方法可以找到这样的功能。Knuth 在 TAoCP 中称这是一个“相当有趣的……谜题”，但他也没有给出算法。

通常，您提供的信息太少，无法找到不需要以某种方式探索整个问题空间的算法。这确实意味着问题的运行时间呈指数级，但可以使用机器学习启发式方法来解决。我不确定这是否适合您的情况。

于 2008-09-05T16:20:58.070 回答
2

也许：

String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);
于 2008-09-05T16:21:11.253 回答
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 的较低优先级分配值（反之亦然，具体取决于您如何比较它们） .

祝你好运！

-亚当

于 2008-09-05T16:36:00.500 回答
1

一开始有几个问题：

  1. 您是否测试过简单的字符串比较太慢了？
  2. 比较看起来如何（'ABC' == 'abc' 或 'ABC' != 'abc'）？
  3. 你要比较多少个字符串？
  4. 你需要做多少比较？
  5. 你的字符串是什么样子的（长度，字母大小写）？

据我所知，Java 中的 String 是一个对象，两个相同的字符串指向同一个对象。

所以，也许比较对象就足够了（可能字符串比较已经以这种方式实现了）。

如果它没有帮助你可以尝试在第一个元素是长度时使用字符串对象的 Pascal 实现，并且如果你的字符串有不同的长度，这应该可以节省一些 CPU 时间。

于 2008-09-05T16:22:27.583 回答
1

只要它是一个哈希函数，无论是 String.hashCode()、MD5 还是 SHA1，除非您对字符串的长度有固定限制，否则冲突是不可避免的。从无限群到有限群的一对一映射在数学上是不可能的。

退一步说，避免碰撞是绝对必要的吗？

于 2008-09-05T22:25:23.560 回答
0

你的琴弦有多长？除非您选择比字符串长的 int 表示形式，否则无论您使用何种转换，冲突总是可能发生的。因此，如果您使用 32 位整数，则只能唯一表示最多 4 个字节的字符串。

于 2008-09-05T16:14:33.203 回答
0

你的琴弦有多大？任意长的字符串不能压缩成 32/64 位格式。

于 2008-09-05T16:15:41.827 回答
0

如果您不想发生冲突，请尝试一些疯狂的东西，例如 SHA-512。我不能保证不会发生碰撞，但我认为他们还没有发现任何碰撞。

于 2008-09-05T16:16:39.797 回答
0

假设“字母数字”表示字母和数字，您可以将每个字母/数字视为以 36 为基数的数字。不幸的是，大字符串会导致数字快速增长，你不得不求助于大整数，这几乎没有效率。

如果在进行比较（即搜索特定字符串）时您的字符串通常不同，则哈希可能是您的最佳选择。一旦你得到一个潜在的命中，你可以进行字符串比较来确定。精心设计的哈希将使冲突极为罕见。

于 2008-09-05T16:18:56.000 回答
0

看起来MD5散列可以正常工作。哈希冲突的风险极不可能。根据字符串的长度，生成 int/long 的哈希会很快遇到最大值问题。

于 2008-09-05T16:19:25.627 回答
0

你为什么不做类似 1stChar + (10 x 2ndChar) + 100 x (3rdChar) .... 之类的事情，在这里你使用每个字符的简单整数值，即 a = 1、b = 2 等，或者只是如果不是字母，则为整数值。这将为每个字符串提供一个唯一的值，即使对于 2 个只是相同字母但顺序不同的字符串也是如此。

当然，如果您需要担心 Unicode 而不仅仅是 ASCII，并且如果您需要使用长字符串，数字可能会变得很大。

标准的 Java 字符串比较函数肯定不够高效吗？

于 2008-09-05T16:20:54.077 回答
0

字符串长度可能会有所不同，但现在假设为 10 个字符。

在这种情况下，为了保证唯一性，您必须使用某种大整数表示。我怀疑对大整数进行比较会比首先进行字符串比较快得多。我将支持其他人在这里所说的，使用某种哈希，然后在哈希匹配的情况下检查原始字符串以清除任何冲突。

无论如何，如果您的字符串大约有 10 个字符，我怀疑比较一堆 32 位散列会比直接字符串比较快得多。我认为您必须问自己是否真的值得增加额外的复杂性。

于 2008-09-05T16:24:47.313 回答