blocks|key|3081103|text|免责声明:如果您希望有效地散列单个自然语言单词，则此解决方案适用。对于较长的文本或包含非字母字符的文本，它的散列效率很低。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|3081104|我不知道有一个函数，但这里有一个想法可能会有帮助：|3081105|3081106|将64位中的52位用于表示字符串中存在的字母。例如，如果'a‘存在，你应该为'b’设置位1，为'A‘设置bit26。这样，只有包含完全相同的字母集的文本才具有相同的“签名”。|unordered-list-item|3081107|3081108|然后，您可以使用剩余的12位对字符串长度(或其模数值)进行编码，以进一步减少冲突，或者使用传统的散列函数生成12位的hashCode。|3081109|假设您的输入是纯文本的，我可以想象这将导致极少的冲突，并且计算成本很低(O(n))。与到目前为止的其他解决方案不同，这种方法将问题域考虑在内，以减少冲突-它基于Programming+Pearls+(参见here)中描述的字形检测器。|3081110|entityMap|0|LINK|mutability|MUTABLE|url|http://shriphani.com/blog/2008/06/14/an-anagram-detector/|1^0|0|1P|0|0|0|18|1|0|0|0|0|2U|4|1|0^^$0|@$1|2|3|4|5|6|7|Z|8|@$9|10|A|11|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|12|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|13|8|@]|D|@]|E|$]]|$1|I|3|J|5|K|7|14|8|@]|D|@$9|15|A|16|1|17]]|E|$]]|$1|L|3|-4|5|6|7|18|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|19|8|@]|D|@]|E|$]]|$1|O|3|P|5|6|7|1A|8|@]|D|@$9|1B|A|1C|1|1D]]|E|$]]|$1|Q|3|-4|5|6|7|1E|8|@]|D|@]|E|$]]]|R|$S|$5|T|U|V|E|$W|X]]|Y|$5|T|U|V|E|$W|X]]]]

DISCLAIMER: This solution is applicable if you wish to efficiently hash individual natural language words. It is inefficient for hashing longer text, or text containing non-alphabetic characters.

I'm not aware of a function but here's an idea that might help:

<ul>
<li>Dedicate 52 of the 64 bits to representing which letters are present in the String. For example, if 'a' were present you'd set bit[0], for 'b' set bit <a href="http://shriphani.com/blog/2008/06/14/an-anagram-detector/" rel="nofollow noreferrer">1</a>, for 'A' set bit[26]. That way, only text containing exactly the same set of letters would have the same "signature".</li>
</ul>

You could then use the remaining 12 bits to encode the string length (or a modulo value of it) to further reduce collisions, or generate a 12 bit hashCode using a traditional hashing function.

Assuming your input is text-only I can imagine this would result in very few collisions and would be inexpensive to compute (O(n)). Unlike other solutions so far this approach takes the problem domain into account to reduce collisions - It is based off the Anagram Detector described in Programming Pearls (see <a href="http://shriphani.com/blog/2008/06/14/an-anagram-detector/" rel="nofollow noreferrer">here</a>).

blocks|key|327025|text|Create+an+SHA-1+hash，然后掩码出最低的64位。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|327026|entityMap|0|LINK|mutability|MUTABLE|url|http://www.anyexample.com/programming/java/java_simple_class_to_compute_sha_1_hash.xml^0|0|K|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]]]]

<a href="http://www.anyexample.com/programming/java/java_simple_class_to_compute_sha_1_hash.xml" rel="nofollow noreferrer">Create an SHA-1 hash</a> and then mask out the lowest 64bits.

blocks|key|324438|text|你有没有看过Apache+commons+lang|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|324439|但是对于64位(和128位)，你需要一些技巧:+Joshua+Bloch所著的Effective一书中的规则可以帮助你轻松地创建64位散列(只需使用long而不是int)。对于128位，你需要额外的hack...|324440|entityMap|0|LINK|mutability|MUTABLE|url|http://commons.apache.org/lang/api-release/org/apache/commons/lang/builder/HashCodeBuilder.html^0|6|J|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Do you look at <a href="http://commons.apache.org/lang/api-release/org/apache/commons/lang/builder/HashCodeBuilder.html" rel="nofollow noreferrer">Apache commons lang</a>?

But for 64 bit (and 128) you need some tricks: the rules laid out in the book Effective Java by Joshua Bloch help you create 64 bit hash easy (just use long instead of int). For 128 bit you need additional hacks...

blocks|key|324446|text|long+hash+=+string.hashCode();|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|324447|是的，前32位将是0，但在遇到哈希冲突问题之前，您可能会耗尽硬件资源。字符串中的hashCode非常有效，并且经过了良好的测试。|unstyled|324448|sfussenegger更新我认为上面的方法满足了最简单的可能的工作，然而，我同意@sfussenegger扩展现有字符串hashCode的想法。|324449|除了为字符串提供良好的hashCode之外，您可能还需要考虑在实现中重新散列散列代码。如果您的存储被其他开发人员使用，或者与其他类型一起使用，这可以帮助分发您的密钥。例如，Java的HashMap基于长度为2的幂的哈希表，所以它添加了这个函数来确保低位充分分布。|324450|++++h+%5E=+(h+>>>+20)+%5E+(h+>>>+12);
++++return+h+%5E+(h+>>>+7)+%5E+(h+>>>+4);|324451|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|P|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$B|C]]|$1|M|3|-4|5|F|7|T|8|@]|9|@]|A|$]]]|N|$]]

<pre><code>long hash = string.hashCode();
</code></pre>

Yes, the top 32 bits will be 0, but you will probably run out of hardware resources before you run into problems with hash collisions. The hashCode in String is quite efficient and well tested.

Update
I think the above satisfies the simplest thing which could possibly work, however, I agree with @sfussenegger idea of extending the existing String hashCode.

In addition to having a good hashCode for your String, you may want to consider rehashing the hash code in your implementation. If your storage is used by other developers, or used with other types, this can help distributed your keys. For example, Java's HashMap is based on power-of-two length hash tables, so it adds this function to ensure the lower bits are sufficiently distributed.

<pre><code> h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);
 return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);
</code></pre>

blocks|key|3081185|text|为什么不使用CRC64多项式呢？这些都是相当有效和优化的，以确保所有的位都被计数并分布在结果空间中。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3081186|如果你用谷歌搜索"CRC64+Java“，网上有很多可用的实现。|3081187|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Why not use a CRC64 polynomial. These are reasonably efficient and optimized to make sure all bits are counted and spread over the result space. 

There are plenty of implementations available on the net if you google "CRC64 Java"

blocks|key|324481|text|这样做：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|324482|import+java.io.ByteArrayOutputStream;
import+java.io.DataOutputStream;
import+java.io.IOException;
import+java.math.BigInteger;
import+java.security.MessageDigest;
import+java.security.NoSuchAlgorithmException;

public+class+Test+{

++++public+static+void+main(String[]+args)+throws+NoSuchAlgorithmException,
++++++++++++IOException+{
++++++++ByteArrayOutputStream+baos+=+new+ByteArrayOutputStream();
++++++++DataOutputStream+dos+=+new+DataOutputStream(baos);

++++++++try+{
++++++++++++MessageDigest+md+=+MessageDigest.getInstance("MD5");
++++++++++++SomeObject+testObject+=+new+SomeObject();

++++++++++++dos.writeInt(testObject.count);
++++++++++++dos.writeLong(testObject.product);
++++++++++++dos.writeDouble(testObject.stdDev);
++++++++++++dos.writeUTF(testObject.name);
++++++++++++dos.writeChar(testObject.delimiter);
++++++++++++dos.flush();

++++++++++++byte[]+hashBytes+=+md.digest(baos.toByteArray());
++++++++++++BigInteger+testObjectHash+=+new+BigInteger(hashBytes);

++++++++++++System.out.println("Hash+"+%2B+testObjectHash);
++++++++}+finally+{
++++++++++++dos.close();
++++++++}
++++}

++++private+static+class+SomeObject+{
++++++++private+int+count+=+200;
++++++++private+long+product+=+1235134123l;
++++++++private+double+stdDev+=+12343521.456d;
++++++++private+String+name+=+"Test+Name";
++++++++private+char+delimiter+=+'\n';
++++}
}|code-block|syntax|javascript|324483|DataOutputStream允许您编写原语和字符串，并将它们输出为字节。在其中包装一个ByteArrayOutputStream将允许您写入字节数组，该数组与MessageDigest很好地集成在一起。您可以从列出的任何算法here中进行选择。|offset|length|324484|最后，BigInteger将允许您将输出字节转换为更易于使用的数字。MD5和SHA1算法都会生成128位的散列，因此如果需要64位，只需截断即可。|324485|SHA1应该能够很好地散列几乎所有的东西，并且很少会发生冲突(128位)。这在Java中工作，但我不确定它是如何实现的。它实际上可能是相当快的。它适用于我的实现中的几个字段:只需将它们全部推送到DataOutputStream上，就可以开始工作了。您甚至可以使用反射和注释(也许是@HashComponent(order=1)来显示哪些字段进入散列以及以何种顺序)。它有一个128位的变种，我想你会发现它使用的CPU并不像你想象的那么多。|style|CODE|324486|我已经使用这样的代码来获取巨大数据集(到目前为止可能有数十亿个对象)的散列，以便能够跨多个后端存储对它们进行分片。无论你需要它做什么，它都应该起作用。请注意，我认为您可能只想调用MessageDigest.getInstance()一次，然后再调用clone()：IIRC克隆速度要快得多。|324487|entityMap|0|LINK|mutability|MUTABLE|url|http://java.sun.com/javase/6/docs/api/java/io/DataOutputStream.html|1|http://java.sun.com/javase/6/docs/api/java/io/ByteArrayOutputStream.html|2|http://java.sun.com/javase/6/docs/api/java/security/MessageDigest.html|3|http://java.sun.com/javase/6/docs/technotes/guides/security/StandardNames.html#MessageDigest|4|http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#BigInteger(byte[])^0|0|0|0|G|0|19|L|1|29|D|2|36|4|3|0|3|A|4|0|2P|G|3W|N|0|2H|R|3G|7|0^^$0|@$1|2|3|4|5|6|7|18|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1A|8|@]|9|@$I|1B|J|1C|1|1D]|$I|1E|J|1F|1|1G]|$I|1H|J|1I|1|1J]|$I|1K|J|1L|1|1M]]|A|$]]|$1|K|3|L|5|6|7|1N|8|@]|9|@$I|1O|J|1P|1|1Q]]|A|$]]|$1|M|3|N|5|6|7|1R|8|@$I|1S|J|1T|O|P]|$I|1U|J|1V|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1W|8|@$I|1X|J|1Y|O|P]|$I|1Z|J|20|O|P]]|9|@]|A|$]]|$1|S|3|-4|5|6|7|21|8|@]|9|@]|A|$]]]|T|$U|$5|V|W|X|A|$Y|Z]]|10|$5|V|W|X|A|$Y|11]]|12|$5|V|W|X|A|$Y|13]]|14|$5|V|W|X|A|$Y|15]]|16|$5|V|W|X|A|$Y|17]]]]

Do something like this:

<pre><code>import java.io.ByteArrayOutputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class Test {

 public static void main(String[] args) throws NoSuchAlgorithmException,
 IOException {
 ByteArrayOutputStream baos = new ByteArrayOutputStream();
 DataOutputStream dos = new DataOutputStream(baos);

 try {
 MessageDigest md = MessageDigest.getInstance("MD5");
 SomeObject testObject = new SomeObject();

 dos.writeInt(testObject.count);
 dos.writeLong(testObject.product);
 dos.writeDouble(testObject.stdDev);
 dos.writeUTF(testObject.name);
 dos.writeChar(testObject.delimiter);
 dos.flush();

 byte[] hashBytes = md.digest(baos.toByteArray());
 BigInteger testObjectHash = new BigInteger(hashBytes);

 System.out.println("Hash " + testObjectHash);
 } finally {
 dos.close();
 }
 }

 private static class SomeObject {
 private int count = 200;
 private long product = 1235134123l;
 private double stdDev = 12343521.456d;
 private String name = "Test Name";
 private char delimiter = '\n';
 }
}
</code></pre>

<a href="http://java.sun.com/javase/6/docs/api/java/io/DataOutputStream.html" rel="nofollow noreferrer">DataOutputStream</a> lets you write primitives and Strings and have them output as bytes. Wrapping a <a href="http://java.sun.com/javase/6/docs/api/java/io/ByteArrayOutputStream.html" rel="nofollow noreferrer">ByteArrayOutputStream</a> in it will let you write to a byte array, which integrates nicely with <a href="http://java.sun.com/javase/6/docs/api/java/security/MessageDigest.html" rel="nofollow noreferrer">MessageDigest</a>. You can pick from any algorithm listed <a href="http://java.sun.com/javase/6/docs/technotes/guides/security/StandardNames.html#MessageDigest" rel="nofollow noreferrer">here</a>.

Finally <a href="http://java.sun.com/javase/6/docs/api/java/math/BigInteger.html#BigInteger(byte[])" rel="nofollow noreferrer">BigInteger</a> will let you turn the output bytes into an easier-to-use number. The MD5 and SHA1 algorithms both produce 128-bit hashes, so if you need 64 you can just truncate.

SHA1 should hash almost anything well, and with infrequent collisions (it's 128-bit). This works from Java, but I'm not sure how it's implemented. It may actually be fairly fast. It works on several fields in my implementation: just push them all onto the <code>DataOutputStream</code> and you're good to go. You could even do it with reflection and annotations (maybe <code>@HashComponent(order=1)</code> to show which fields go into a hash and in what order). It's got a 128-bit variant and I think you'll find it doesn't use as much CPU as you think it will.

I've used code like this to get hashes for huge data sets (by now probably billions of objects) to be able to shard them across many backend stores. It should work for whatever you need it for. Note that I think you may want to only call <code>MessageDigest.getInstance()</code> once and then <code>clone()</code> from then on: IIRC the cloning is a lot faster.

blocks|key|326143|text|反转字符串以获得另一个32位哈希码，然后将两者合并：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|326144|String+s+=+"astring";
long+upper+=+(+(long)+s.hashCode()+)+<<+32;
long+lower+=+(+(long)+s.reverse().hashCode()+)+-+(+(long)+Integer.MIN_VALUE+);
long+hash64+=+upper+%2B+lower;|code-block|syntax|javascript|326145|这是伪代码；String.reverse()方法不存在，需要以其他方式实现。|offset|length|style|CODE|326146|entityMap^0|0|0|6|G|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Reverse the string to get another 32-bit hashcode and then combine the two:

<pre><code>String s = "astring";
long upper = ( (long) s.hashCode() ) &lt;&lt; 32;
long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE );
long hash64 = upper + lower;
</code></pre>

This is pseudocode; the <code>String.reverse()</code> method doesn't exist and will need to be implemented some other way.

blocks|key|326152|text|今天(2018)的答案。SipHash。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|326153|它将比这里的大多数答案快得多，并且比所有答案的质量都要高得多。|326154|Guava库有一个：https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--|offset|length|326155|entityMap|0|LINK|mutability|MUTABLE|url|https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--^0|0|0|A|2T|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

An answer for today (2018). SipHash.

It will be much faster than most of the answers here, and significantly higher quality than all of them.

The Guava library has one: <a href="https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--" rel="noreferrer">https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--</a>

I'm looking for a hash function that:

<ol>
<li>Hashes textual strings well (e.g. few collisions)</li>
<li>Is written in Java, and widely used</li>
<li>Bonus: works on several fields (instead of me concatenating them and applying the hash on the concatenated string)</li>
<li>Bonus: Has a 128-bit variant.</li>
<li>Bonus: Not CPU intensive.</li>
</ol>

What is a good 64bit hash function in Java for textual strings?

大数据

Java

我正在寻找一个散列函数：对文本字符串进行哈希处理效果很好(例如，很少冲突)是用Java语言编写的，并且被广泛使用奖励:适用于多个字段(而不是我将它们连接起来并对连接的字符串应用散列)奖励:具有128位CPU不密集型。

问在Java中，对于文本字符串，什么是一个好的64位哈希函数？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Java中，对于文本字符串，什么是一个好的64位哈希函数？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Java中，对于文本字符串，什么是一个好的64位哈希函数？
EN