해시 함수 및 해시 코드

일반적인 해시 함수는 먼저 검색 키를 해시 코드라는 정수 값으로 변환한 다음 해시 코드를 해시 테이블에 대한 인덱스로 압축합니다. Java의 루트 클래스 Object에는 정수 해시 코드를 반환하는 hashCode 메서드가 있습니다. 기본적으로 이 메서드는 개체의 메모리 주소를 반환합니다. hashCode 메소드의 일반 계약은 다음과 같습니다.

1. 두 개의 동일한 객체가 동일한 해시 코드를 반환하도록 equals 메서드를 재정의할 때마다 hashCode 메서드를 재정의해야 합니다.
2. 프로그램 실행 중에 hashCode 메소드를 여러 번 호출하면 객체의 데이터가 변경되지 않는 한 동일한 정수가 반환됩니다.
3. 두 개의 서로 다른 객체가 동일한 해시 코드를 가질 수 있지만 이러한 경우가 너무 많이 발생하지 않도록 hashCode 메소드를 구현해야 합니다.

기본 유형의 해시 코드

byte, short, int 및 char 유형의 검색 키의 경우 간단히 int로 캐스팅하세요. . 따라서 이러한 유형 중 하나의 서로 다른 두 검색 키는 서로 다른 해시 코드를 갖게 됩니다.

float 유형의 검색 키의 경우 Float.floatToIntBits(key)를 해시 코드로 사용하세요. floatToIntBits(float f)는 비트 표현이 부동 숫자 f의 비트 표현과 동일한 int 값을 반환합니다. 따라서 float 유형의 서로 다른 두 검색 키는 서로 다른 해시 코드를 갖게 됩니다.

long 유형의 검색 키의 경우 단순히 int로 캐스팅하는 것은 좋은 선택이 아닙니다. 처음 32비트만 다른 모든 키에 동일한 해시 코드. 처음 32비트를 고려하려면 64비트를 두 부분으로 나누고 배타적 논리합 연산을 수행하여 두 부분을 결합합니다. 이 과정을 접기라고 합니다. long 키의 해시 코드는

입니다.

int hashCode = (int)(key ^ (key >> 32));

>>은 비트 32 위치를 오른쪽으로 이동하는 오른쪽 시프트 연산자입니다. 예를 들어 1010110 >> 2는 0010101을 산출합니다. ^는 비트 배타적 논리합 연산자입니다. 이는 이진 피연산자의 두 해당 비트에 대해 작동합니다. 예를 들어 1010110 ^ 0110111은 1100001을 산출합니다.

double 유형의 검색 키의 경우 먼저 Double.doubleToLongBits 메서드를 사용하여 long 값으로 변환한 다음 다음과 같이 접기를 수행합니다. 다음:

긴 비트 = Double.doubleToLongBits(key);
int hashCode = (int)(비트 ^ (비트 >> 32));

문자열의 해시 코드

검색 키는 문자열인 경우가 많으므로 문자열에 적합한 해시 함수를 설계하는 것이 중요합니다. 직관적인 접근 방식은 모든 문자의 유니코드를 문자열의 해시 코드로 합산하는 것입니다. 이 접근 방식은 애플리케이션의 두 검색 키에 동일한 문자가 포함되어 있지 않은 경우 작동할 수 있지만 tod 및 dot와 같이 검색 키에 동일한 문자가 포함되어 있으면 충돌이 많이 발생합니다. .

더 나은 접근 방식은 문자 위치를 고려하는 해시 코드를 생성하는 것입니다. 구체적으로 해시 코드를

s0*b(n - 1) + s1*b(n - 2) + c + sn-1

si는 s.charAt(i)입니다. 이 표현식은 일부 양수 b에 대한 다항식이므로 다항식 해시 코드라고 합니다. 다항식 평가를 위한 Horner의 규칙(사례 연구: 16진수를 10진수로 변환 참조)을 사용하면 다음과 같이 해시 코드를 효율적으로 계산할 수 있습니다.

(...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1

이 계산은 긴 문자열에 대해 오버플로를 일으킬 수 있지만 Java에서는 산술 오버플로가 무시됩니다. 충돌을 최소화하려면 적절한 값 b를 선택해야 합니다. 실험에 따르면 b에 대한 좋은 선택은 31, 33, 37, 39 및 41입니다. String 클래스에서 hashCode는 b가 31.

해시 코드 압축

키의 해시 코드는 해시 테이블 인덱스 범위를 벗어나는 큰 정수일 수 있으므로 인덱스 범위에 맞게 축소해야 합니다. 해시 테이블의 인덱스가

0과 N-1 사이에 있다고 가정합니다. 정수를 0과 N-1 사이로 확장하는 가장 일반적인 방법은 을 사용하는 것입니다.

h(hashCode) = hashCode % N

인덱스가 균등하게 분산되도록 하려면 2보다 큰 소수가 되도록 N을 선택하세요.

이상적으로는 N에 소수를 선택해야 합니다. 그러나 큰 소수를 찾는 것은 시간이 많이 걸린다. java.util.HashMap에 대한 Java API 구현에서 N은 2의 거듭제곱 값으로 설정됩니다. 이 선택에는 타당한 이유가 있습니다. N이 2의 거듭제곱 값일 때,

h(hashCode) = hashCode % N

동일합니다

h(hashCode) = hashCode & (N – 1)

앰퍼샌드 &는 비트 AND 연산자입니다. 두 해당 비트의 AND는 두 비트가 모두 1인 경우 1을 생성합니다. 예를 들어 N = 4 및 hashCode = 11, 11 % 4 = 3이라고 가정하면 01011 & 00011 = 11. & 연산자는 % 연산자보다 훨씬 빠르게 수행할 수 있습니다.

해싱이 균등하게 분산되도록 하기 위해

java.util.HashMap 구현 시 기본 해시 함수와 함께 보충 해시 함수도 사용됩니다. 이 함수는 다음과 같이 정의됩니다.

private static int 보충 해시(int h) {

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

^ 및 >>>은 비트 배타적 OR 및 부호 없는 오른쪽 시프트 연산입니다. 비트 연산은 곱셈, 나눗셈, 나머지 연산보다 훨씬 빠릅니다. 가능할 때마다 이러한 연산을 비트 연산으로 바꿔야 합니다.

완전한 해시 함수는 다음과 같이 정의됩니다.

h(hashCode) = 보충Hash(hashCode) % N

이것도 마찬가지입니다

h(hashCode) = 보충Hash(hashCode) & (N – 1)

N은 2의 거듭제곱 값이기 때문입니다.

위 내용은 해시 함수 및 해시 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!