在字符串上生成唯一的整数/长哈希键，以实现更快的比较
我很好奇其他人是如何解决这个问题的，以及天真的解决方案背后可能潜藏着什么问题：
我有一个处理股票市场数据的系统。有数以万计的符号，以及相关的价格/大小，以每毫秒几千的速度流入系统。
在每个节拍上需要进行的基本操作之一是字符串比较，以查看传入的符号是否与我们感兴趣的符号匹配。在如此高的频率下，这些字符串比较的优化可以在整个系统的性能中产生可测量的差异。
我正在考虑生成符号字符串的散列，并将其与记录一起存储。对于随后的比较，系统应该使用这个散列(如果是int或long，比较应该是单个操作，而不是遍历字符串的每个字符，直到发现不匹配)。
让我们忽略生成散列本身的成本(实际上，这可能是令人望而却步的)。我能看到的唯一问题是，对于大量的唯一符号，散列冲突(两个单独的符号生成相同的散列)将是灾难性的。有没有一种散列算法可以保证匹配特定约束(比如字符数限制)的字符串是唯一的？
编辑:我将用Java编写这段代码。不确定hashCode的(碰撞)质量或计算速度。
回答 10
Stack Overflow用户
发布于 2009-07-02 16:33:00
也许哈希函数在这里不是最好的方法。如果您正在接收一个股票代码(而不是股票代码的哈希值)，那么您将不得不在每次收到它时计算它的哈希值。如果这是一个没有冲突的散列算法，那么无论如何你都需要查看符号的每个字符。所以你不妨直接比较一下这些字符。
我建议为你感兴趣的所有报价器建立一个Trie数据结构。(参见http://en.wikipedia.org/wiki/Trie)。遍历树中的每个符号，如果到达报价器的末尾没有找到匹配项，那么它就不是一个有趣的报价器。
使用散列，您无论如何都必须在感兴趣的报价器的所有散列值的集合中执行此遍历。
Stack Overflow用户
发布于 2009-07-02 16:12:23
常见的加密散列函数，如SHA-1，输出20字节(160位)。你们的股票代号有多长？如果我们讨论像"WMT“(沃尔玛)、"KO”(可口可乐)等这样的ticker symbols，那么它们似乎只有几个字节长--因此，直接比较它们应该比处理20字节的散列更快。您提到了散列冲突--我不会担心它们，特别是当输入比散列输出小得多的时候。
根据编程语言和平台的不同，您可以将字节转换为int或long，然后在一条CPU指令中对这些“数字”进行比较。(我不知道现代编译器是否可以通过调用memcmp来比较一堆字节的速度。)
Stack Overflow用户
发布于 2009-07-02 16:12:24
你应该考虑使用Perfect hash function，我认为它符合你的要求
https://stackoverflow.com/questions/1075250
复制相似问题
腾讯云开发者
