해쉬 collision

* 해쉬란? 주어진 키에 대하여 실제 레코드가 저장될 주소를 계산해 내는 것. N개의 키 집합에서 m개의 주소 집합으로의 사상이라고 이해해도 된다.

* 해쉬함수란? 해쉬값(해쉬-코드)을 생성하는 함수. 이 해쉬값은 키의 집합들을 (0~m-1)범위의 정수로 균등하게 사상시킨 것이다. API 측면에서는 키의 집합들을 해쉬테이블의 버켓에 사상시킨다.

* 해쉬함수의 역할: 키를 가지고 저장될 해시공간 상에서의 주소를 직접 계산하되, 해시공간에서 어느 한쪽에 집중되는 군집현상이 일어나지 않도록 하고 균등하게 분포할 수 있도록 저장해야 한다. 장점이라면 탐색시간이 O(1)로 짧다는것이고, 단점이라면 해시충돌과 해시공간에서 사용되지 않는 빈 공간이 많이 생긴다는 점이다.

* 해쉬테이블이란? 해쉬함수를 활용해 채운 도표에 해당한다고 이해해도 되며, 버켓이라는 m개(여기서 주소는 0~m-1이 된다)의 위치배열로 생각해도 된다. 구현하는 방법은 아래 그림처럼 배열형태로 사용할 수도 있다.

* 해쉬 충돌(collision)이란? 서로 다른 키에 대하여 동일한 주소를 계산해 내는 경우를 말한다.

- 이는 메모리 공간의 문제가 아니라 해쉬함수의 특성상(계산과정) 반드시 발생한다.

- 이를 보완하기 위한 다양한 방법들이 제시되어 있으며 공개 주소 방식(1개의 버켓에 1개의 키)과 비공개 주소 방식(1개의 버켓에 여러개의 키)으로 구분할 수 있다. 다음은 공개 주소 방식(선형탐색, 제곱탐색, 이중해시)에 대한 설명이다. 선형탐색은 해쉬함수가 생성한 주소에 이미 레코드가 점유하고 있는 경우 그 다음 빈곳을 찾는다. (현 주소 + 1) MOD m 으로 계산할 수 있다. 이러한 선형탐색의 경우에도 클러스터(군집) 현상이 발생한다. 이를 보완하기 위해 제곱탐색 방식도 있으나 여전히 클러스터 현상이 존재한다. 제곱탐색은 (현 주소 + i^2) MOD m 으로 계산할 수 있다(i ≥ 1). 현 주소에 1, 4, 9 등을 더하면서 빈곳을 찾는 방식이다. 이외에 이중해시(충돌 시 두번째로 서로 다른 성격의 해쉬함수를 사용) 방법도 있다. 비공개 주소 방식은 한 개의 버켓에 여러개의 키를 연결해서 저장한다. 이때 키는 나중에 삽입된 키를 맨 앞에 저장한다.

* 충돌을 일으키지 않고 한 영역에 집중되지 않도록 균일하게 대응시키는 해시함수의 선택은 어려운 문제이다.

* 완전해시함수: 충돌이 발생하지 않도록 모든 키들을 버켓에 완전히 분산시키는 해시함수

* 최소완전해시함수: 키에 대한 집합의 범위를 함수 유도과정에 포함시킨 해시함수

* 일반적으로 프로그래밍 언어에서 API로 제공하는 해쉬테이블은 키와 레코드를 쌍으로 연속적으로 저장할 수 있도록 구현한 자료구조이다.

[출처] 해쉬(hash, 해시)에 대한 기초 개념|작성자 네오 에이치