자료구조 - 해시 테이블 (Hash Table)

1. 해시 테이블(Hash Table)이란 무엇인가?

해시 테이블은 키(key)를 이용해서 값(value)에 아주 빠르게 접근하는 자료구조이다.

---

2. 해시 함수(Hash Function)

해시 함수는 임의의 길이를 가진 데이터(key) 값을 입력 받아 배열의 특정 인덱스(index)로 변환해주는 함수이다.

즉, 데이터를 저장하거나 검색하기 위해 key값을 숫자 형태의 위치 값으로 바꿔준다.

 

또한, 해시 함수는 key 값들이 특정 위치에 몰리지 않도록 배열 전체에 고르게 분산되게 만들어 충돌(Collision)을 줄이고,  빠른 검색 속도를 유지할 수 있도록 도와준다.

---

3. Key와 Value의  구조 

 

해시 테이블에서 key와 value는 한 쌍으로 저장되는 데이터 이다.

Key는 해시 함수를 통해 데이터를 찾기 위한 인덱스가 되고,

value는 실제 저장되는 데이터이다.
해시 테이블은 key를 활용해 저장 위치를 통해 value 값을 빠르게 찾을 수 있다.

---

4. 충돌(Collision)이 발생하는 이유

 

 

해싱(Hashing) 과정에서 해시 함수(hash function)를 통해 각 key에 대한 해시 값(hash value)를 생성하게 된다.
이 때 생성된 해시 값은 해시 테이블에서 데이터를 저장할 인덱스(index)로 사용된다.

 

하지만, 서로 다른 key라고 해도 언제나 다른 해시 값을 가지는 것은 아니고, 같은 해시 값(Hash Table의 index)을 반환하는 상황이 발생할 수 있다.

 

이 때, 두 개 이상의 key가 동일한 해시 값을 가지게 되는 현상을 충돌(Collision)이라고 한다.

 

---

5. 충돌 해결 방법

5.1 Chaining

체이닝(Chaining)은 같은 해시 값을 가지는 데이터들을 연결 리스트로 연결하여 저장하는 방법이다.

서로 다른 키(key)가 같은 인덱스로 매핑되어 충돌해도, 해당 위치에서 데이터를 연결 리스트 형태로 이어 붙여 저장하게 된다.

체이닝 방식은 구조가 비교적 단순해서 구현이 쉬운 편이지만, 연결 리스트를 추가로 사용해야 하므로 추가적인 메모리 공간이 필요하다는 단점이 있다.

5.2 Open Addressing

이 방법은 충돌이 발생했을 때, 해시 테이블 내부에서 빈 공간을 찾아 데이터를 저장하는 방식이다.
위의 체이닝 방식처럼 연결 리스트를 사용하는 것이 아니라, 해시 테이블 자체에서 새로운 저장 위치를 탐색한다.

 

즉, 충돌이 발생하면 다른 빈 곳을 찾아 데이터를 저장하는 것이다.

해시테이블의 각 칸은 데이터가 저장되거나 비어있는 상태(NIL)로 존재하고, 원하는 데이터를 찾을 때까지 테이블 내부를 탐색한다.

Open Addressing의 가장 대표적 기법은 선형 조사법이다.

선형 조사법

선형 조사법은 충돌이 발생했을 때 다음 인덱스를 순차적으로 탐색하는 방식이다.
만약 원래 저장하려던 위치가 이미 사용 중이라면 바로 다음 칸을 확인하고, 비어있는 공간이 나올 때까지 한 칸씩 이동하며 탐색한다.

---

6. 파이썬의 dictionary와 해시 테이블의 관계

 

파이썬의 dictionary와 Hash Table의 공통점과 차이점을 아래와 같이 정리해보았다. 

구분	해시 테이블	파이썬의 dictionary
개념	key-value 데이터를 빠르게 저장하고 조회하기 위한 자료구조 원리	해시 테이블을 기반으로 구현된 파이썬의 내장 자료형
사용 방식	구현 대상으로 사용	파이썬에서 바로 사용 가능
데이터 저장 방식	해시 함수를 이용해 key를 인덱스로 변환하여 저장	내부적으로 해시 테이블 방식을 사용
공통점
둘 다 key → value 형태로 데이터를 저장한다
해싱(Hashing)을 통해 데이터를 빠르게 조회할 수 있다
데이터의 삽입, 삭제, 조회가 평균적으로 빠른 편이다

 

 

 

---

7. 해시 테이블의 장단점

장점

1️⃣ 키(key)의 유연성

해시 테이블은 키의 타입을 유연하게 허용한다.
정수 인덱스만 사용하는 배열(Array)과 달리, 해시 테이블은 문자열을 포함한 다양한 자료형을 key로 사용할 수 있다.

2️⃣ 빠른 검색,삽입,삭제

해시 테이블은 검색(Search), 삽입(Insertion), 삭제(Deletion) 연산이 일반적으로 빠른 편이다.
이는 해시 함수를 이용해 데이터를 저장할 위치를 바로 찾아가기 때문이다.
평균적으로 해시 테이블의 시간 복잡도는 O(1) 수준이다.

3️⃣ 동적인 크기 조정

해시 테이블은 데이터 개수가 증가하거나 감소함에 따라 테이블의 크기를 동적으로 조정(resize) 할 수 있다.

---

단점

1️⃣ 정렬되지 않은 데이터

해시테이블은 요소의 저장 순서나 정렬을 보장하지 않는다. 그래서 만약 특정 순서를 유지해야 하는 상황이라면, 요소를 연속적으로 저장하는 배열과 같은 자료구조가 더 적합할 수 있다.

2️⃣ 추가적인 메모리 오버헤드

해시 테이블은 추가적인 메모리 사용이 필요하다.
이는 해시 함수, 해시 버킷(bucket), 그리고 해시 충돌(collision)을 처리하기 위한 추가 공간이 필요하기 때문이다.

---

8. 해시 테이블

8.1 간단한 해시 테이블 및 해시 충돌 예시 구현해보기

카페 음료(key)와 가격(value)를 저장하는 해시테이블을 구현해보았다.

class Cafe:
  def __init__(self,size=5):
    self.size=size # self.size :  카페의 음료 개수
    self.table=[[] for _ in range(self.size)]
    # 음료의 개수 만큼 리스트 안에 [음료 이름,가격] 리스트를 넣기 위해 빈 리스트들을 그만큼 미리 추가
    # 예를 들어 음료가 5개라면 
    # [ [], [], [], [], [] ] 미리 세팅 


 # 음료 이름을 받아서 해시 값을 생성하는 해시 함수 
  def hash_func(self,key):

    hash_value=sum([ord(char) for char in key])

    return hash_value % self.size  # 생성된 해시값을 테이블의 크기로 나눈 나머지를 return -> self.table의 인덱스가 된다


# 음료 이름(key)과 가격(value)를 해시 테이블에 저장한다.  
  def put(self,key,value):



    idx= self.hash_func(key) # 음료 이름(key)를 해시 함수를 돌려 나온 값을 idx로 

    bucket= self.table[idx] # table[idx] 

    # 해당 인덱스에 이미 같은 음료가 등록되어 있는 지 확인 

    for kv in bucket :
      if kv[0]== key: # 이미 같은 메뉴가 있을 때

        kv[1]=value # value 값으로 kv[1]을 변경한다
        return

    bucket.append([key,value]) # 저장되어 있지 않았던 음료라면 bucket에 이를 넣는다. 

# 해시테이블에서 key값으로 value 값을 찾는다

  def get(self,key):
    index=self.hash_func(key)

    bucket = self.table[index]

    for kv in  bucket : # bucket을 돌면서
      if kv[0] == key: # key값과 동일한 kv를 찾으면 
        return kv[1] # 그 key에 대응하는 value값을 return

    return "없는 메뉴입니다." # bucket에 key 값이 없을 때 해당 문구를 반환

cafe=Cafe(6) # 메뉴 6개 

cafe.put('아메리카노',4700)
cafe.put('카페 라떼',5200)
cafe.put('말차 라떼',6100)
cafe.put('레모네이드',5500)
cafe.put('초콜릿 크림 칩 프라푸치노',6200)
cafe.put('자몽 허니 블랙 티', 5900)

## 가격 수정
cafe.put('아메리카노',5000)

## 가격 조회
print("말차 라떼 가격:", cafe.get('말차 라떼'))  
print("아메리카노 가격:", cafe.get('아메리카노'))  

# 없는 메뉴 검색
print('딸기 라떼 가격:',cafe.get('딸기 라떼'))

# 현재 해시테이블 내부 상태 확인

print("== 현재 해시테이블 상태 체크 ==")

for i, bucket in enumerate(cafe.table): 
  print(f'{i}번 bucket : {bucket}')

 

실행결과