[자료구조] 해시 (Hash)

해시란?

데이터를 저장하거나 탐색할 때, 처음부터 끝까지 순차적으로 탐색하는 것은 비효율적 입니다. 그렇다면 위치를 탐색할 필요 없이 바로 데이터를 찾으려면 어떻게 해야할까요? 이럴 때 사용하는 자료구조가 "해시"입니다.

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장합니다. 그리고 이 키를 활용해서 데이터 탐색을 빠르게 합니다. 우리 일상에서도 찾아볼 수 있는데, 엑셀의 Default로 명시된 행번호가 바로 인덱스이고 값의 위치 정보라고 이해할 수 있습니다.

 

 

 

해시 충돌 문제

해시 함수가 변환한 값이 충돌이 발생하기도 하는데 "윤아", "유리"라는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일하게 나타나는 상황을 의미합니다. 그래서 해시를 구현할 때 이 부분을 고려해야 합니다.

 

그렇다면 해시 함수를 어떻게 구현할까요?

구현하면서 이해하는데 빠르기 때문에 자주 사용하는 해시 함수인 나눗셈법과 곱셈법을 파이썬으로 직접 구현해보았습니다. 실행 해보시면 아시겠지만 테스트 코드를 실행해보면 나눗셈법의 해싱 결과가 충돌이 일어나는 것을 보실 수 있을 것 입니다. 일부러 충돌 케이스를 구현했는데, 나눗셈법을 사용할 때 충돌 가능성이 높다는 것을 보여주고 싶었습니다.

# 해시 함수 구현 및 출력 클래스

class HashTable:
   def __init__(self, size):
      self.size = size            # 해시 테이블 크기
      self.table = [None] * size  # 테이블 초기화
   
   # 나눗셈법을 사용한 해시 함수
   def division_hash(self, key):
      return key % self.size  # key를 size로 나눈 나머지를 해시 값으로 사용
   
   # 곱셈법을 사용한 해시 함수
   def multiplication_hash(self, key):
      A = 0.6180339887        # 황금비율을 이용한 계수
      return int(self.size * ((key * A) % 1))  # 소수 부분을 활용한 해싱
   
   # self.table에 데이터 삽입 (나눗셈법)
   def insert_division(self, key, value):
      index = self.division_hash(key)
      self.table[index] = value

   # self.table에 데이터 삽입 (곱셈법)
   def insert_multiplication(self, key, value):
      index = self.multiplication_hash(key)
      self.table[index] = value
   
   # 데이터 검색
   def get(self, key, method='division'):
      if method == 'division':
         index = self.division_hash(key)
      else:
         index = self.multiplication_hash(key)
      return self.table[index]

   # 해시 테이블 출력
   def display(self):
      for i, value in enumerate(self.table):
         print(f'Index {i}: {value}')

# 테스트 코드

# 테이블 사이즈
ht = HashTable(10)

# 나눗셈법 해싱
ht.insert_division(25, "Apple")
ht.insert_division(35, "Banana")
ht.insert_division(15, "Cherry")

print("--- Hash Table (Division Method) ---")
ht.display()

# 곱셈법 해싱
ht.insert_multiplication(25, "Dog")
ht.insert_multiplication(35, "Elephant")
ht.insert_multiplication(15, "Fox")

print("\n--- Hash Table (Multiplication Method) ---")
ht.display()


--- Hash Table (Division Method) ---
Index 0: None
Index 1: None
Index 2: None
Index 3: None
Index 4: None
Index 5: Cherry
Index 6: None
Index 7: None
Index 8: None
Index 9: None

--- Hash Table (Multiplication Method) ---
Index 0: None
Index 1: None
Index 2: Fox
Index 3: None
Index 4: Dog
Index 5: Cherry
Index 6: Elephant
Index 7: None
Index 8: None
Index 9: None

 

 

충돌이 발생하는 부분은 어떻게 해결해야 할까요?

실제 구현에서는 충돌을 해결하기 위한 로직을 사용해야 합니다. 대표적으로 체이닝 방식의 해시 테이블을 구현해보면 좋을 것 같습니다. 아래 코드 출력 결과를 보시게 되면 아마 인덱스 한 곳에 여러개의 key, value 값이 들어가 있는 것을 볼 수 있습니다. 데이터의 누락(충돌) 없이 테이블에 데이터가 반영되었습니다.

# 체이닝(Chaining) 방식의 해시 테이블 구현
class ChainingHashTable:
   def __init__(self, size):
      self.size = size                        # 해시 테이블 크기
      self.table = [[] for _ in range(size)]  # 체이닝을 위한 리스트 초기화
   
   # 나눗셈법을 사용한 해시 함수
   def division_hash(self, key):
      return key % self.size  # key를 size로 나눈 나머지를 해시 값으로 사용
   
   # self.table에 데이터 삽입 (나눗셈법)
   def insert_division(self, key, value):
      index = self.division_hash(key)
      
      # 동일 키가 이미 존재하면 값을 업데이트
      for pair in self.table[index]:
         if pair[0] == key:
            pair[1] = value
            return
      
      # 동일 키가 아니면 새로운 (key, value) 추가
      self.table[index].append([key, value])

   # 데이터 검색
   def get(self, key):
      index = self.division_hash(key)
      for pair in self.table[index]:
         if pair[0] == key:
            return pair[1]
      return None

   # 해시 테이블 출력
   def display(self):
      for i, bucket in enumerate(self.table):
         print(f'Index {i}: {bucket}')

# 테스트 코드
ht = ChainingHashTable(10)  # 크기가 10인 해시 테이블 생성

# 데이터 삽입
ht.insert_division(25, "Apple")
ht.insert_division(35, "Banana")
ht.insert_division(15, "Cherry")
ht.insert_division(25, "Grapes")  # 같은 키(25)의 값 업데이트

# 해시 테이블 출력
print("--- Hash Table (Chaining Method) ---")
ht.display()

# 데이터 검색
print("\nSearch Key 25:", ht.get(25))
print("Search Key 35:", ht.get(35))


--- Hash Table (Chaining Method) ---
Index 0: []
Index 1: []
Index 2: []
Index 3: []
Index 4: []
Index 5: [[25, 'Grapes'], [35, 'Banana'], [15, 'Cherry']]
Index 6: []
Index 7: []
Index 8: []
Index 9: []

Search Key 25: Grapes
Search Key 35: Banana

 

나눗셈법과 곱셈법 외에도 해시 함수는 다양하게 있을텐데, 중요한 것은 적재적소 잘 사용하는 거겠죠....ㅎ

아직 부족하지만 다양한 케이스에 적용해보면서 감을 익혀가야 하겠습니다.