HW)
코드 데이터 관련하여 다른 자료 구조로써, 이번에는 해시 테이블(Hash table)의 개념과 구조에 대해서 알아보자. 해시 함수(Hash function)와 index 충돌(Collision)의 의미를 이해하고, 특히 해시 충돌을 해결하는 방법으로 체이닝(Chaining) 방식과 개방 주소(Open Addressing) 방식을 파이썬으로 구현하여 이해해보자.
우선, 해시 테이블(Hash table)이란 무엇일까?
> Hash table은 순차적으로 배열된 각 index에 해당하는 값(bucket or values)을 저장하고 검색(색인)할 수 있도록 재구성된 자료구조이다.
- 아래 [그림1]과 같이, 입력 data에서 주어진 데이터는 쌍으로 주어지며(ex, 딕셔너리의 {'key' : value},...), 그 key가 Hash 함수에 입력값이 되어서 정해진 Hash 연산을 통해 얻은 출력값(해시값)을 Hash table 배열의 index로 사용하게 된다.
- Hash table의 index를 활용하여 데이터 목록을 재구성하는 방식은 작업(검색, 삽입, 삭제) 효율성을 높인다. 다만, index가 충돌(collision)하는 문제가 발생하는 경우에, 공간을 추가하거나 남은 공간을 순차적으로 찾는 방식으로 데이터를 저장함으로써 index 충돌로 인해 데이터가 덮어씌워지는(overwriting) 문제를 해결한다.
필자는 입력 data를, 예를 들어, 대한민국 역대 국가대표 축구선수 베스트 11명을 선정하여 예제로 활용하였다.
※ [그림1] 입력 data, Hash 함수, index 충돌, Hash table 및 Chaining 방식에 대한 도식
> 위 그림의 우측에는, Hash 함수의 연산결과로 index가 중복될 경우, Hash table에 재구성할 때 같은 index의 bucket에 데이터가 겹치는 즉 충돌이 발생하는 문제를 Chaining 방식으로 해결한 결과를 표현하였다.
※ Hash 함수의 연산식은 글쓴이가 임의로 정의하였는데, Hash 함수값과 index를 구한 식은 아래 코드에서 다시 언급하고자 한다.
- 먼저 Chaining 방식은 동일한 index의 bucket에 여러 값을 추가하는 방식으로 저장하는 방식이다.
> 이와 비교하여 아래 그림에서는, Over Addressing 방식으로 해결한 결과를 표현하였다. 즉 Hash 함수의 출력값을 맨 위값(ex, ('차범근', 93)) 부터 순차적으로 읽어서 Hash table의 index에 대응하여 bucket에 데이터를 입력하게 된다.
- 두번째인 ('손흥민', 96)도 index 7번에 해당하지만 이미 ('차범근', 93)이 있어서, 다음 index 8번으로 값이 이동하고 그 8번의 bucket 공간이 비었으면 ('손흥민', 96) 값이 대입되게 된다.
- 이와 같은 방식으로 세번째인 ('안정환', 85) 부터 마지막인 ('조현우', 80)까지 Hash table에서 빈 공간을 순차적으로 찾아서 대입되는 순서를 한 단계씩 표현하였다. 결국, 최종적으로 얻어진 Hash table에서 마지막 ('조현우', 80)는 자신의 초기 index 2번에 들어가지 못하고 index 3번에 들어가게 되는 이유를 쉽게 이해할 수 있다.
※ [그림2] Over Addressing 방식으로 Hash table의 남은 공간을 활용한 충돌을 해결하는 과정.
> Index의 충돌로 인한 문제를 해결하기 위한 방법으로 두 가지(Chaining VS Open Addressing)방식의 차이점을 표로 비교하였다.
| 구분 | Chaining 방식 | Open Addressing 방식 |
| 개념 | > index 충돌이 발생할 시, 동일한(하나의) index에 리스트(Linked List 등)로 여러 값들을 묶어서 저장하는 해결 방식. - 즉 index가 충돌했을 때, 먼저 입력된 값을 나중에 입력된 값으로 덮어씌우지 않고, 해당 index의 bucket 안에 값을 순차적으로 추가할 수 있다. |
> index 충돌이 발생할 시, Hash table 내에서 빈 공간을 찾아서 데이터를 선착순으로 저장하는 방식 - 다른 데이터가 같은 index에 들어오면, 이미 있는 데이터를 그대로 두고(덮어씌우지 않고), 다음 index로 이동하여 빈 공간을 순차적으로 찾아서 저장하게 된다. |
| 특징 | > 충돌 시 데이터를 외부 구조(list)에 저장하므로 안정적임. > Hash table size와 관계없이 같은 index에 계속 저장 가능. |
> Node 삭제 시, 탐색 경로가 끊기지 않도록 주의가 필요 > 선형/이차 탐사, 더블 해싱 등의 충돌 처리 방식이 있다. |
| 장점 | > list에서 node 제거하는 방식으로 데이터 삭제가 편리함. | > 외부 구조(list)의 개입이 없이 비교적 단순한 선형 구조를 가지기 때문에, 효율적인 메모리 사용 가능. |
| 단점 | > Node마다 pointer가 필요하여 메모리의 오버헤드가 발생하기 쉬움 → 연결 list가 길어지면 효율성(성능) 저하. | > index 충돌이 많아질 수 록, 메모리 사용량이 증가하여 성능이 저하됨 > Hash table이 가득 차게 되면 추가 저장 불가 |
| 적합한 상황 | > Hash table size를 정하기 어려운 경우 > 데이터(node)의 삭제, 삽입이 빈번할 때 - 즉 데이터 개수가 변할 수 있는 가능성이 클 때 |
> Hash table size가 고정되어 있는 경우 > 메모리 사용 부하율이 일정 수준이하로 제어 가능 할 때 - 캐시 효율이 중요한 경우 |
그러면, 파이썬으로 Hash table과 두 가지 해결 방식을 구현하는 연습을 해보자.
> 입력 data는 11명 선수의 이름과 글쓴이의 주관적인 오버롤(종합 능력 점수) 이다.
- 이를 딕셔너리 {'key' : value,...} 형식으로 시작하자.
# ────────────────────────────────
# 테스트 목록(나만의 대한민국 축구 베스트 11)
# Hash table: 이름(key) -> 점수(value)
# ────────────────────────────────
li = {
'차범근': 93,
'손흥민': 96,
'안정환': 85,
'이강인': 84,
'박지성': 90,
'기성용': 81,
'황인범': 83,
'이영표': 84,
'김민재': 88,
'송종국': 82,
'조현우': 80,
}
print("테스트 목록(나만의 대한민국 축구 베스트 11)")
print("이름(key) : 점수(value)")
print("-"*30)
# key, value 쌍을 줄바꿈으로 출력
for key, value in li.items():
print(f"{key}:\t {value}")
> 입력 data는 딕셔너리 {'key' : value,...} 형식으로 key는 이름, value는 점수로 출력할 수 있다.
'''
테스트 목록(나만의 대한민국 축구 베스트 11)
이름(key) : 점수(value)
------------------------------
차범근: 93
손흥민: 96
안정환: 85
이강인: 84
박지성: 90
기성용: 81
황인범: 83
이영표: 84
김민재: 88
송종국: 82
조현우: 80
'''
> Hash 함수의 연산식은 글쓴이가 임의로 정해보았다.
- 예로써, 선수 이름의 한글 문자를 유니코드 숫자로 변환한 값에 선수의 점수를 나눈 '몫'을 '누적'하여 total 값으로 저장하였다.
- Hash 함수값 : total += ord(n) + li[key]
# hash 함수와 index 계산을 직접 확인해보기
# 임의 hash 함수 : 이름의 각 글자에 대한 유니코드 숫자와 선수의 점수를 임의로 조합한 함수
# (두 값의 몫의 누적값)
def simple_hash(key):
"""이름 문자열의 문자 코드 합을 구하는 간단한 해시 함수"""
total = 0
for n in key: # name
total += ord(n) // li[key] # ord(n): 이름을 유니코드 숫자로 변환 // li[key]: 선수의 점수
return total
> Hash table의 사이즈는 선수 11명이 배열되어 대입될 수 있는 공간된다.
# hash table 크기
table_size = len(li) # 선수 11명
#print(table_size)
# index와 value를 저장할 hash table 초기화
table = [None] * table_size
# hash 함수와 index 계산 과정 보여주기
print(">> 목록의 각 key : value에 대한 hash 함수값과 구해진 index")
print("이름\t점수 hash 함수값 index")
print("-"*50)
for key, value in li.items():
h = simple_hash(key) # def simple_hash(key)
index = h % table_size # index 는 목록 요소의 개수(11명)에 의존한다.
print(f"{key}\t {value}\t {h}\t {index}")
table[index] = (key, value) # 실제로 값 저장 (충돌 고려 X)
print("\n>> key가 hash 함수에 적용되어 출력된 hash table (index 별 key, value)")
print(">> index가 같아서 충돌이 난 경우, 값이 overwriting 되었다.")
print("index\t bucket")
print("-"*50)
for i, bucket in enumerate(table):
print(f" {i:2.0f} → {bucket}")
> 입력 data와 Hash 함수값과 Hash 연산으로 얻어진 index를 아래와 같이 출력할 수 있다.
- 공교롭게도 황인범과 이영표의 hash 함수값이 같게 되었다.
'''
>> 목록의 각 key : value에 대한 hash 함수값과 구해진 index
이름 점수 hash 함수값 index
--------------------------------------------------
차범근 93 1558 7
손흥민 96 1591 7
안정환 85 1841 4
이강인 84 1738 0
박지성 90 1656 6
기성용 81 1787 5
황인범 83 1857 9
이영표 84 1857 9
김민재 88 1632 4
송종국 82 1771 0
조현우 80 1960 2
'''
> 그 출력값을 Hash table의 순차적인 index에 대응하여 bucket에 입력된 데이터는, index가 중복된 경우에 먼저 대입된 데이터가 나중에 대입된 데이터로 덮어 씌워지게 된다. 즉 먼저 입력된 데이터를 잃어버리게 된다.
- 위 [그림1]을 참고해보자. 한 예로, index 7번에서 먼저 대입된 데이터 ('차범근', 93)이 나중에 대입된 ('손흥민', 96) 으로 덮어씌워졌다(overwriting). 다른 index 4, 0, 9 번의 중복된 경우도 마찬가지다.
'''
>> key가 hash 함수에 적용되어 출력된 hash table (index 별 key, value)
>> index가 같아서 충돌이 난 경우, 값이 overwriting 되었다.
index bucket
--------------------------------------------------
0 → ('송종국', 82)
1 → None
2 → ('조현우', 80)
3 → None
4 → ('김민재', 88)
5 → ('기성용', 81)
6 → ('박지성', 90)
7 → ('손흥민', 96)
8 → None
9 → ('이영표', 84)
10 → None
'''
> Hash table에서 Chaining 방식으로 index 충돌 문제를 해결하는 방식을 구현해보자.
# ────────────────────────────────
# Hash Table (Chaining 방식)
# ────────────────────────────────
# hash table 크기
table_size = len(li) # 선수 11명
#print(table_size)
# index와 value를 저장할 hash table 초기화
table = [None] * table_size
table = [[ ] for _ in range(table_size)] # 각 칸이 리스트
#print(table)
# 삽입
for key, value in li.items():
index = simple_hash(key) % table_size
table[index].append((key, value)) # 같은 index면 리스트에 추가
# 결과 출력
print(">> Chaining 방식으로 연결리스트를 이용하여 충돌을 해결한 결과")
print(">> 같은 index를 지닌 데이터들을 리스트(list)로 묶어 저장함. (overwriting 회피)")
print("index\t bucket")
print("-"*50)
for i, bucket in enumerate(table):
print(f" {i:2.0f} → {bucket}")
- Chaining 방식을 적용하면, 같은 index의 경우 데이터가 bucket에 list로 묶여서 순차적으로 대입된다. (overwrithing 회피)
- 첫번째로 입력된 데이터가 무엇인지를 리스트의 첫번째 값으로 확인할 수 있다.
'''
>> Chaining 방식으로 연결리스트를 이용하여 충돌을 해결한 결과
>> 같은 index를 지닌 데이터들을 리스트(list)로 묶어 저장함. (overwriting 회피)
index bucket
--------------------------------------------------
0 → [('이강인', 84), ('송종국', 82)]
1 → []
2 → [('조현우', 80)]
3 → []
4 → [('안정환', 85), ('김민재', 88)]
5 → [('기성용', 81)]
6 → [('박지성', 90)]
7 → [('차범근', 93), ('손흥민', 96)]
8 → []
9 → [('황인범', 83), ('이영표', 84)]
10 → []
'''
> Hash table에서 Open Addressing 방식으로 index 충돌 문제를 해결하는 방식을 구현해보자.
# ────────────────────────────────
# Hash Table (Open Addressing 방식): 삽입 함수, 충돌 시 선형 탐색
# ────────────────────────────────
# hash table 크기
table_size = len(li) # 선수 11명
#print(table_size)
# index와 value를 저장할 hash table 초기화
table = [None] * table_size
print(">> 충돌이 나면 다음 칸(next index)으로 이동하는 것을 빈 칸에 저장될 때까지 반복함.)")
print("-"*100)
def insert_open_addressing(table, key, value):
index = simple_hash(key) % table_size
start_index = index # 무한루프 방지용
while table[index] is not None: # 이미 차 있으면
index = (index + 1) % table_size # 다음 index 칸으로 이동
print(f"!! 충돌 발생: {key} -> index '{index}' 에 이미 데이터가 있어서, 다음 index '{(index + 1) % table_size}' (으)로 이동")
if index == start_index: # 한 바퀴 다 돌면
print("테이블이 가득 찼습니다!")
return
table[index] = (key, value)
# 데이터 삽입 및 확인
for key, value in li.items():
insert_open_addressing(table, key, value)
print("\n>> Open Addressing 방식으로 연결리스트를 이용하여 충돌을 해결한 결과 (overwriting 회피)")
print("index \t bucket")
print("-"*30)
for i, bucket in enumerate(table):
print(f" {i:2.0f} → {bucket}")
- Open Addressing 방식을 적용하면, 같은 index의 경우 데이터가 다음 index로 이동하여 빈칸이면 대입되고, 빈칸이 아니면 다다음 index로 순차적으로 이동하면서 빈칸을 채우는 방식으로 Hash table이 재구성된다. (overwrithing 회피)
- 이 방식은 파이썬에서도 많이 사용되는 방식이라고 한다. 그 장점에 대해서는 위 [표]의 내용을 다시 상기해보자.
'''
>> 충돌이 나면 다음 칸(next index)으로 이동하는 것을 빈 칸에 저장될 때까지 반복함.)
----------------------------------------------------------------------------------------------------
!! 충돌 발생: 손흥민 -> index '8' 에 이미 데이터가 있어서, 다음 index '9' (으)로 이동
!! 충돌 발생: 이영표 -> index '10' 에 이미 데이터가 있어서, 다음 index '0' (으)로 이동
!! 충돌 발생: 김민재 -> index '5' 에 이미 데이터가 있어서, 다음 index '6' (으)로 이동
!! 충돌 발생: 김민재 -> index '6' 에 이미 데이터가 있어서, 다음 index '7' (으)로 이동
!! 충돌 발생: 김민재 -> index '7' 에 이미 데이터가 있어서, 다음 index '8' (으)로 이동
!! 충돌 발생: 김민재 -> index '8' 에 이미 데이터가 있어서, 다음 index '9' (으)로 이동
!! 충돌 발생: 김민재 -> index '9' 에 이미 데이터가 있어서, 다음 index '10' (으)로 이동
!! 충돌 발생: 김민재 -> index '10' 에 이미 데이터가 있어서, 다음 index '0' (으)로 이동
!! 충돌 발생: 김민재 -> index '0' 에 이미 데이터가 있어서, 다음 index '1' (으)로 이동
!! 충돌 발생: 김민재 -> index '1' 에 이미 데이터가 있어서, 다음 index '2' (으)로 이동
!! 충돌 발생: 송종국 -> index '1' 에 이미 데이터가 있어서, 다음 index '2' (으)로 이동
!! 충돌 발생: 송종국 -> index '2' 에 이미 데이터가 있어서, 다음 index '3' (으)로 이동
!! 충돌 발생: 조현우 -> index '3' 에 이미 데이터가 있어서, 다음 index '4' (으)로 이동
>> Open Addressing 방식으로 연결리스트를 이용하여 충돌을 해결한 결과 (overwriting 회피)
index bucket
------------------------------
0 → ('이강인', 84)
1 → ('김민재', 88)
2 → ('송종국', 82)
3 → ('조현우', 80)
4 → ('안정환', 85)
5 → ('기성용', 81)
6 → ('박지성', 90)
7 → ('차범근', 93)
8 → ('손흥민', 96)
9 → ('황인범', 83)
10 → ('이영표', 84)
'''
이와 같이, Hash table의 index 충돌 문제를 해결하는 두 가지 방식(Chaining, Open Addressing)에 대해서 파이썬 구현을 통해 이해할 수 있었다. 초보자의 관점에서 상대적으로 쉬운 코드를 사용하여 예제를 구현하여 이해하고 확인하는 것은 즐거운 일이다. 앞으로 코드에 계속 능숙해지고 로직에 대한 이해가 깊어지면, 연결리스트(Linked List)의 개념과 더불어 데이터를 삽입하고 삭제는 것까지 구현할 수 있을 것 같다.
필자는 ChartGPT5를 활용하여 파이썬 초보자의 시점에서 체계적인 Q&A를 통해서 코드를 익히고 있다. 적극적으로 활용하되 맹종하지 말고, 에러를 걱정하지 말자!
즐거운 파이썬~ 즐 파이씽~~
[주의] 내용에 오류가 있을 수 있습니다.
'[Code] Study & Practice' 카테고리의 다른 글
| [Python] 자료 구조5 - 힙(Heap)의 개념, 구조, 규칙 (0) | 2025.11.01 |
|---|---|
| [Python] 자료 구조4 - 이진 트리(Binary Tree)의 개념, 구조, 규칙 (0) | 2025.11.01 |
| [Python] 자료 구조2 - Single & Double Linked List(연결 리스트)의 개념과 차이점 (1) | 2025.10.28 |
| [Python] 자료 구조1 - 스택(Stack)과 큐(Queue)의 개념과 차이점 (0) | 2025.10.27 |
| [Python] 메모리(RAM)와 변수(Variable)의 개념. (0) | 2025.10.22 |