[크래프톤 정글 week01] 해시 테이블

해시 테이블의 정의

**해시 테이블(Hash Table)**은 해시 함수를 사용하여 데이터(키-값 쌍)를 특정 인덱스에 매핑(mapping)함으로써, 평균적으로 O(1) 시간 복잡도로 데이터의 **삽입(Insertion), 삭제(Deletion), 검색(Search)**을 지원하는 효율적인 자료 구조다.

해시 테이블은 주어진 키를 빠르게 검색할 수 있도록 해시 값을 사용하여, 데이터를 저장할 위치를 계산하고 해당 위치에 데이터를 저장한다.

O(1) 복잡도(상수 시간 복잡도)는 알고리즘의 실행 시간이 입력 크기와 상관없이 일정한 경우를 나타낸다.

 

해시 테이블의 주요 구성 요소

1. 해시 함수(Hash Function):
   • 입력 값(키)을 고정된 크기의 해시 값으로 변환하는 함수다. 이 해시 값은 해시 테이블에서 데이터가 저장될 인덱스를 결정한다.
   • 해시 함수는 해시 값을 고르게 분포시켜 **해시 충돌(Hash Collision)**을 최소화해야 하며, 효율적으로 계산될 수 있어야 한다.
2. 해시 값(Hash Value):
   • 해시 함수의 결과로 얻어지는 값이다. 이 값은 일반적으로 해시 테이블의 크기와 연관된 인덱스를 나타내며, 데이터를 저장하고 검색하는 데 사용된다.
3. 버킷(Bucket):
   • 해시 값이 동일한 여러 개의 키-값 쌍을 저장할 수 있는 저장 공간이다. 버킷은 연결 리스트(Chaining) 또는 **개방 주소법(Open Addressing)**을 사용해 충돌이 발생했을 때 여러 데이터를 처리할 수 있다.
4. 해시 충돌(Hash Collision):
   • 서로 다른 키들이 동일한 해시 값을 가질 때 발생하는 상황이다. 이를 처리하기 위해 해시 테이블은 **연결 리스트(Chaining)**나 개방 주소법(Open Addressing) 같은 충돌 해결 기법을 사용한다.

 

버킷(Bucket) 과 인덱스

 

인덱스(index)란 데이터 구조나 데이터베이스에서 특정 데이터에 빠르게 접근할 수 있도록 도와주는 구조나 개념을 의미한다. 인덱스는 책의 색인처럼, 필요한 정보를 찾기 위해 빠르게 참조할 수 있는 위치를 가리키는 역할을 한다.

버킷과 인덱스의 유사점:

1. 데이터 위치 지정: 둘 다 데이터를 저장할 위치를 지정하는 역할을 한다.
2. 빠른 접근: 데이터를 빠르게 검색하거나 접근할 수 있도록 돕는다.
3. 고유한 식별자: 각각 고유한 번호(버킷 번호나 인덱스)를 사용해 데이터의 위치를 식별한다.

즉, 버킷과 인덱스 모두 효율적인 데이터 관리와 빠른 접근을 위해 사용된다.

인덱스가 빠른 조회를 가능하게 하는 주요 이유

1. 정렬된 데이터 구조:
   • 인덱스는 보통 B-트리(Balanced Tree) 구조나 해시 테이블(Hash Table) 구조로 저장된다. 이 데이터 구조들은 삽입, 삭제, 검색 연산을 매우 효율적으로 수행할 수 있도록 설계되어 있다.
   • 예를 들어, B-트리 구조에서는 인덱스가 정렬된 상태로 유지되므로, 이진 탐색(Binary Search)을 통해 검색 속도를 매우 빠르게 할 수 있다.
   • 해시 테이블의 경우, 해시 함수를 통해 특정 키(key)에 대한 값을 즉시 접근할 수 있어 검색 속도가 매우 빠르다(O(1) 복잡도).
2. 이진 탐색(Binary Search) 사용:
   • 인덱스는 데이터가 정렬된 상태로 저장되기 때문에, 이진 탐색을 사용하여 검색할 수 있다.
   • 이진 탐색은 탐색 공간을 절반씩 줄여가면서 목표 데이터를 찾는 방식으로, 시간 복잡도가 O(log n)으로 매우 효율적이다.
   • 예를 들어, 1,000개의 데이터 중 특정 값을 찾기 위해 전체를 순차적으로 검색하는 대신, 이진 탐색을 사용하면 약 10번만 비교하면 된다.
3. 데이터의 부분 집합만 스캔:
   • 인덱스를 사용하면 전체 테이블이 아니라 데이터의 일부(부분 집합)만 검색할 수 있다.
   • 예를 들어, orders 테이블에서 user_id가 1인 모든 주문을 찾을 때, 인덱스가 없다면 모든 행을 하나씩 확인해야 한다(전체 테이블 스캔). 그러나 user_id에 인덱스가 있으면 인덱스 구조를 통해 user_id가 1인 행들만 빠르게 찾을 수 있다.
4. 인덱스 페이지 탐색:
   • 데이터베이스는 인덱스를 메모리에 적재할 수 있는 작은 페이지 단위로 저장하고 관리한다.
   • 데이터베이스가 특정 데이터를 찾기 위해 페이지를 탐색할 때, 인덱스는 훨씬 적은 수의 페이지 조회만으로 데이터를 찾을 수 있게 한다. 이는 디스크 I/O(입출력) 비용을 크게 줄인다.
5. 효율적인 검색 경로 제공:
   • 인덱스는 특정 컬럼의 값에 대해 데이터가 저장된 위치를 가리키는 "포인터"를 포함하고 있다.
   • 이러한 포인터를 통해 데이터베이스는 특정 값이 저장된 정확한 위치로 곧바로 이동할 수 있어 조회 속도가 빨라진다.

 

해시 테이블의 특징

빠른 검색: 해시 테이블은 평균적으로 O(1) 시간 복잡도로 데이터를 검색할 수 있어 빠른 조회가 가능하다.

• 효율적인 메모리 사용: 데이터가 해시 값을 기반으로 저장되므로, 메모리를 효율적으로 사용할 수 있다.
• 키-값 쌍 저장: 해시 테이블은 주로 키-값 쌍을 저장하고 관리하는 데 적합하다.

해시 테이블의 장점

• 빠른 데이터 액세스: 평균적으로 O(1) 시간에 데이터의 삽입, 검색, 삭제가 가능하다.
• 효율적인 메모리 사용: 필요에 따라 해시 테이블 크기를 동적으로 조정할 수 있다.
• 다양한 응용: 캐시, 데이터베이스 인덱스, 집합(Set), 맵(Map) 등의 다양한 상황에서 활용된다.

해시 테이블의 단점

• 해시 충돌: 잘못된 해시 함수로 인해 충돌이 자주 발생하면 성능이 저하될 수 있다.
• 메모리 사용량: 해시 테이블의 크기를 크게 설정해야 충돌이 줄어드나, 메모리 사용량이 증가할 수 있다.
• 정렬되지 않은 데이터: 해시 테이블의 데이터는 정렬되지 않으므로, 정렬된 데이터가 필요한 경우 부적합하다.

 

해시 테이블의 기본 개념

 

예를 들어 친구의 전화번호를 찾기 위해 우리는 전화번호부를 사용한다. 전화번호부는 보통 이름 순서로 정렬되어 있어서, 알파벳 순서로 이름을 찾고, 그에 대응하는 전화번호를 찾는다. 해시 테이블은 이 전화번호부를 아주 빠르게 찾을 수 있도록, 이름을 숫자로 바꿔서 그 숫자에 해당하는 위치에 전화번호를 저장하는 방식이라고 생각할 수 있다.

 

간단한 해시 테이블 예시

1. 해시 함수: 이름을 숫자로 바꿔주는 함수라고 생각하자.
   • 예를 들어, 해시 함수는 각 이름의 첫 글자를 숫자로 변환한다고 하자. 'A'는 1, 'B'는 2, ..., 'Z'는 26이 된다.
2. 해시 테이블 구조: 전화번호를 저장할 26개의 상자(버킷)가 있는 배열이 있다고 가정하자.
   • 각 상자는 A부터 Z까지의 각 글자에 해당하는 전화번호를 저장할 수 있다.
3. 데이터 저장:
   • 예를 들어, "Alice"라는 이름의 전화번호를 저장하려고 한다고 하자.
   • 첫 글자 'A'를 해시 함수에 넣으면, 숫자 1이 나온다.
   • 그럼, 1번 상자(버킷)에 "Alice"의 전화번호를 저장한다.

 

 

1. 데이터 검색:
   • "Alice"의 전화번호를 찾고 싶을 때, 다시 해시 함수에 이름 "Alice"를 넣어 첫 글자 'A'가 숫자 1임을 알게 된다.
   • 이제 1번 상자를 바로 확인하여 전화번호를 찾을 수 있다. 다른 모든 상자를 다 뒤져볼 필요가 없으므로 매우 빠르다.

 

Python을 사용한 해시 테이블 예제

아래는 이름과 전화번호를 저장하고 조회할 수 있는 간단한 해시 테이블 예시다:

```python

# 해시 테이블을 크기 26의 리스트로 초기화 (알파벳 A-Z에 대응)
hash_table = [None] * 26

# 간단한 해시 함수: 이름의 첫 글자를 숫자로 변환 ('A' -> 0, 'B' -> 1, ..., 'Z' -> 25)
def hash_function(name):
    return ord(name[0].upper()) - ord('A')

# 데이터 삽입 함수
def insert(name, phone_number):
    index = hash_function(name)  # 이름을 해시 값으로 변환
    hash_table[index] = phone_number  # 해당 해시 값 위치에 전화번호 저장

# 데이터 검색 함수
def search(name):
    index = hash_function(name)  # 이름을 해시 값으로 변환
    return hash_table[index]  # 해당 위치에 저장된 전화번호 반환

# 데이터 저장
insert("Alice", "010-1234-5678")
insert("Bob", "010-2345-6789")

# 데이터 검색
print(search("Alice"))  # 출력: 010-1234-5678
print(search("Bob"))    # 출력: 010-2345-6789

```

해시 충돌 

예시: 우체통과 편지

1. 우체통과 해시 테이블의 비유:
   • 우체통이 여러 개 있는 아파트를 생각해보자. 각 우체통은 특정 아파트 호수(예: 101호, 102호, ...)에 해당하는 고유 번호를 가지고 있다.
   • 해시 테이블은 우체통처럼 여러 개의 "버킷"을 가지고 있고, 이 버킷들이 데이터를 저장할 공간을 의미한다.
2. 해시 함수의 역할:
   • 아파트 관리자가 새로운 편지를 받을 때마다, 편지에 적힌 이름을 보고 해당 우체통(버킷)에 넣어야 한다고 생각해보자.
   • 이때, "이름 → 우체통 번호"로 변환하는 규칙이 해시 함수의 역할을 한다.
3. 해시 충돌의 발생:
   • 만약 "Alice"와 "Alan" 두 사람의 편지를 받았는데, 관리자가 이름을 변환하는 규칙(해시 함수)을 사용해 보니 두 사람의 이름 모두 "101호 우체통"에 해당한다고 나온다면, 이것이 바로 해시 충돌이다.
   • 즉, 서로 다른 두 사람("Alice"와 "Alan")의 편지가 동일한 우체통(버킷)으로 매핑된 상황이다.

해시 충돌 해결 방법

해시 충돌을 해결하는 방법은 여러 가지가 있다.

 

1. 체이닝(Chaining):

• 각 버킷은 연결 리스트(Linked List) 또는 다른 데이터 구조를 사용해, 충돌이 발생한 모든 데이터를 저장한다.
• 동일한 해시 값을 가지는 여러 개의 데이터가 한 버킷에 들어가게 되면, 이 버킷은 그 데이터를 모두 연결 리스트로 연결한다.
• 검색할 때는, 해당 버킷에 접근한 다음, 연결 리스트의 모든 요소를 순차적으로 탐색하여 일치하는 데이터를 찾는다.

예를 들어, 해시 함수가 다음과 같은 값을 반환했다고 가정하자:

• "Alice" → 해시 값 2
• "Bob" → 해시 값 3
• "Charlie" → 해시 값 2

이 경우, "Alice"와 "Charlie"는 동일한 해시 값을 가지기 때문에, 둘 다 버킷 2에 저장된다. 버킷 2는 "Alice"와 "Charlie"를 연결 리스트로 관리하게 된다.

 

2. 개방 주소법(Open Addressing):

• 충돌이 발생할 때, 다른 비어 있는 버킷을 찾아 데이터를 저장하는 방식이다.
• 이 방법은 여러 가지 방식으로 구현될 수 있으며, 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다.
• 예를 들어, 충돌이 발생하면 해시 테이블 내에서 순차적으로 다음 비어 있는 버킷을 찾아 데이터를 저장한다.

예를 들어:

• "Alice" → 해시 값 2
• "Bob" → 해시 값 3
• "Charlie" → 해시 값 2 (충돌 발생)

충돌이 발생했으므로, "Charlie"는 버킷 2가 아닌 다음 빈 버킷(예: 버킷 4)에 저장된다.