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

StackOverflow https://stackoverflow.com/questions/1660501

문제

해시 기능을 찾고 있습니다.

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

해결책

당신은 왜 a를 사용하지 않습니까? 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 비트 이상의 해시에 대한 USECASE는 많지 않으며 64 비트 이상을 가진 해시의 경우에는 하나도 없을 것입니다.

수십억 개의 서버에 걸쳐 배포 된 거대한 해시 가능이 상상할 수 있으며 아마도 수백억 개의 매핑을 저장할 수 있습니다. 이러한 시나리오의 경우 @brianegge는 여전히 유효한 점이 있습니다. 32 비트는 2^32 (약 43 억)의 다른 해시 키를 허용합니다. 강력한 알고리즘을 가정하면 여전히 충돌이 거의 없어야합니다. 64 비트 (18,446,744,073 억 7,73 억 3 천만 명의 다른 키)를 사용하면 필요한 미친 시나리오에 관계없이 확실히 저장하십시오. 128 비트 키 (340,282,366,938,463,463,463,374,607,430 억 키)에 대한 USECASE를 생각하는 것은 거의 불가능합니다.

여러 필드의 해시를 결합하려면 간단히 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이지만 해시 충돌 문제가 발생하기 전에 하드웨어 리소스가 부족할 것입니다. 문자열의 해시 코드는 매우 효율적이고 잘 테스트되었습니다.

업데이트나는 위의 것이 만족한다고 생각한다 작동 할 수있는 가장 간단한 것, 그러나 기존 문자열 해시 코드를 확장하려는 @sfussenegger 아이디어에 동의합니다.

문자열에 적합한 해시 코드를 갖는 것 외에도 구현에서 해시 코드를 다시 해싱하는 것을 고려할 수 있습니다. 스토리지를 다른 개발자가 사용하거나 다른 유형과 함께 사용하는 경우 키를 분산시키는 데 도움이 될 수 있습니다. 예를 들어, Java의 해시 맵은 두 길이의 전력 해시 테이블을 기반으로 하므로이 기능을 추가하여 더 낮은 비트가 충분히 분산되도록합니다.

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

CRC64 다항식을 사용하지 않겠습니까? 이들은 모든 비트가 결과 공간에 걸쳐 계산되고 퍼지도록 합리적으로 효율적이고 최적화되어 있습니다.

Google "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 프리미티브와 줄을 쓰고 바이트로 출력 할 수 있습니다. 포장 a BytearRayoutputStream 그것은 당신이 바이트 어레이에 쓸 수있게 해주 며, 이는 멋지게 통합됩니다. MessageDigest. 나열된 알고리즘에서 선택할 수 있습니다 여기.

드디어 Biginteger 출력 바이트를 사용하기 쉬운 번호로 바꿀 수 있습니다. MD5 및 SHA1 알고리즘은 둘 다 128 비트 해시를 생성하므로 64가 필요한 경우 잘릴 수 있습니다.

SHA1은 거의 모든 것을 해시해야하며 드물게 충돌해야합니다 (128 비트). 이것은 Java에서 작동하지만 어떻게 구현되었는지 잘 모르겠습니다. 실제로 상당히 빠를 수 있습니다. 그것은 내 구현의 여러 분야에서 작동합니다. DataOutputStream 그리고 당신은 가기 좋습니다. 반사와 주석으로도 할 수도 있습니다 (아마도 @HashComponent(order=1) 어떤 필드가 해시에 들어가서 순서대로 보여줍니다). 128 비트 변형이 있으며 CPU가 생각만큼 사용하지 않는다고 생각합니다.

나는 이와 같은 코드를 사용하여 거대한 데이터 세트 (아마도 수십억 개의 객체)에 대한 해시를 얻을 수 있도록 많은 백엔드 상점에서 그들을 보충 할 수있었습니다. 필요한 것은 무엇이든 작동해야합니다. 당신이 전화하고 싶을 수도 있다고 생각합니다. MessageDigest.getInstance() 한 번 clone() 그때부터 : IIRC는 복제가 훨씬 빠릅니다.

다른 32 비트 해시 코드를 얻으려면 문자열을 반전시킨 다음 두 가지를 결합합니다.

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

이것은 의사 코드입니다. 그만큼 String.reverse() 메소드는 존재하지 않으며 다른 방법으로 구현해야합니다.

오늘의 답변 (2018). Siphash.

여기는 대부분의 답변보다 훨씬 빠르며 모든 답변보다 훨씬 높은 품질이 될 것입니다.

구아바 도서관에는 하나가 있습니다. https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/hashing.html#siphash24--

당신은 보입니까? Apache Commons Lang?

그러나 64 비트 (및 128)에는 몇 가지 요령이 필요합니다. Joshua Bloch의 효과적인 Java에 제시된 규칙은 64 비트 해시를 쉽게 만들 수 있도록 도와줍니다 (int 대신 오래 사용). 128 비트의 경우 추가 해킹이 필요합니다 ...

면책 조항 :이 솔루션은 개별 자연어 단어를 효율적으로 해시하려는 경우 적용됩니다. 더 긴 텍스트를 해싱하거나 비 알파벳 문자를 포함하는 텍스트에 비효율적입니다.

나는 기능을 모르지만 여기에 도움이 될 수있는 아이디어가 있습니다.

  • 64 비트 중 52 개를 문자열에 존재하는 글자를 나타내는 데 전념하십시오. 예를 들어, 'a'가 존재한다면 'b'세트 비트에 대해 비트 [0]을 설정합니다. 1, 'A'세트 비트 [26]. 이렇게하면 정확히 동일한 문자 세트를 포함하는 텍스트 만 동일한 "서명"을 갖습니다.

그런 다음 나머지 12 비트를 사용하여 문자열 길이 (또는 모듈로 값)를 인코딩하여 충돌을 더 줄이거 나 기존 해싱 함수를 사용하여 12 비트 해시 코드를 생성 할 수 있습니다.

귀하의 입력이 텍스트 전용이라고 가정하면 이것이 충돌이 거의없고 계산하기에 저렴할 것이라고 상상할 수 있습니다 (O (n)). 지금까지 다른 솔루션과 달리이 접근법은 문제 영역을 고려하여 충돌을 줄입니다. - 프로그래밍 진주에 설명 된 아나그램 탐지기를 기반으로합니다 (참조 여기).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top