수색…
해시 함수 소개
해시 함수 h()
는 임의의 크기의 데이터 x ∈ X
를 고정 된 크기의 값 y ∈ Y
매핑 한 임의의 함수입니다. y = h(x)
. 좋은 해시 함수에는 다음과 같은 제한이 있습니다.
해시 함수는 균일 한 분포를 좋아합니다.
해시 함수는 결정적입니다.
h(x)
는 주어진x
대해 항상 같은 값을 반환해야합니다.빠른 계산 (런타임 O (1) 있음)
일반적으로 해시 함수의 크기가 입력 데이터의 크기보다 작은 경우 : |y| < |x|
. 해시 함수는 가역적이지 못하며 ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)
충돌 가능성이있다. 즉 ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)
. X
는 유한 또는 무한 집합 일 수 있으며 Y
는 유한 집합입니다.
해시 함수는 소프트웨어 엔지니어링, 암호화, 데이터베이스, 네트워크, 기계 학습 등 컴퓨터 과학 분야에서 많이 사용됩니다. 서로 다른 도메인 별 속성을 가진 다양한 유형의 해시 함수가 있습니다.
종종 해시는 정수 값입니다. 해시 계산을위한 프로그래밍 언어에는 특별한 방법이 있습니다. 예를 들어, C#
GetHashCode()
메서드는 모든 유형에 대해 Int32
값 (32 비트 정수)을 반환합니다. Java
모든 클래스는 int
를 반환하는 hashCode()
메서드를 제공합니다. 각 데이터 유형에는 자체 또는 사용자 정의 구현이 있습니다.
해시 메소드
해시 함수를 결정하는 데는 여러 가지 방법이 있습니다. 일반성을 잃지 않고, x ∈ X = {z ∈ ℤ: z ≥ 0}
은 양의 정수이다. 흔히 m
은 소수 (2의 정확한 지수에 너무 가깝지 않음)입니다.
방법 | 해시 기능 |
---|---|
분할 방법 | h(x) = x mod m |
곱셈법 | h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1} |
해시 테이블
해시 테이블에서 슬롯 배열로 색인을 계산하는 데 사용되는 해시 함수입니다. 해시 테이블은 사전 (키 - 값 구조)을 구현하기위한 데이터 구조입니다. 좋은 구현 된 해시 테이블에는 다음 작업을위한 O (1) 시간이 있습니다 : 키로 데이터를 삽입, 검색 및 삭제하십시오. 하나 이상의 키가 동일한 슬롯에 해시 될 수 있습니다. 충돌을 해결하는 데는 두 가지 방법이 있습니다.
연결 : 연결된 목록은 슬롯에 동일한 해시 값을 가진 요소를 저장하는 데 사용됩니다.
오픈 어드레싱 : 0 또는 하나의 요소가 각 슬롯에 저장 됨
다음 방법은 개방형 어드레싱에 필요한 프로브 시퀀스를 계산하는 데 사용됩니다
방법 | 공식 |
---|---|
선형 프로빙 | h(x, i) = (h'(x) + i) mod m |
이차 탐침 | h(x, i) = (h'(x) + c1*i + c2*i^2) mod m |
더블 해싱 | h(x, i) = (h1(x) + i*h2(x)) mod m |
여기서 i ∈ {0, 1, ..., m-1}
, h'(x), h1(x), h2(x)
는 보조 해시 함수이고, c1, c2
는 양의 보조 상수이다.
예제들
x ∈ U{1, 1000}, h = x mod m
. 다음 표는 프라임이 아닌 프라임의 경우 해시 값을 보여줍니다. 굵게 표시된 텍스트는 동일한 해시 값을 나타냅니다.
엑스 | m = 100 (소수가 아님) | m = 101 (소수) |
---|---|---|
723 | 23 | 16 |
103 | 삼 | 2 |
738 | 38 세 | 31 |
292 | 92 | 90 |
61 | 61 | 61 |
87 | 87 | 87 |
995 | 95 | 86 |
549 | 49 | 44 |
991 | 91 | 82 |
757 | 57 번 | 50 개 |
920 | 20 | 11 |
626 | 26 세 | 20 |
557 | 57 번 | 52 |
831 | 31 | 23 |
619 | 19 | 13 |
모래밭
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개.
C #의 일반적인 유형에 대한 해시 코드
System
네임 스페이스의 기본 제공 C # 유형 에 대해 GetHashCode()
메서드에서 생성 된 해시 코드는 아래와 같습니다.
부울
값이 참이면 1, 그렇지 않으면 0입니다.
Byte , UInt16 , Int32 , UInt32 , Single
값 (필요한 경우 Int32에 캐스트).
SByte
((int)m_value ^ (int)m_value << 8);
숯
(int)m_value ^ ((int)m_value << 16);
Int16
((int)((ushort)m_value) ^ (((int)m_value) << 16));
Int64 , Double
64 비트의 하위 32 비트와 상위 32 비트 사이의 XOR
(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));
UInt64 , DateTime , TimeSpan
((int)m_value) ^ (int)(m_value >> 32);
소수
((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];
목적
RuntimeHelpers.GetHashCode(this);
기본 구현은 sync 블록 인덱스를 사용 합니다 .
끈
해시 코드 계산은 플랫폼 유형 (Win32 또는 Win64), 임의 해싱 문자열 해시 사용, 디버그 / 릴리스 모드에 따라 다릅니다. Win64 플랫폼의 경우 :
int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
hash1 = ((hash1 << 5) + hash1) ^ c;
c = s[1];
if (c == 0)
break;
hash2 = ((hash2 << 5) + hash2) ^ c;
s += 2;
}
return hash1 + (hash2 * 1566083941);
ValueType
첫 번째 비 정적 필드는 찾아서 해시 코드를 얻습니다. 유형에 비 정적 필드가없는 경우 유형의 해시 코드가 반환됩니다. 정적 멤버의 해시 코드는 해당 멤버가 원래 유형과 동일한 유형 인 경우 계산이 무한 루프로 끝나기 때문에 수행 할 수 없습니다.
Nullable <T>
return hasValue ? value.GetHashCode() : 0;
정렬
int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}