해시 테이블: 데이터 저장의 효율화
해시 테이블
데이터를 저장하고 검색하는 방법은 여러 가지가 있지만, 그 중에서도 해시 테이블은 탁월한 속도를 자랑하는 자료 구조이다. 마치 도서관의 책처럼, 데이터를 특정 키(key) 값으로 분류하여 저장하고, 필요할 때 키 값만으로 빠르게 데이터를 찾아낼 수 있다. 이러한 해시 테이블은 데이터베이스, 캐싱, 컴파일러 등 다양한 분야에서 널리 활용되고 있다. 자료구조에서 다룬 바 있지만, 이번에는 알고리즘의 관점에서 보다 자세히 알아보고자 한다.
Direct addressing: key와 index 1대1 대응
해시 테이블을 구현하는 가장 간단한 방법은 직접 주소 지정 방식(direct addressing)이다. 이 방식은 키 값을 배열의 인덱스로 직접 사용하여 데이터를 저장한다. 예를 들어, 학생 번호를 키 값으로 사용하는 경우, 각 학생 번호에 해당하는 배열 요소에 학생 정보를 저장할 수 있다.
하지만 이 방식은 키 값의 범위가 매우 크거나 키 값이 균등하게 분포하지 않을 경우, 메모리 공간을 낭비하게 되는 단점이 있다. 만약 학생 번호가 1부터 100,000까지 존재하지만 실제로 저장된 학생 정보는 100개뿐이라면, 99,900개의 배열 요소는 빈 공간으로 남게 된다.
Direct addressing : worst case |
해시 함수: 키 값을 슬롯에 매핑
직접 주소 지정 방식의 단점을 해결하기 위해 해시 함수(hash function)를 사용한다. 해시 함수는 임의의 키 값을 입력으로 받아 해시 테이블의 슬롯(slot)에 해당하는 인덱스를 출력하는 함수이다. 즉, 해시 함수는 키 값을 해시 테이블의 특정 위치에 매핑하는 역할을 한다.
해시 함수는 다양한 종류가 있으며, 좋은 해시 함수는 키 값을 균등하게 분포시켜 충돌(collision)을 최소화하는 특징을 갖는다. 충돌이란 서로 다른 키 값이 해시 함수에 의해 같은 슬롯에 매핑되는 현상을 말한다.
hash function |
체이닝: 충돌(collision) 해결을 위한 연결 리스트
충돌을 처리하는 방법에는 여러 가지가 있으며, 그 중 하나가 체이닝(chaining)이다. 체이닝은 각 슬롯에 연결 리스트를 사용하여 충돌된 키들을 저장하는 방식이다. 즉, 같은 슬롯에 매핑되는 키 값들은 해당 슬롯의 linked list에 순차적으로 저장된다.
chaining |
예를 들어, "apple"과 "banana"라는 두 개의 키 값이 해시 함수에 의해 같은 슬롯에 매핑되었다면, 해당 슬롯의 연결 리스트에는 "apple"과 "banana"가 순차적으로 저장된다.
체이닝의 장단점
체이닝 방식은 구현이 간단하고 메모리 낭비가 적다는 장점이 있다. 하지만 최악의 경우, 모든 키 값이 같은 슬롯에 매핑되어 연결 리스트의 길이가 매우 길어질 수 있다. 이 경우 검색 연산에 O(n) 시간이 소요될 수 있으며, 해시 테이블의 성능을 저하시키는 요인이 된다. 그래서 충돌 해결을 위한 방법으로 Open addressing이 등장했다. 자료구조에서 linear proving과 double hashing에 대해 다룬 바 있으므로 참고하자. 지금은 알고리즘을 다루고 있으므로 생략하고 알고리즘의 관점에서 분석해보겠다.
chaining vs open addressing |
비둘기집 원리: 체이닝의 한계
비둘기집 원리에 따르면, n개의 키 값을 m개의 슬롯에 저장할 때, 최소한 하나의 슬롯에는 ⌈n/m⌉개 이상의 키 값이 저장된다. 즉, 키 값의 개수가 슬롯의 개수보다 많다면, 충돌은 불가피하다.
체이닝 방식은 이러한 충돌을 연결 리스트를 이용하여 해결하지만, 최악의 경우 direct addressing의 worst case와 같이 모든 키 값이 같은 슬롯에 매핑되어 연결 리스트의 길이가 n이 될 수 있다. 이는 체이닝 방식의 근본적인 한계점이다.
다음 시간에는 이러한 문제점을 해결하기 위해 무작위성을 활용하는 방법과, 더 나아가 유니버설 해싱(universal hashing)에 대해 알아보자.
추천글 :
[알고리즘] Linear-Time Sorting
(https://hyeonb.blogspot.com/2024/09/linear-time-sorting.html)
[알고리즘] Randomized algorithm - quicksort, randomized selection, majority element
(https://hyeonb.blogspot.com/2024/10/randomized-algorithm-quicksort.html)