해쉬 테이블의 필요성
모든 원소를 선형으로 검토하여 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요된다. 특히 저장된 데이터가 많을 수록 검색 시간은 크게 증가하게 된다.
예를 들어 사전에서 단어를 찾는다고 가정한다면 특정 단어의 뜻을 찾기 위해서는 수십만개의 단어를 차례대로 비교하면서 찾는 단어가 나타나거나 사전의 맨 마지막에 도달하면 종료되게 된다. 이 방법은 O(N)의 시간 복잡도를 갖기 때문에 매우 느리다.
선형 검색의 문제점은 O(logN)의 시간복잡도를 갖는 높이-균형 트리에 데이터를 저장하는 방법을 생각해볼 수 있다. 이러한 경우 시간 복잡도는 O(N)에 비해 훨씬 빨리지게 된다. 하지만 수백, 수천만 이상의 데이터가 저장된 경우 이러한 방식 역시 빠르다고 할 수 없다.
이러한 문제를 해결하기 위해 해시 테이블이 등장하였다. 해시테이블의 핵심은 해싱이다.
해싱이란 각각의 데이터를 고유한 숫자값으로 표현하고 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 방식이다.
그리고 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해쉬 함수라고 한다.
해쉬 함수
해쉬 함수는 해쉬 테이블을 구성하기 위한 핵심적인 개념이다. 해쉬 함수의 기본적인 개념은 데이터를 원하는 범위의 값으로 매핑하는 것이다.
해쉬 함수를 이용해 데이터를 원하는 형태로 매핑하고 이를 해쉬 테이블에 저장하면 특정 데이터를 해쉬 함수를 통해 변환하여 인덱스 값으로 해쉬 테이블에서 값을 찾을 수 있기 때문에 O(1)의 시간복잡도를 갖게된다. 이는 O(N)과 비교하면 매우 빠른 검색 속도이다.
충돌
가장 간단한 해쉬 함수는 데이터를 특정 정수로 나누는 나머지를 반환하는 모듈로 함수이다.
만약 이 함수에 어떤 숫자 x를 입력으로 주면 x%n 연산의 결과가 반환되고 이 값을 배열의 x%n 위치에 삽입한다.
하지만 이러한 함수는 서로 다른 데이터에 대해 같은 해시 값을 반환할 수 있다는 문제가 존재한다.
예를 들어 9%7과 16%7은 모두 해쉬 값으로 2를 반환한다. 그렇기 때문에 해쉬 테이블의 2번 인덱스에 저장된 데이터가 9인지 16인지 알 수 없다. 이러한 문제를 충돌이라고 한다.
즉 충돌이란 해쉬 함수가 서로 다른 키에 대해 같은 해쉬 값을 반환함으로써 다수의 키가 같은 값을 갖게 되는 현상을 말한다.
충돌 해결 방법
체이닝
위에서 설명한 해쉬 테이블에서는 하나의 키 값에 대해 하나의 데이터만 저장할 수 있었다. 따라서 만약 특정 해쉬 값에 이미 원소가 존재한다면 새로운 값과 이전 값 중 하나를 버려야만 한다.
체이닝은 이러한 문제를 해결하기 위해 특정 위치에 하나의 키를 저장하는 것이 아닌 하나의 연결리스트를 저장한다.
따라서 새로 삽입된 키에 의해 충돌이 발생한다면 리스트의 맨 뒤에 새로운 키를 추가한다.
체이닝 기법을 사용하게 된다면 새로운 원소를 삽입하는 연산에 대해서는 O(1)의 시간복잡도를 갖는다. 하지만 데이터를 탐색하는 작업에 대해서는 연결 리스트에서 선형 검색을 수행하는 것과 같기 때문에 O(N)의 시간 복잡도를 갖는다는 문제점이 있다.
열린 주소 지정
열린 주소 지정은 체이닝처럼 해쉬 테이블에 추가적인 연결리스트를 삽입하는 것이 아닌 모든 원소를 해쉬 테이블 내에 저장한다.
이 방법의 핵심은 특정 해쉬 값에 값이 이미 존재한다면 테이블의 다른 비어 있는 위치를 찾는다.
-
선형 탐색
선형 탐색은 특정 해쉬 값에서 충돌이 발생한다면 해당 위치에서 하나씩 다음 셀 위치로 이동하면서 셀이 비어있는지 확인하고 비어있다면 원소를 삽입하는 방법이다. -
이차함수 탐색
뻐꾸기 해싱
뻐꾸기는 다른 새의 둥지에서 알을 낳는다. 이후에 부화된 뻐꾸기 새끼가 다른 새의 알이나 새끼들을 둥지에서 밀어내어 깨버린다. 다른 새의 어미는 그런 줄도 모르고 뻐꾸기 새끼를 품고 자기 새끼처럼 키운다. 이러한 조류의 습성을 탁란이라고 하는데 이를 모방한 해싱 방법이다.
뻐꾸기 해싱은 2개의 해시 함수와 해시 테이블이 필요하다. 두 개의 해시 테이블을 htable과 dtable이라고 정의하겠다. 키가 처음 삽입되는 테이블을 htable로 정의한다. 키의 위치가 htable에 중복되었을 경우, 있던 값을 밀어내기 위한 또 다른 테이블을 dtable이라 정의한다. 각각의 테이블에 값이 입력될 때 사용되는 해시 함수는 다른 해시 함수이다.
최대 2회의 해시함수 계산으로 각각의 테이블 원소를 찾아 각 연산을 처리한다. 모든 경우에 대해서 탐색과 삭제를 O(1) 시간에 보장할 수 있는 해시함수는 아직 존재하지 않지만 삽입의 경우 뻐꾸기 해싱은 높은 확률로 O(1) 시간에 수행이 가능하다.
- 처음에는 일반 해시함수들과 똑같이 동작을 한다. 들어온 키를 정해진 해시함수를 거쳐 해시 테이블에 위치시킨다.
계속해서 hash함수를 통해 H_table을 채워나간다.
- 키를 채우던 중, 내가 위치해야할 자리에 이미 h_table이 차 있으면, 원래 있던 키인 5는 d hash 함수를 이용해 다시 한 번 위치를 정하여 d_table에 위치시키고, 방금 들어온 3은 h_table에 위치시킨다. 원래 h_table에 있던 키를 d_table로 밀어내는 과정이다. (뻐꾸기 해싱)
- 내가(8) 위치해야 할 자리에 이미 table이 차 있어 원래 있던 키(1)를 밀어내어 dhash을 통해 d_table로 보냈다. 그러나 d_table의 자리마저 다른 키(6)가 위치해 있는 상황이라면? 그 다른 키(6)마저 밀어내고 원래 있던 키는 d_table을 차지하고, 다른 키(6)는 다시 hash 함수를 통해 h_table에 위치하게 된다. (재해싱)
이와 같은 과정을 모두가 자리에 위치할 때까지 반복해주는 것이다.
