Hash

해시는 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 변화시켜 저장하는 과정입니다. 그리고 해시값을 구하는 과정에 사용하는 함수, 알고리즘을 해시함수라고 하죠.

해시함수란?

해시함수는 임의의 길이를 데이터로 입력받아 일정한 길이의 비트열로 반환시켜줍니다.

원래의 값이나 키를 색인하는데 사용되며, 그 값이 관련된 데이터가 검색될 때 마다 다시 사용됩니다. 즉 데이터의 효율적 관리를 목적으로 임의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수죠.

해시함수는 다음과 같이 여러 해시함수로 나뉠 수 있습니다.

1. 나눗셈법
   1. 해시함수 중 가장 간단한 방법으로 입력값을 테이블 크기로 나누고 그 나머지를 인덱스로 활용하는 방법입니다. 이때 소수를 테이블 크기로 활용하였을 때 가장 성능이 좋다고합니다.
2. 곱셈법
   1. 곱셈법은 다음과 같은 공식을 따릅니다.
   2. H(k) = (kA mod 1 ) * m
   3. A는 0과 1 사이의 실수이며 m은 랜덤값입니다.
3. Universal Hashing
   1. 해시함수를 여러개 만들고 이 해시함수의 집합에서 무작위로 해시함수를 선택하여 값을 만드는 방법입니다.
   2. 임의의 키 값을 임의의 해시값에 매핑할 확률을 1/m으로 만드는 것이 목적입니다.