[ Data Structure ] 해시 맵(Hash Map)과 해시 테이블(Hash Table)

해시 맵과 해시 테이블은 현대 컴퓨터 과학에서 가장 중요하고 널리 사용되는 자료 구조(data structure) 중 하나이다. 이들은 빠른 데이터 접근(data access)과 효율적인 저장(storage)을 가능하게 하여 다양한 응용 프로그램(application)에서 핵심적인 역할을 한다.

해시 맵(Hash Map)

해시 맵(Hash Map)의 정의와 용도

해시맵은 키-값 쌍(key-value pair)으로 이루어진 자료 구조이다. 키를 해시 함수(hash function)에 넣어 계산한 해시 값(hash value)을 배열(array)의 인덱스(index)로 사용하여 값을 저장하고 조회한다. 주요 특징은 다음과 같다:

• 데이터 조회, 삽입, 삭제(lookup, insertion, deletion)의 시간 복잡도(time complexity)가 O(1)로 매우 빠르다.
• 키를 기반으로 값을 효율적으로 찾을 수 있다.
• 데이터 크기(data size)가 동적으로(dynamically) 늘어날 수 있다.

해시 맵의 주요 개념

1. 해시 함수(Hash Function)
   • 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑(mapping)하는 함수이다.
   • 해시 값을 배열의 인덱스로 사용한다.
2. 해시 테이블(Hash Table)
   • 해시맵을 구현하기 위한 자료 구조이다.
   • 배열과 연결 리스트(linked list)로 구성된다.
3. 해시 충돌(Hash Collision)
   • 서로 다른 키에 대해 같은 해시 값이 계산되는 상황이다.
   • 해결 기법으로는 개별 체이닝(separate chaining), 개방 주소법(open addressing) 등이 있다.

해시 맵의 장단점

장점(Advantages)	단점(Disadvantages)
데이터 조회/삽입/삭제의 시간 복잡도가 O(1)로 매우 빠름	해시 충돌이 발생할 수 있음
키를 기반으로 값을 효율적으로 찾을 수 있음	데이터가 정렬된(sorted) 상태로 저장되지 않음
데이터 크기가 동적으로 늘어날 수 있음	메모리 오버헤드(memory overhead)가 발생할 수 있음

해시 테이블(Hash Table)

해시 테이블은 해시맵을 구현하기 위한 실제적인 자료 구조(data structure)이다. 배열과 연결 리스트로 구성되어 있으며, 해시 함수를 통해 계산된 해시 값을 배열의 인덱스로 사용한다.

해시 테이블의 구조

• 배열의 각 인덱스에는 연결 리스트가 연결되어 있다.
• 키-값 쌍(key-value pair)은 연결 리스트에 저장된다.

해시 테이블의 주요 연산

1. 삽입(Insertion)
   • 해시 함수를 통해 해시 값을 계산하고, 그 값을 인덱스로 사용하여 연결 리스트에 키-값 쌍을 삽입한다.
2. 조회(Search)
   • 해시 함수를 통해 해시 값을 계산하고, 그 값을 인덱스로 사용하여 연결 리스트를 탐색하며 키에 해당하는 값을 찾는다.
3. 삭제(Deletion)
   • 해시 함수를 통해 해시 값을 계산하고, 그 값을 인덱스로 사용하여 연결 리스트에서 키에 해당하는 값을 삭제한다.

해시 충돌 해결 기법

1. 개별 체이닝(Separate Chaining)
   • 해시 충돌이 발생하면 연결 리스트에 데이터를 추가한다.
   • 장점(Advantage): 구현이 간단하다.
   • 단점(Disadvantage): 메모리 오버헤드 발생 가능성이 높다.
2. 개방 주소법(Open Addressing)
   • 해시 충돌이 발생하면 다른 빈 공간(empty space)을 찾아 데이터를 저장한다.
   • 대표적인 기법: 선형 탐색(Linear probing), 이중 해싱(Double hashing) 등
   • 장점(Advantage): 메모리 오버헤드가 적다.
   • 단점(Disadvantage): 계산 복잡도(computation complexity)가 높고, 클러스터링(clustering) 문제가 발생할 수 있다.

실제 응용 사례

1. 데이터베이스 인덱싱(Database indexing): 빠른 데이터 검색(data retrieval)을 위해 사용된다.
2. 캐싱 시스템(Caching system): 웹 서버에서 자주 요청되는 데이터를 빠르게 제공하기 위해 사용된다.
3. 중복 제거(Deduplication): 대용량 데이터에서 중복된 항목을 효율적으로 제거하는 데 사용된다.
4. 블록체인(Blockchain): 암호화폐의 거래 검증(transaction verification)에 사용된다.

해시 맵과 해시 테이블은 그 효율성(efficiency)과 유연성(flexibility)으로 인해 현대 컴퓨팅에서 필수적인 자료 구조이다. 그러나 해시 충돌과 같은 잠재적 문제를 이해하고 적절히 관리하는 것이 중요하다.