Sha*_*baz 24 string algorithm hash comparison
我很好奇其他人是如何解决这个问题的,以及天真解决方案背后可能存在的问题:
我有一个处理股市数据的系统.有数以万计的符号,以及相关的价格/大小,以每毫秒几千的速率流入系统.
需要在每个tick上进行的基本操作之一是字符串比较,以查看传入是否匹配我们感兴趣的符号.在如此高的频率下,这些字符串比较的优化可以使整个系统的性能产生可测量的差异.
我正在考虑生成符号字符串的哈希值,并将其与记录一起存储.对于后续比较,系统应使用此哈希(为int或long,比较应该是单个操作,而不是遍历字符串的每个字符,直到找到不匹配).
让我们忽略生成散列本身的成本(实际上,这可能实际上是禁止的).我能看到的唯一问题是,对于大量唯一符号,哈希冲突(两个单独的符号生成相同的哈希)将是毁灭性的.是否有一个散列算法可以保证匹配某些约束的字符串(例如字符数限制)是唯一的？
编辑:我将用Java编写此代码.不确定hashCode的(碰撞)质量或计算速度.
Jer*_*ell 12
也许散列函数不是最好的方法.如果您收到一个股票代码(而不是股票代码的散列),您将不得不每次计算它的哈希值.如果它的哈希算法没有冲突,那么无论如何你都需要查看符号的每个字符.所以你不妨直接比较一下这些角色.
我建议建立一个你感兴趣的所有代码的Trie数据结构.(参见http://en.wikipedia.org/wiki/Trie).遍历每个符号的树,如果到达股票代码的末尾而没有找到匹配,那么它不是一个有趣的股票代码.
使用散列,无论如何,您必须在有趣的代码的所有散列值集合中进行此遍历.
| 归档时间： |
|
| 查看次数： |
10470 次 |
| 最近记录： |