Data Structure in C++ - Hash

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다.

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 일곱 번째 순서는 Hash Table이다. 

hash table은 각 data값이 key를 가지고 있는 자료구조이다. 우리가 특정 키로 특정 자물쇠를 바로 여는 것과 비슷한 자료구조이다.  키만 가지고 있다면 별도의 탐색과정 없이 효율적으로 데이터를 찾을 수 있고 이는 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적이다. 

사실 배열도 일종의 hash라고 볼 수 있다. 각 인덱스에 대칭되는 값들을 배열이 가지고 있다. 그렇다면 배열이 있는데 우리는 왜 별도의 hash라는 것을 사용할까? 

일반적으로 배열에서 사용하는 방식인 Direct Addressing은 table에 저장할 떄 키와 값을 일대일 매핑하는 방식이다. 배열에서 key는 index가 될 것이고, value는 그 배열 index의 값이 될 것이다. 하지만 키-값 쌍이 매우 많은 경우 이러한 Direct Addressing 방법에 문제가 있다. 만약 key 1개가 엄청나게 크다면 그 값을 위한 필요 없는 배열이 늘어날 것이고, table은 해당 값들을 저장하기 위해 매우 거대해질 것이다. 즉 이는 일반적인 컴퓨터에서 사용할 수 있는 메모리를 고려할 때 비 실용적이거나, 만약 표현 범위를 넘어간다면 저장이 불가능할 수 도 있다. 

이를 해결할 수 있는 자료구조가 바로 hash인 것이다. 

 

Hash Function

hash 함수는 특정 key 값이 주어졌을 때 다른 key값을 반환해주는 특수한 함수를 의미한다. 이를 통해 위에서 언급한 Direct Addressing의 문제를 해결할 수 있다.

Direce Accessing같은 경우 key값이 k인 value는 slot k에 저장이 된다. 하지만 hash 함수를 사용한다면 key값 k가 주어졌을 때 이 값이 적절히 변환되어 다른 key로 반환이 된다.  주어진 특정 key를 통해 hash 함수로 계산된 값들은 hash 값 이라고 하는데, 이는 table의 key 값을 나타내는 역할을 한다. 

아래는 가장 일반적인 hash 함수이다. 

vector<int> table(256);
int hash_funtion(int key) { return key % table.size(); }

key값을 table의 size로 나눈 것인데, 이렇게 하면 key값이 table의 size보다 커도, 해당 table안에 key-value 쌍으로 mapping 할 수 있다. 

그렇다면 key값이 2인경우와 258인 경우 동일한 hash값이 나올 텐데, 이를 colision이 일어났다 혹은 충돌이 일어났다고 명명한다. 이런 경우에 해당 key값에 뒤로 링크드리스트로 연결하는 chaining 방법과, 그다음 테이블에 저장하는 open addressing 등 여러 방법이 있다. 해시는 주로 데이터베이스의 indexing이나, associative arrays의 구현 혹은 set 자료구조의 구현 등에 사용이 된다. 

해시에 대한 대략적인 설명은 여기까지 하고 구현을 살펴보자. 

 

구현부분은 현재 수정 중입니다.