해싱 (Hashing)

#개념

해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다.

이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다.

이 값은 해시 코드, 해시 섬(sum), 체크섬 등으로도 불린다.

 

대표적으로 해시 테이블, 해시 셋 등에서 유용하게 사용된다.

위 자료구조들은 인덱스에 해시값을 사용하는 자료 구조로, 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다.

 

해시를 사용하다 보면 동일한 해시 코드가 얻어지는 경우가 있는데 이를 해시 충돌이라 하며 해시 함수의 알고리즘이 뛰어날수록 충돌 확률이 낮다.

해시 충돌의 대표적인 대안으로써 다음과 같은 방법들이 있다.

 

@Chaining

해시 충돌이 일어날 경우 해당 해시 코드로 최초 저장된 데이터를 시작으로 연결 리스트의 형태를 취한다.

최악의 경우 (모든 데이터의 해쉬 코드가 일치하여 한 인덱스에 저장되었을 경우)엔 연결 리스트의 탐색 시간과 동일한 선형 시간을 가지게 된다.

 

@Linear Probing

Open Addressing의 대표적인 방식이며 key값으로 인덱스를 계산할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 다음으로 이동한 후에도 충돌이 발생했다면  다시 바로 다음 인덱스에 저장한다. 즉, 충돌이 일어나지 않을 때까지 다음 인덱스로 이동을 해가며 빈 공간을 찾으면 그 위치에 저장한다.

 

@Resizing

Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 버킷이 차게 되면 확장해야 한다. 또한 Chaining인 경우에도 버킷이 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 버킷을 늘려줘야 한다. 이를 Resizing이라고 한다. 기존 테이블보다 크기를 늘린 테이블을 생성한 뒤 기존 데이터를 다시 해시하여 정렬한다.