[알고리즘] hash table - direct addressing, hash function, chaining

해시 테이블: 데이터 저장의 효율화

해시 테이블

데이터를 저장하고 검색하는 방법은 여러 가지가 있지만, 그 중에서도 해시 테이블은 탁월한 속도를 자랑하는 자료 구조이다. 마치 도서관의 책처럼, 데이터를 특정 키(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)

hyeon_B

안녕하세요! AI 기술을 이용해 더 나은 세상을 만들어 나가고 싶은 과기원생 Hyeon이라고 합니다. 저는 앞으로 인공지능 시대에는 지식을 '활용'하는 능력이 중요해질 것이라고 생각합니다. 대부분의 일들은 인공지능이 뛰어난 모습을 보이지만, 인공지능은 데이터로 부터 연관관계를 학습하기 때문에 지식들을 새로 통합해서 활용하는 능력이 부족합니다. 인공지능이 뉴턴 전에 만들어졌다면 사과가 떨어지는 이유에 대답하지 못했을 것이고, 아인슈타인 전에 만들어졌다면 중력이 어떻게 생기는지 설명하지 못했을 것입니다. 따라서 앞으로 우리는 '본질'을 탐구하고 그 본질로부터 다른 곳에 적용하며 인공지능을 현명하게 활용해야 할 것입니다. 함께 인공지능 시대를 준비합시다!

댓글 쓰기

다음 이전

POST ADS1

POST ADS 2