algorithm - 在字符串上生成唯一的整数/长散列 key ，以便更快地进行比较

Question

我很好奇其他人是如何解决这个问题的，以及天真的解决方案背后可能潜伏着什么问题:

我有一个处理股票市场数据的系统。有数以万计的交易品种，以及相关的价格/尺寸，以每毫秒数千个的速度流入系统。

需要在每个报价上发生的基本操作之一是字符串比较，以查看传入的交易品种是否与我们感兴趣的交易品种匹配。在如此高的频率下，优化这些字符串比较可以在性能上产生可衡量的差异整个系统。

我正在考虑生成符号字符串的散列，并将其与记录一起存储。对于后续的比较，系统应该使用这个散列(是一个 int 或一个 long，比较应该是一个单一的操作，而不是遍历字符串的每个字符直到找到不匹配)。

让我们忽略生成哈希本身的成本(实际上，这可能实际上是高得令人望而却步的)。我能看到的唯一问题是，对于大量唯一符号，哈希冲突(两个不同的符号生成相同的哈希)将是毁灭性的。是否有一种哈希算法可以保证符合特定约束条件(例如字符数限制)的字符串是唯一的？

编辑:我将用 Java 编写这段代码。不确定 hashCode 的(冲突)质量或它的计算速度。

Answer 1

也许散列函数不是这里的最佳方法。如果你收到一个股票代码(而不是股票代码的散列)，你将不得不在它每次通过时计算它的散列。如果它是一种没有冲突的散列算法，那么无论如何您都需要查看符号的每个字符。所以你还不如直接比较字符。

我建议为您感兴趣的所有代码构建一个 Trie 数据结构。(参见 http://en.wikipedia.org/wiki/Trie)。为每个符号遍历树，如果您到达代码的末尾但没有找到匹配项，那么它不是一个有趣的代码。

使用散列，您无论如何都必须在感兴趣代码的所有散列值的集合中执行此遍历。