[C++] 해시 (Hash)

[C++] 해시 (Hash)

---

해시 (Hash)

해시는 해시함수의 결과물이며, 저장소에서 값과 매칭되어 저장되며 해시테이블의 구성 요소이다.

해시 연관 컨테이너

▹ 이진 트리가 아닌 해시 테이블로 구성되어있다.

▹ 올바른 키와 올바른 해시 테이블 크기가 만족된다면 요소를 검색하는 속도는 O(N)에서 O(1)로 단축할 수 있다.

해시 테이블 (Hash Table)

출처 : 위키백과 - 해시테이블

해시 테이블은 연관 컨테이너 구조를 이용하여 키(key)에 값(Value)을 저장하는 자료 구조이다.

키, 해시 함수(Hash Function), 해시, 값, 저장소(Bucket)로 이루어져 있으며 키는 해시함수를 통해 해시로 변경되며 해시는 값과 매칭되어 저장소에 저장이 된다.

해시 함수 (Hash Function)

키(key)를 해시(Hash)로 바꿔주는 역할을 하며 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 효율적인 저장소 운영을 하게 해준다. 하지만 서로 다른 키가 같은 해시가 되는 경우 해시 충돌(Hash Collision)이 발생할 수 있다.

해시 충돌과 그 해결 방법

해시충돌은 다른 키가 같은 해시가 되는 경우를 의미한다. 즉, 1인 1실인 방에 2명이 들어갈려고 하는 경우인 것이다.

이를 해결하기 위한 방법은 Chaining과 Open Addressing(개방주소법)이 있다. 

Chaining

자료 저장 시 저장소에서 충돌이 일어나면 링크드 리스트 자료구조를 이용하여 기존값 다음에 해당값을 연결해주는 것이다. 이 방법은 한정되고 제한적인 저장소에서 효율적이고 해시 함수를 적게사용하며 상대적으로 적은 메모리를 사용하는 장점이 있다. 하지만 한 저장소에 자료들이 몰리게 된다면 검색효율이 떨어지며 외부 저장 공간을 사용하여 이 공간 작업을 해줘야한다는 단점을 가지고 있다.

개방 주소법 (Open Addressing)

자료 저장 시 저장소가 비어있지 않다면 다른 비어있는 저장소(해시)를 찾아 저장해주는 방법이다. 이 방법을 사용하면 1개의 해시와 1개의 값이 매칭되는 형태가 된다. 다른 비어있는 해시를 찾는 방법은 선형 탐색, 제곱 탐색, 이중 해시가 있다.

선형 탐색 (Linear Probing) : 다음이나 n개를 이동하여 비어있는 해시를 찾고 데이터를 저장하는 방법이다.
제곱 탐색 (Quadratic Probing) : 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장하는 방법이다.
이중 해시 (Double Hashing) : 다른 해시 함수를 한번 더 적용하여 해시에 데이터를 저장하는 방법이다.

또 다른 외부 저장 공간이 필요 없으며 이 공간을 위한 작업을 할 필요가 없다는 장점을 가지고 있다. 하지만 해시 함수의 성능에 전체 해시 테이블 성능이 좌지우지될 수 있는 단점이 있다.

---

해시 테이블은 적절한 함수를 사용한다면 O(1)의 상당히 빠른 속도를 가진 검색을 할 수 있는 컨테이너이다. 키를 통해서 빠르게 값을 찾을 수 있는 장점을 이용하여 게임에서 플레이어의 ID를 통해 플레이어 정보를 조회하는 기능을 구현하면 좋을 것 같다.