blocks|key|1388579|text|常见的加密散列函数，如SHA-1，输出20字节(160位)。你们的股票代号有多长？如果我们讨论像"WMT“(沃尔玛)、"KO”(可口可乐)等这样的ticker+symbols，那么它们似乎只有几个字节长--因此，直接比较它们应该比处理20字节的散列更快。您提到了散列冲突--我不会担心它们，特别是当输入比散列输出小得多的时候。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1388580|根据编程语言和平台的不同，您可以将字节转换为int或long，然后在一条CPU指令中对这些“数字”进行比较。(我不知道现代编译器是否可以通过调用memcmp来比较一堆字节的速度。)|style|CODE|1388581|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Ticker_symbol^0|21|E|0|0|M|3|Q|4|20|6|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@$A|U|B|V|F|G]|$A|W|B|X|F|G]|$A|Y|B|Z|F|G]]|9|@]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

Common cryptographic hash functions like SHA-1 outputs 20 bytes (160 bit). How long are your stock symbols? If we're talking about <a href="http://en.wikipedia.org/wiki/Ticker_symbol" rel="nofollow noreferrer">ticker symbols</a> like "WMT" (Walmart), "KO" (Coca-Cola), etc, then they seem to be only a couple of bytes long -- thus it should be faster to compare them directly instead of dealing with a 20 byte hash. You mention hash collisions -- I wouldn't worry about them, especially not when the inputs are much smaller than the hash output.

You might be able to cast the bytes into an <code>int</code> or <code>long</code> depending on the programming language and platform and then do the comparison between these "numbers" in one CPU instruction. (I don't know if modern compilers can compare a bunch of bytes equally fast with a call to <code>memcmp</code>?)

blocks|key|1047117|text|你应该考虑使用Perfect+hash+function，我认为它符合你的要求|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1047118|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Perfect_hash_function^0|7|L|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You should consider using a <a href="http://en.wikipedia.org/wiki/Perfect_hash_function" rel="nofollow noreferrer">Perfect hash function</a>, I think it fits your requirements

blocks|key|1047153|text|任何像样的哈希函数都能很好地处理冲突。基本上，如果散列的结果是存在多个答案的命中结果，那么该桶中就有一个潜在解决方案的链表，并且必然会减慢寻找正确答案的速度(如果存在的话)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1047154|但是不要编写自己的散列函数，使用外部的散列函数。|1047155|哦，而且我认为生成散列应该只做一次。因为您有一个正在跟踪的事物的查找表，而哈希表应该只在您添加要扫描的新“有趣”事物时才需要更改。|1047156|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Any decent hash function handles collisions well. Basically, if the hash results in a hit for which multiple answers exist, there's a linked list of potential solutions in that bucket, and of necessity, things slow down in finding the correct answer (if one exists).

But don't write your own hash function, use one that is out there.

Oh, and generating the hash should be done only once, I would think. Because you have a lookup table of things you are tracking, and the hash table should only have to change when you add a new "interesting" thing to scan for.

blocks|key|86196|text|编辑:比我自己的评论更好的评论被抛上(更早)，这使得我的评论充其量是多余的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|86197|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Edit: Better comments than my own were thrown on (and earlier), making mine redundant at best.

blocks|key|87016|text|也许哈希函数在这里不是最好的方法。如果您正在接收一个股票代码(而不是股票代码的哈希值)，那么您将不得不在每次收到它时计算它的哈希值。如果这是一个没有冲突的散列算法，那么无论如何你都需要查看符号的每个字符。所以你不妨直接比较一下这些字符。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|87017|我建议为你感兴趣的所有报价器建立一个Trie数据结构。(参见http://en.wikipedia.org/wiki/Trie)。遍历树中的每个符号，如果到达报价器的末尾没有找到匹配项，那么它就不是一个有趣的报价器。|offset|length|87018|使用散列，您无论如何都必须在感兴趣的报价器的所有散列值的集合中执行此遍历。|87019|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Trie^0|0|U|X|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

Maybe hash functions aren't the best approach here. If you're receiving a ticker symbol (and not the hash of the ticker symbol) you're going to have to compute the hash for it every single time it comes through. If its a hashing algorithm with no collisions, you'll need to look at every character of the symbol anyway. So you might as well directly compare the characters.

I suggest building a Trie data structure of all the tickers you're interested in. (see <a href="http://en.wikipedia.org/wiki/Trie" rel="noreferrer">http://en.wikipedia.org/wiki/Trie</a>). Traverse the tree for each symbol and if you reach the end of the ticker without finding a match, then its not an interesting ticker.

With hashing, you'll have to do this traversal anyway in the set of all hash values of the interesting tickers.

blocks|key|87035|text|你想要的是一个具有良好辨别能力的快速哈希函数。对于每个字符串，计算关联的散列函数并将其与字符串一起存储。然后，为了进行比较，代码:+if+(Hash(s1)==Hash(s2)+&&+s1==s2)+Then+{+...+}除非散列匹配，否则不会进行实际的字符串比较，实际上只有当字符串匹配时才会进行比较。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|87036|有些人会告诉你要实现一个完美的哈希。只有当要散列的字符串集的大小有限制时才能这样做，通常只有10-1000个。对于任意大的字符串词汇表，您不能这样做。因为您不能这样做，所以您实际上必须比较字符串以确定是否相等。|87037|加密散列有很强的辨别能力，但并不是为了快速而设计的。CRC函数通常速度非常快，辨别能力也很好，大多数语言都很容易找到能够快速计算这些函数的库(使用字节的查表技术)。我们使用CRC-32，它对此非常有效(基本上，当字符串不匹配时，2%5E32发生散列冲突的可能性为1)。您可以使用CRC-64，但它提供的额外辨别能力并不会真正增加任何真正的功能。|87038|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

What you want is a fast hash function that has good discrimination power.
For each string, compute the associated hash function and store it with the string.
Then for a comparison, code:
 if (Hash(s1)==Hash(s2)
 &amp;&amp; s1==s2)
 then { ... }
The actual string compare won't occur unless the hashes match, which in practice
is only when the strings match.

Some folks will tell you to implement a perfect hash. You can only do
that when the set of strings you want to hash has bounded size, usually
only 10-1000. You can't do that for an arbitrarily big vocabulary of strings. 
Since you can't do that, you actually have to compare the strings to determine equality.

Cryptographic hashes have great discrimination power but aren't designed
to be fast. What is generally very fast and has good discrimination
power are CRC functions, and most langauges have easily found libraries
that compute these quickly (using a table lookup technique on bytes).
We use CRC-32 and it is very effective for this (basically 1 chance in 2^32 that a hash collision will occur, when the strings
don't match). You can use CRC-64, but the additional discrimination power
it provides won't really add any real functionality.

blocks|key|1047343|text|我同意上面关于Trie结构的建议，认为这是解决这种情况的最佳方法。在计算上等同于完美的哈希，但在概念上要漂亮得多。这是假设你的符号在长度上是有限制的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1047344|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I second the above suggestion of a Trie structure as the best approach for this case. Computationally equivalent to a perfect hash, but conceptually much prettier. This is presuming your symbols are bounded in length.

blocks|key|1388741|text|FWIW，在我参与的上一个高数据量项目中，我们发现使用一些高度调优的C代码对数据进行过滤、聚合和预分类是关键。我们所有的提要都进入了这个预处理器，在将大量数据传递给基于Java的系统进行处理之前，它负责进行简单的数据清理。基本上，预处理器做的就是你想要的:识别感兴趣的记录，验证它们是完整的，并删除重复和空白。在高峰期，预处理器可以消除我们每小时获得的大约800万条记录中的20%25+(可能不是我想象中的从股票市场提要中获得的量)。我们最初的Java版本幸运地得到了一半(但它至少是“优雅的”！)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1388742|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

FWIW, on the last high-data-volume project I was on, we found filtering, aggregating and pre-classifying data using some heavily-tuned C code was key. All our feeds went into this pre-processor and it took care of the simple data cleansing before passing the bulk of the data to our Java-based system for processing. Basically the pre-processor did just what you're asking: identifying records of interest, verifying they were complete and removing dups and empties. During peak times the pre-processor could eliminate up to 20% of the 8M or so records we'd get per hour (probably not quite the volume I imagine you get from stock market feeds). Our original Java version was lucky to get half that (but it was "elegant", at least!)

blocks|key|4264785|text|如果您接收的是4个字母的滚动条符号，那么每个字母应该可以表示为一个字节。把这4个放在一起组成一个32位的int，瞧，你就有了你的"hash“。现在，您可以使用一条机器指令将其与参考进行比较。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4264786|如果您没有使用Java，那就是说。|4264787|我真的不建议在对速度要求很高的情况下使用Java，特别是不建议每毫秒进行数千次字符串比较。|4264788|编辑:如果你想使用64位代码，你可以把8个字母打包到每个长整数，然后在一条指令中进行比较。|4264789|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

If you are receiving 4-letter ticker symbols, then each letter should be representable as a single byte. Pack all 4 together into a 32-bit int, and voila, you have your "hash". You can now compare this against the reference using a single machine instruction.

If you weren't using Java, that is.

I really wouldn't suggest using Java for anything speed-critical, especially not thousands of string comparisons per millisecond.

edit: If you wanted to use 64-bit code, you could pack up to 8 letters per long int and then compare in 1 instruction.

blocks|key|87121|text|不管它有什么价值。我专门针对CMS+(NYSE)和CQS+(NASDAQ)符号系统解决了这个问题。符号根长度最多为6个字符，且为大写。我的要求如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|87122|87123|数据将到达未知符号|unordered-list-item|87124|在接收数据时计算要用于comparison|87125|Compute的哈希值一次，将该值存储在映射中以供将来的comparison|87126|Value比较将是相等的|87127|87128|值比较将针对一个范围。|87129|87130|例如，如果用于GOOG的数据到达，则需要对其进行处理并将其分发到符号范围F-HAA中的进程。(F+<=+GOOG+<=+HAA+)。我使用了一个具有低值(F)和高值(HAA)的range类。我的哈希函数概念类似于将字符打包成字节，但是出于日志记录、网络和端序的目的，我选择了unsigned+long+long作为我的存储类型。在调用此函数之前，用“@”字符填充符号。(IBM@)|87131|unsigned+long+long+SymbolToVal(std::string&+str)
{
+size_t+maxlen+=+6;+//+Symbology+constraint
+if+(str.length()+!=+maxlen)+return+0;
+unsigned+long+long+val;
+unsigned+long+long+retval=0;
+int+expon+=+maxlen*2;+//+ASCII+val+range+(65-90)
+double+factor+=+std::pow(10.0,expon);
+expon-=2;
+for+(size_t+i+=+0;+i+<+maxlen;+i%2B%2B)
+{
++++val+=+(unsigned+long+long)factor+*+str[i];
++++retval+%2B=+val;
++++factor+=+(unsigned+long+long)+std::pow(10.0,expon);
++++expon-=2;
++}
++return+retval;
+}|code-block|syntax|javascript|87132|一种蛮力方法是计算所有可能的符号，对它们进行适当的排序，并为它们分配一个整数，然后将它们存储在映射中。如果传入数据只包含总域的一小部分(这是正常情况)，则可能是过度杀伤力。|87133|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|13|8|@]|9|@]|A|$]]|$1|H|3|I|5|E|7|14|8|@]|9|@]|A|$]]|$1|J|3|K|5|E|7|15|8|@]|9|@]|A|$]]|$1|L|3|-4|5|E|7|16|8|@]|9|@]|A|$]]|$1|M|3|N|5|E|7|17|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|18|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|19|8|@]|9|@]|A|$]]|$1|R|3|S|5|T|7|1A|8|@]|9|@]|A|$U|V]]|$1|W|3|X|5|6|7|1B|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]]|Z|$]]

For what its worth. I solved this problem specific to CMS (NYSE) and CQS (NASDAQ) symbology. Symbol roots will be at most 6 characters long and will be uppercase. My requirements were as follows:

<ul>
<li>Data would arrive for unknown symbol</li>
<li>Upon receiving data compute a hash value to be used for comparison</li>
<li>Compute the value once, store the value in a map for future comparison</li>
<li>Value comparisons will be equality</li>
<li>Value comparisons will be against a range.</li>
</ul>

For Example If data for GOOG arrives it will need to be processed and distributed to processes in the symbol range [F-HAA]. ( F &lt;= GOOG &lt;= HAA ) . I used a range class that has a low value (F) and a high value (HAA). My Hash function concept is similar to packing the characters into bytes but for logging,network, and endian purposes I chose unsigned long long as my storage type. Prior to calling this function the symbols are padded with an '@' character. (IBM@@@)

<pre><code>unsigned long long SymbolToVal(std::string&amp; str)
{
 size_t maxlen = 6; // Symbology constraint
 if (str.length() != maxlen) return 0;
 unsigned long long val;
 unsigned long long retval=0;
 int expon = maxlen*2; // ASCII val range (65-90)
 double factor = std::pow(10.0,expon);
 expon-=2;
 for (size_t i = 0; i &lt; maxlen; i++)
 {
 val = (unsigned long long)factor * str[i];
 retval += val;
 factor = (unsigned long long) std::pow(10.0,expon);
 expon-=2;
 }
 return retval;
 }
</code></pre>

A brute force method would be to compute all possible symbols sort them properly and assign them an integer then store them in a map. May be overkill if incoming data only consists of a small portion of the total domain (which is the normal case).

I'm curious how others have solved this problem, and what problems might lurk behind the naive solution:

I have a system which processes stock market data. There are tens of thousands of symbols, with associated prices/sizes, flowing into the system at the rate of several thousand every millisecond.

One of the basic operations that needs to happen on every tick is string comparison to see if the incoming matches the symbol we are interested in. At such high frequency, optimization of these string comparisons can make a measurable difference in the performance of the whole system.

I am thinking of generating a hash of the symbol string, and storing it with the record. For subsequent comparison, the system should use this hash (being an int or a long, the comparison should be a single operation, rather than iterating through each character of the string until a mismatch is found).

Let's ignore the cost of generating the hash itself (which, in reality, may actually be prohibitive). The only problem I can see is that with a large number of unique symbols, a hash collision (two separate symbols generate the same hash) would be devastating. Is there a hashing algorithm which guarantees that strings which match certain constraints (such as limit on the number of characters) are unique?

EDIT: I'll write this code in Java. Not sure of the (collision) quality of hashCode or the speed with which it is calculated.

unique integer/long hash key generation over strings for faster compairson

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我很好奇其他人是如何解决这个问题的，以及天真的解决方案背后可能潜藏着什么问题：我有一个处理股票市场数据的系统。有数以万计的符号，以及相关的价格/大小，以每毫秒几千的速度流入系统。在每个节拍上需要进行的基本操作之一是字符串比较，以查看传入的符号是否与我们感兴趣的符号匹配。在如此高的频率下，这些字符串比较的优化可以在整个系...

问在字符串上生成唯一的整数/长哈希键，以实现更快的比较
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在字符串上生成唯一的整数/长哈希键，以实现更快的比较EN