2

我正在寻找为非常特定的字符串情况创建哈希码的最有效方法。

我有可以转换为整数的字符串，它们从 1 到 10,000 不等，并且非常集中在 1-600 范围内。

我的问题是，就从集合中检索项目以实现其哈希码的性能而言，最有效的方法是什么。

我在想的是：

  • 我可以将字符串转换为整数并使用直接访问表（10.000 行的数组）——这对于检索来说非常快，但在内存分配方面不是很聪明；

  • 我可以将字符串用作字符串并为其获取哈希码（我不必将其转换为整数，但我不知道字符串的哈希码在冲突方面的效果如何）

非常感谢任何其他想法。

多谢

谢谢大家及时回复...

还有另一个我忘记添加的信息。如果我让你知道我的最终目标，我想它会让你明白这一点——我什至可能不需要哈希表！！！

我只想针对不可变的字典验证流。我想检查给定标签是否出现在我的消息中。

我将收到一个带有几对 tag=value 的字符串。我想验证我的应用程序是否必须处理标签。

4

4 回答 4

1

您可能需要考虑使用 trie (http://en.wikipedia.org/wiki/Trie) 或基数树 (http://en.wikipedia.org/wiki/Radix_tree)。无需将字符串解析为整数，或计算哈希码。当你走绳子时，你正在走一棵树。

编辑：

在字符串上计算哈希码和从字符串中解析整数都涉及遍历整个字符串，然后使用该值作为对特定数据结构的查找。其他技术可能涉及在遍历数据结构的同时检查字符串。这可能对要求“其他想法”的发帖人有价值。

于 2012-05-22T20:34:48.673 回答
1

许多集合（例如 HashMap）已经应用了一种补充的“rehash”方法来帮助处理糟糕的哈希码算法。例如浏览HashMap.hash(). 并且字符串是非常常见的键，因此您可以确定 String.hashCode() 是高度优化的。所以，除非你注意到你的 hashCodes 之间有很多冲突，否则我会使用标准代码。

我尝试将 0..600 的字符串放入 HashSet 以查看发生了什么，但是查看有多少条目发生冲突非常乏味。寻找你自己！如果您真的很在意，请将 HashMap 中的源代码复制到您自己的类中，对其进行编辑，以便您可以访问条目（在我正在查看的 Java 6 源代码中，即transient Entry[] tableYMMV），然后添加方法计算碰撞。

于 2012-05-22T21:02:36.167 回答
0

If there are only a limited valid range of values, why not represent the collection as a int[10000] as you suggested? The value at array[x] is the number of times that x occurs.

If your strings are represented as decimal integers, then parsing them to strings is a 5-iteration loop (up to 5 digits) and a couple of additions and subtractions. That is, it is incredibly fast. Inserting the elements is effectively O(1), retrieval is O(1). Memory required is around 40kb (4 bytes per int).

One problem is that insertion order is not preserved. Maybe you don't care.

Maybe you could think about caching the hashcode and only updating it if your collection has changed since the last time hashcode() was called. See Caching hashes in Java collections?

于 2012-05-22T20:59:41.100 回答
0

«插入免责声明，仅当它是您应用程序中的热点并且您可以证明时才这样做»

那么整数值本身将是一个完美的哈希函数，您不会遇到任何冲突。但是这种方法有两个问题：

  1. HashMap不允许您指定自定义哈希函数。所以要么你必须实现你自己的HashMap，要么你使用一个包装器对象。
  2. HashMap使用按位而不是模运算来查找存储桶。这显然会丢掉一些东西，因为它只是一个面具。java.util.HashMap.hash(int)试图弥补这一点，但我看到声称这不是很成功。我们再次回到实施您自己的HashMap.

现在既然您使用整数值作为哈希函数，为什么不使用整数值作为键HashMap而不是字符串呢？如果你真的想优化它，你可以编写一个使用int而不是Integer键的哈希映射，或者使用来自trove的TIntObjectHashMap。

如果您真的对寻找好的哈希函数感兴趣，我可以推荐Hashing in Smalltalk，请忽略作者对 Java 的咆哮（免责声明：我认识作者）。

于 2012-05-22T21:13:03.710 回答