CS학습2026년 8월 16일

해시 테이블: 키-값 쌍을 저장하고 효율적인 검색, 삽입, 삭제를 지원하는 자료구조

해시 테이블은 키(Key)와 값(Value)의 쌍을 저장하는 자료구조로, 배열과 해시 함수를 이용하여 데이터에 빠르게 접근할 수 있다. 충돌 해결 전략에 따라 성능이 달라지며, 다양한 실무 환경에서 활용된다. 특히 검색 속도가 중요한 경우 유용하다.

송민성4분 읽기

1. 개념

해시 테이블(Hash Table)은 키-값 쌍(Key-Value Pair)을 저장하는 자료구조이다. 배열과 해시 함수를 사용하여 데이터를 저장하고 검색한다. 키는 해시 함수를 통해 배열의 인덱스로 변환되고, 이 인덱스에 해당하는 위치에 값이 저장된다.

2. 왜 사용하는가

빠른 접근: 평균적으로 O(1) 시간 복잡도로 데이터에 접근할 수 있다 (충돌이 없을 경우).
효율적인 검색: 키를 이용하여 데이터를 빠르게 찾을 수 있다.
다양한 활용: 캐싱, 데이터베이스 인덱스 등 다양한 분야에서 사용된다.

3. 동작 원리

해시 함수(Hash Function): 키를 입력받아 정수 형태의 해시 값(Hash Value)을 반환한다. 좋은 해시 함수는 키의 작은 변화에도 해시 값이 크게 달라지도록 설계되어야 한다 (균등 분포).
배열: 해시 값을 인덱스로 사용하여 데이터를 저장하는 배열이다.
충돌 해결(Collision Resolution): 서로 다른 키가 동일한 해시 값으로 변환되는 현상을 충돌이라고 한다. 충돌이 발생하면 체이닝(Chaining) 또는 개방 주소법(Open Addressing)과 같은 방법을 사용하여 해결한다.

* 체이닝 (Chaining): 각 배열 요소에 연결 리스트(Linked List)를 두어, 동일한 해시 값을 갖는 키-값 쌍을 연결 리스트에 저장하는 방식이다. * 개방 주소법 (Open Addressing): 충돌이 발생하면 배열의 다른 빈 공간을 찾아 데이터를 저장하는 방식이다. 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 방법이 있다.

4. 코드 예제

python

class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)] # 체이닝을 위한 리스트 초기화

    def hash_function(self, key):
        return hash(key) % self.capacity

    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index].append((key, value)) # 키-값 쌍을 연결 리스트에 추가

    def get(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None # 키가 없으면 None 반환

    def delete(self, key):
        index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return

5. 시간 복잡도 또는 성능 특성

삽입: 평균 O(1), 최악 O(n) (충돌이 많이 발생할 경우)
검색: 평균 O(1), 최악 O(n) (충돌이 많이 발생할 경우)
삭제: 평균 O(1), 최악 O(n) (충돌이 많이 발생할 경우)

해시 테이블의 성능은 해시 함수의 품질과 충돌 해결 전략에 크게 의존한다. 좋은 해시 함수는 키를 균등하게 분산시켜 충돌을 최소화해야 한다.

6. 실무 사용 사례

캐싱: 자주 접근하는 데이터를 해시 테이블에 저장하여 빠른 액세스 속도를 제공한다.
데이터베이스 인덱스: 데이터베이스에서 특정 필드를 기준으로 빠르게 검색할 수 있도록 해시 인덱스를 사용한다.
컴파일러 심볼 테이블: 변수, 함수 등의 이름과 해당 정보를 저장하는 데 사용된다.
JSON 객체: JavaScript 객체의 구현에 활용되는 경우가 많다 (key-value 구조).

7. 주의할 점

충돌 처리: 충돌이 발생했을 때 성능 저하를 최소화하기 위해 적절한 충돌 해결 전략을 선택해야 한다.
해시 함수 품질: 해시 함수의 품질은 성능에 큰 영향을 미치므로, 데이터 특성에 맞는 좋은 해시 함수를 설계해야 한다. Python의 hash()는 문자열, 숫자 등 기본적인 자료형에 대해서는 잘 작동하지만, 사용자 정의 객체에는 적절하지 않을 수 있다.
리사이징: 해시 테이블의 크기가 너무 작으면 충돌이 자주 발생하여 성능이 저하될 수 있다. 따라서 필요에 따라 해시 테이블의 크기를 늘려주는 리사이징(Resizing)을 고려해야 한다.

8. 핵심 정리

해시 테이블은 키-값 쌍을 효율적으로 저장하고 검색하는 데 유용한 자료구조이다. 좋은 성능을 위해서는 적절한 해시 함수와 충돌 해결 전략을 선택하는 것이 중요하다. 다양한 실무 환경에서 활용되며, 캐싱, 데이터베이스 인덱스 등 중요한 역할을 수행한다.