Hash

C++의 map 자료구조에 대해 공부하다 원리가 Hash임을 알게 되었고, 원리를 정확히 알고 쓰자는 생각으로 짧게 정리해보려 한다.

 

< Hash 란? >

원소의 값에 의해 원소가 저장되는 위치가 결정되는 자료구조.

검색, 삽입, 삭제 등의 연산을 평균적으로 상수 시간에 할 수 있음. O(1)

 

해싱(Hashing) - 매핑의 전체 과정

키(Key) - 매핑 전 원래 데이터의 값

해시함수(Hash Function) - 임의의 길이의 데이터를 특정 길이의 데이터로 변환하는 함수

해시값(Hash Value) - 매핑 후 데이터의 값

 

< 해시 충돌 >

해시함수를 통해 해시값을 할당할 때, 중복되는 인덱스값을 사용하게 되면 해시충돌이 일어남.

 

해결 방법 1 - 체이닝(Chaining)

같은 인덱스로 해싱되는 노드들을 연결리스트(Linked List)로 관리. 노드의 수가 많아지면 트리(Tree)로 더 효율적으로 관리할 수 있음.

 

해결 방법 2 - 개방 주소(Open Addressing)

개방 주소 기법은 또 여러가지 기법들로 나눌 수 있음.

1. 선형 조사

2. 이차원 조사

3. 이중 해싱

선형 조사를 예로 들면 해시충돌이 일어날 때 비어있는 인덱스를 찾아 데이터를 할당하는 기법임.

 

결국, 체이닝과 개방 주소 기법들의 차이점은 인덱스를 공유하느냐 하지 않느냐의 차이로 정리 가능할 듯.

 

이렇듯 해시충돌을 해결하는 기법들이 있으나, 가장 좋은 것은 애초에 충돌이 일어나지 않게 하는 것. 따라서 이 부분에서 해시 함수의 기능성이 요구됨.