Hash, Hash function는 무엇일까? (해시 값 및 해시 함수 설명)

우선 위키피디아에 검색하면 다음처럼 설명한다.

 

해시 함수란, '임의의 길이의 데이터'를 '고정된 길이의 데이터'로 매핑하는 함수이다.

이렇게 매핑된 함수의 출력을 '해시'라고 부른다.

이러한 해시 함수는, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다.

 

즉, 예를 들어 32bit, 64bit, 128bit 등 임의의 N-bit 데이터를 갖고있을때, 이 데이터를 16bit와 같은 적은 bit의 데이터로 매핑하는 방법에 대한 설명이다. 

 

64bit 데이터를 16bit의 데이터로 변환하는 간단한 해시 함수는 다음과 같다.

 

 

 

int16 hashfunction( int64 i )
{
    int16 hash = (int16)(i & 0xFFFF);
    hash ^= (int16)((i >> 16) & 0xFFFF);
    hash ^= (int16)((i >> 32) & 0xFFFF);
    hash ^= (int16)((i >> 48) & 0xFFFF);

    return hash;
}

 

 

 

해시는,

1. 두 해시값이 다르다면, 원래 데이터도 달라야 한다.

2. 이상적인 해시함수는 입력된 데이터를 'random-like manner'의 순서를 갖는 정수로 매핑할 수 있어야 한다. 즉, 입력 형태에 어떠한 패턴이 있더라도, 출력 해시는 패턴을 갖으면 안된다는 것이다. (이상적인 해시 함수의 경우)

 

이렇게 얻은 해시값을 결합시키는(combining hash values) 방법도 중요한데, 

해시값 A, B, C, D, E,... 가 있다고 한다면 이를 단일 해시값 Z로 결합시켜 그 데이터의 크기를 굉장히 많이 줄일 수 있다.

 

물론, 결합시키는 과정에서 많은 데이터가 소실되며 결과적으로 해시값을 암호나 파일의 무결성 확인등에 사용하는 이유이기도 하다.

 

 

 

간단하여 널리 사용되는 방법은 위의 코드에서와 같이, 두 해시값의 각 비트를 XOR 연산 시키는 것이다.

 

(ex). 1000_0001_0001_1001 ^(XOR) 1000_0011_0111_0000 = 0000_0010_0110_1001

 

이 XOR 연산이 OR, AND등의 연산보다 해시 결합에 적합하다고 판단되는 이유를 설명하자면 다음과 같은데,

and연산과 or연산의 결과는 아래 표와 같이, 0과 1의 비율이 75%와 25%씩 번갈아 나오는것을 알 수 있다. 하지만 xor연산의 경우 50%와 50%의 비율을 갖도록 출력되기 때문에, uniform probability distribution을 갖는 입력들에 대해 해시값으로써 더 적합한 결과를 갖게 되는 것이다. 

 

하지만, 이 xor 함수또한 많은 문제점을 갖고있고, 이상적인 combining 방법은 아니다. 

그 이유는.. 다음번에 정리해봐야겠다.

 

 

해시를 사용할일이 생겨 급하게 정리해보았는데, 생각보다 공부할게 많은 분야인것같다.

추후 더 많은 시간을 들여 공부해봐야 할 것 같다.

 

출처1: https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

해시 함수 - 위키백과, 우리 모두의 백과사전

출처2: https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html

Hash Functions

출처3: https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes

Why is XOR the default way to combine hashes?