algorithm
해시 함수

해시 함수 소개

해시 함수 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의 정확한 지수에 너무 가깝지 않음)입니다.

해시 테이블

해시 테이블에서 슬롯 배열로 색인을 계산하는 데 사용되는 해시 함수입니다. 해시 테이블은 사전 (키 - 값 구조)을 구현하기위한 데이터 구조입니다. 좋은 구현 된 해시 테이블에는 다음 작업을위한 O (1) 시간이 있습니다 : 키로 데이터를 삽입, 검색 및 삭제하십시오. 하나 이상의 키가 동일한 슬롯에 해시 될 수 있습니다. 충돌을 해결하는 데는 두 가지 방법이 있습니다.

1. 연결 : 연결된 목록은 슬롯에 동일한 해시 값을 가진 요소를 저장하는 데 사용됩니다.

2. 오픈 어드레싱 : 0 또는 하나의 요소가 각 슬롯에 저장 됨

다음 방법은 개방형 어드레싱에 필요한 프로브 시퀀스를 계산하는 데 사용됩니다

여기서 i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) 는 보조 해시 함수이고, c1, c2 는 양의 보조 상수이다.

예제들

x ∈ U{1, 1000}, h = x mod m . 다음 표는 프라임이 아닌 프라임의 경우 해시 값을 보여줍니다. 굵게 표시된 텍스트는 동일한 해시 값을 나타냅니다.

모래밭

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개.

• 해시 테이블 개요

• Wolfram MathWorld - 해시 함수

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

참고 문헌

• GitHub .Net 핵심 CLR