Java에서 텍스트 문자열을위한 좋은 64 비트 해시 함수는 무엇입니까?

Java에서 텍스트 문자열을위한 좋은 64 비트 해시 함수는 무엇입니까?

---

다음과 같은 해시 함수를 찾고 있습니다.

1. 텍스트 문자열을 잘 해시 합니다 (예 : 충돌이 거의 없음).
2. Java로 작성되었으며 널리 사용됨
3. 보너스 : 여러 필드에서 작동합니다 (이를 연결하고 연결된 문자열에 해시를 적용하는 대신)
4. 보너스 : 128 비트 변형이 있습니다.
5. 보너스 : CPU 집약적이지 않습니다.

---

long기본값 의 변형 을 사용하지 않는 이유는 무엇입니까 String.hashCode()(정말 똑똑한 사람들이이 코드를 이미 살펴본 수천 명의 개발자 눈은 언급하지 않고 확실히 효율적으로 만들기 위해 노력하는 곳)?

// adapted from String.hashCode()
public static long hash(String string) {
  long h = 1125899906842597L; // prime
  int len = string.length();

  for (int i = 0; i < len; i++) {
    h = 31*h + string.charAt(i);
  }
  return h;
}

더 많은 비트를 찾고 있다면 아마도BigInteger 편집을 사용할 수 있습니다 .

@brianegge의 답변에 대한 의견에서 언급했듯이 32 비트 이상의 해시에는 사용 사례가 많지 않으며 64 비트 이상의 해시에는 단일 사용 사례가 없을 가능성이 큽니다.

수십억 개의 매핑을 저장하는 수십 개의 서버에 분산 된 거대한 해시 테이블을 상상할 수 있습니다. 이러한 시나리오의 경우 @brianegge는 여전히 유효한 지점을 가지고 있습니다. 32 비트는 2 ^ 32 (약 43 억) 개의 서로 다른 해시 키를 허용합니다. 강력한 알고리즘이라고 가정하면 여전히 충돌이 거의 발생하지 않습니다. 64 비트 (18,446,744,073 억 개의 서로 다른 키)를 사용하면 필요한 미친 시나리오에 관계없이 확실히 절약 할 수 있습니다. 128 비트 키 (340,282,366,920,938,463,463,374,607,431 억 개의 가능한 키)에 대한 사용 사례를 생각하는 것은 거의 불가능합니다.

여러 필드에 대한 해시를 결합하려면 XOR을 소수와 곱한 다음 추가하면됩니다.

long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);

작은 소수는 전환 된 값에 대해 동일한 해시 코드를 피하기 위해 존재합니다. 즉, { 'foo', 'bar'} 및 { 'bar', 'foo'}는 같지 않으며 다른 해시 코드를 가져야합니다. XOR은 두 값이 같으면 0을 반환하므로 잘못되었습니다. 따라서 { 'foo', 'foo'} 및 { 'bar', 'bar'}는 동일한 해시 코드를 갖습니다.

---

SHA-1 해시 를 만든 다음 가장 낮은 64 비트를 마스킹합니다.

---

long hash = string.hashCode();

예, 상위 32 비트는 0이지만 해시 충돌 문제가 발생하기 전에 하드웨어 리소스가 부족할 수 있습니다. String의 hashCode는 매우 효율적이고 잘 테스트되었습니다.

업데이트 위의 내용 이 작동 할 수있는 가장 간단한 것을 만족한다고 생각 하지만 기존 String hashCode를 확장하는 @sfussenegger 아이디어에 동의합니다.

String에 대한 좋은 hashCode를 갖는 것 외에도 구현에서 해시 코드를 다시 해싱하는 것을 고려할 수 있습니다. 다른 개발자가 스토리지를 사용하거나 다른 유형과 함께 사용하는 경우 키를 배포하는 데 도움이 될 수 있습니다. 예를 들어, Java의 HashMap은 2의 제곱 길이 해시 테이블을 기반으로하므로 하위 비트가 충분히 분산되도록이 함수를 추가합니다.

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);

---

CRC64 다항식을 사용하지 않는 이유는 무엇입니까? 이는 합리적으로 효율적이며 모든 비트가 계산되고 결과 공간에 분산되도록 최적화됩니다.

"CRC64 Java"를 검색하면 인터넷에서 사용할 수있는 많은 구현이 있습니다.

---

다음과 같이하십시오.

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';
    }
}

DataOutputStream을 사용하면 기본 요소와 문자열을 작성하고이를 바이트로 출력 할 수 있습니다. ByteArrayOutputStream 을 래핑하면 MessageDigest 와 잘 통합되는 바이트 배열에 쓸 수 있습니다 . 여기에 나열된 알고리즘 중에서 선택할 수 있습니다 .

마지막으로 BigInteger 를 사용하면 출력 바이트를 사용하기 쉬운 숫자로 바꿀 수 있습니다. MD5 및 SHA1 알고리즘은 모두 128 비트 해시를 생성하므로 64 개가 필요한 경우 자르기 만하면됩니다.

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 DataOutputStream and you're good to go. You could even do it with reflection and annotations (maybe @HashComponent(order=1) 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 MessageDigest.getInstance() once and then clone() from then on: IIRC the cloning is a lot faster.

---

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

String s = "astring";
long upper = ( (long) s.hashCode() ) << 32;
long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE );
long hash64 = upper + lower;

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

---

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: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--

---

Do you look at Apache commons lang?

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...

---

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:

• 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 1, for 'A' set bit[26]. That way, only text containing exactly the same set of letters would have the same "signature".

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 here).

ReferenceURL : https://stackoverflow.com/questions/1660501/what-is-a-good-64bit-hash-function-in-java-for-textual-strings