해시테이블(Hash Table)이란?

1. Hashing이란?

해싱(hashing)은 각각의 데이터를 해시 함수를 통해 '고유한 값(해시값)'으로 변환하는 과정을 의미합니다.

 

이 해시값은 데이터의 식별자(index)로 사용되어, 데이터 탐색에 활용됩니다

해싱 개념을 기반으로 만들어진 자료구조가 바로 해시 테이블(Hash Table)입니다.

 

---

 

2. 해시 함수(Hash Function)

해시 함수는 입력값을 고정된 길이의 고유한 값으로 변환하는 함수입니다.

예를 들어, "Hello World!"라는 문자열을 해시 함수에 입력하면 다음과 같은 해시값(문자열)이 생성됩니다.

"Hello World!"의 해시 값 : 2ef7 bde6 08ce 5404 e97d 5f04 2f95 f89f 1c23 2871

 

 

만약 입력값 중 한 글자라도 바뀌면, (ex. "Helli World!"로 변경) 다음과 같은 완전히 다른 해시값이 생성됩니다.

"Helli World!"의 해시 값 : ec8a c7b8 a5c0 f1d0 835f 488b a3d4 f46e 6a5f 9630

 

이처럼 해시 함수는 입력값이 조금만 달라져도 전혀 다른 고유값을 만들어 냅니다

 

 

---

 

3. 해시 테이블(Hash Table)

해시 테이블(Hash Table)이란, 데이터를 key - value 형태로 저장하는 자료구조를 의미합니다.

 

가령, 'apple' : 3라는 자료를 저장하고자 할 때, 다음과 같은 과정이 일어납니다

 

I. key 값('apple')에 해시함수를 적용합니다. 다음과 같은 해시값 생성

2ef7 bde6 08ce 5404 e97d 5f04 2f95 f89f 1c23 2871

 

II. 자료를 넣을 index를 계산합니다.

이때 index를 구하는 공식은 다음과 같습니다.

 

index = hash(key) % capacity

 

hash 값에 해시 테이블의 사이즈(capacity)로 mod(나누기) 연산을 진행합니다

 

index = (2ef7 bde6 08ce 5404 e97d 5f04 2f95 f89f 1c23 2871) % capacity

 

III. 도출한 index를 이용하여 값을 저장합니다

 

 

---

 

 

Q1. 해시 테이블의 capacity로 나누기 연산을 하는 이유가 무엇인가요?

A. 해시값은 '매우 큰 수'입니다. 이를 해시 테이블의 '유효한 인덱스'로 변환하는 과정이 필요하고, 이로 인해 capacity를 사용하는 것입니다. 해시 테이블의 사이즈가 5라면(capacity = 5), 유효한 인덱스는 0~4에 해당하고, 0~4 범위 내에 해당하는 값을 구하기 위해 capacity로 매우 큰 수를 나누는 것입니다

 

 

Q2. 'apple' = 3이라는 자료를 저장할 때, 그냥 dict를 사용하면 되지 않나요? 

A. 사실 dict는 내부적으로 해시 함수를 사용하고 있어, 'apple'이라는 문자열을 해싱한 후, 인덱스를 계산하여 저장합니다. 직접 hash(key) % capacity를 계산하지 않아도, 파이썬이 이 과정을 자동으로 처리하는 것이죠. 따라서 dict['apple']의 조회 시간은 평균적으로 O(1)입니다

 

 

 

---

4. 해시 충돌(Hash Collision)

해시 테이블(Hash Table)에는 해시 충돌이 존재합니다.

나누기 연산을 하다보면, 같은 인덱스를 가리키는 값들이 발생하게 되는데하, 이때 자료를 어디에 저장할 것인가를 확정하는 것을 해시 충돌이라고 칭합니다

 

 

해시 충돌은 I. 체이닝(Chaining)과 II. 개방 주소법(Open Addressing)으로 해결합니다

 

 

I. Chaining

Chaining 기법은 해시 테이블에서 충돌이 발생했을 때, 해당 인덱스에 여러 개의 데이터를 저장할 수 있도록 별도의 자료구조(보통 연결 리스트)를 사용하는 방식입니다.

• 같은 해시 인덱스를 가지는 여러 개의 (key, value) 쌍을 리스트, 연결 리스트 등으로 저장합니다.
• 이로 인해 충돌이 발생하더라도 각 데이터를 구분해서 관리할 수 있습니다.

 

 

 

II. Open Addressing

Open Addressing은 충돌이 발생했을 때, 해시 테이블 내에 비어 있는 공간에 할당하는 방식입니다.

 

Open Addressing은 3가지 방법으로 분류됩니다

 

a. 선형 탐사 (Linear Probing)

정의 : 충돌이 발생했을 때, 한 칸씩 다음 위치로 이동하면서 빈 자리를 찾습니다

 

 

예를 들어 'delete' = 1002, 'int' = 1003이라는 두 데이터를 저장하려고 할 때,
두 key 모두 해시 함수를 통해 계산된 index = 3을 가리킨다고 가정해 봅시다.

 

1. 먼저 'delete'가 저장되며, index 3이 비어 있으므로 해당 위치에 저장됩니다.
2. 이후 'int'를 저장할 때, index 3은 이미 사용 중이므로,
   다음 인덱스 (index 4)를 확인합니다
3. index 4가 비어 있으므로 'int'는 index 4에 저장됩니다.

 

index 3을 가리키는 데이터가 들어오면 다음 빈 공간이 나올때까지 index + 1 연산을 계속해서 수행합니다

직관적이고, 쉬운 해결법인 반면, 클러스터링(군집화) 문제가 발생할 수 있습니다.

 

클러스터링(군집화). 문제는 다음과 같습니다 : 

해시 테이블의 가장 큰 장점은 인덱스를 통해 값을 빠르게 찾을 수 있다는 점으로, 평균적으로 시간 복잡도가 O(1)입니다.
하지만 해시 충돌이 많아질수록, 같은 인덱스에 여러 값이 몰리게 되어 해당 위치 근처의 모든 요소를 탐색해야 하므로 성능이 저하될 수 있습니다.

 

 

b. 제곱 탐사 (Quadratic Probing)

 

정의 : 충돌 시, 제곱 간격으로 다음 위치를 탐색합니다

 

 

c. 이중 해싱 (Double Hashing)

정의 : 충돌 시, 두 번째 해시 함수로 간격을 계산하여 이동합니다.

 

앞에서 소개한 두 기법 중, 클러스터링 현상이 가장 적으나, 불필요한 연산이 2번 수행된다는 단점이 존재합니다