휴대폰에서 전화번호 검색을 위해 상대방의 이름을 쳐서 검색한 적이 있으신가요?
이 때, 내부에는 효율적인 검색을 위해 HashTable 를 이용하여 전화번호를 찾습니다.
이 글에선 과연 HashTable는 무엇인지, 어떤 원리가 숨어있는 지를 알아보겠습니다.

참조: HashTable은 기본적인 DS로 다른 알고리즘이나 DS에 정말 많이 쓰입니다.

HashTable은 어떤 기능을 하나요?

어떤 값을 빠른 시간에 Search하거나 값을 Update를 할 수 있는 자료 구조입니다.
자세히 이야기하면, 키(key)를 통해 얻고자 하는 값에 접근 하는 자료구조입니다.

여러 기능 중 HashTable의 Search의 효율을 예와 함께 설명을 드리겠습니다.

문제 제시:

한 시골 학교에 6명의 학생이 있는 반과 그 반의 선생님이 있습니다.
어제 수학 시험을 쳤고 선생님은 각 학생의 수학 점수 기록을 가지고 있습니다.
이 중 ‘재석’이라는 학생이 자신의 수학점수가 궁금해서 선생님을 찾아 왔습니다.

위는 수학점수 기록이고, 선생님은 어떻게 효율적으로 ‘재석’의 수학 점수를 알 수 있을까요?
※스스로 한 번 방법을 생각해봅시다!

Brute-force하게 해봅시다.

단순하게 위에서부터 학생의 이름을 한 명씩 비교해서 찾을 수 있습니다.
그 과정은 아래와 같습니다.

우리가 찾고 싶은 건 ‘재석’ 학생이지만 데이터의 첫 번째 칸은 ‘동훈’ 학생입니다.
따라서 다음으로 넘어갑니다.

위의 경우에도 ‘재석’ 학생의 데이터가 아닙니다.
이처럼 이름이 찾는 이름이 아닐 경우에는 계속 다음 데이터로 넘어갑니다.

마지막에 비로소 재석의 이름에 해당하는 데이터를 찾았습니다.

하지만 위 방법으로 진행했을 경우, 최악의 경우 처음부터 모든 데이터를 검사해야 합니다.
심지어 왼쪽처럼 이름을 비교하는 상황에도 시간 cost가 발생합니다.

찾는 과정은 Time-complexity를 보았을 때, 최악의 경우는 O(N*M)입니다.
(이 때 N = 학생 수, M = 학생 이름의 길이)

더 나아가, ‘재석’ 뿐 아니라 다른 학생들도 수학 점수가 궁금해서 찾아오면 어떡할까요?
매 학생이 물을 때마다, 모든 데이터를 체크해야 하고, 이건 굉장히 비효율적입니다.
만약 K명의 학생이 물어본다고 가정하면 시간 소모는 O(N*M *K)가 됩니다.

따라서 물어보는 학생이 많으면 많을 수록 소모되는 시간은 기하급수적으로 커집니다.
이 비효율성을 줄이고자, 다음과 같은 HashTable이라는 자료구조가 고안되었습니다.

HashTable:

이 문제를 해결하는 아이디어는 Hashing와 Dynamic-array의 마법을 이용하는 것입니다.
사실, 이 두 가지의 비밀 뒤에는 수학, 통계, LUT 등 여러가지 고려할 것이 많습니다.
하지만, 이 글에서는 HashTable의 전체적인 구조에 관해서만 간단히 알아보겠습니다.

-참조 Dynamic-array의 마법을 알고 싶으면 Dynamic-array
-참조 Hashing의 마법을 알고 싶으면 Hashing

전체적인 구조:
※ 쉬운 이해를 위해, 몇 개의 전제 조건을 설정하겠습니다.

10개 slots의 slots-list로 시작
사용자 임의의 한글-LUT(lookupTable)
사용자 임의의 String-Hash 함수
Birthday-Paradox는 신경 쓰지 않음
잘못된 Hashing 함수로 인한 Duplicate-key는 신경 쓰지 않음

초기의 HashTable:

위는 아직 아무런 Key와 데이터가 없는 초기의 HashTable을 만든 모습입니다.
HashTable은 Keys - Hash - slots의 구조로 이루어져 있다고 생각하면 됩니다.
slots은 초기 사이즈가 10인 Dynamic-array로 되어있습니다.
Hashing 함수는 다음과 같은 두 단계로 이루어져있습니다.

String의 각 글자의 값을 합칩니다.
합친 값을 slots의 갯수로 %(Modulo)를 합니다.

Key를 받으면, Hashing이 Key를 Slots의 알맞은 index의 값으로 바꾸어 줍니다.
오른쪽은 임의의 한글-LUT로 Hashing의 값을 구할 때 도와줍니다.

HashTable 데이터를 넣는 과정:

아래는 ‘동훈’의 데이터를 넣는 과정입니다.

데이터를 넣는 과정은 크게 5단계로 이루어 집니다.

‘동훈’ 학생의 이름이 Key로 들어갑니다.
‘동훈’ 각각 ‘동’, ‘훈’에 해당하는 Decimal 값을 LUT에서 찾습니다.
LUT에서 찾은 값을 이용해 Hash-function에서 두 가지 단계로 처리합니다.
나온 값 3에 해당하는 Index를 가진 slot에 접근합니다.
해당하는 index의 slot에 ‘동훈’의 점수인 15를 넣습니다.

아래는 ‘명수’의 데이터를 넣는 과정입니다.

HashTable에 데이터를 다 넣은 상태:

아래는 모든 학생의 데이터를 다 넣고 난 후 HashTable의 모습입니다.

HashTable 데이터를 찾는 과정:

아래는 ‘재석’ 학생의 데이터를 찾는 과정입니다.

데이터를 찾는 과정은 데이터를 넣을 때의 과정과 비슷합니다.

Hash-func을 통해서 ‘재석’의 Index 값인 4를 찾는다.
index가 4인 slot에 접근한다.
index가 4인 slot에 저장된 데이터인 ‘100’을 도출한다.

아래는 Keys에 없는 ‘홍철’ 학생의 데이터를 찾는 과정입니다.

만약 기존의 키에 없었던 ‘홍철’이라는 학생 데이터를 찾으려고 하면
위처럼 Hash-func에 의해 index가 1인 slots에 접근하게됩니다.
하지만, index가 1인 slot에는 데이터가 없고 따라서 Null을 Return 합니다.

실제론, Birthday-paradox 같은 문제로 Collision이란 것이 생깁니다.
대처하기 위한 전략으론 Open-address나 separate-channing 등 몇 가지가 있습니다.
더 자세히 알아보기

HashTable의 평가:

일단 data를 Insert할 떄는 brute-force 방법보다 더 걸릴 수 밖에 없습니다.
각 데이터는 Hashing을 거쳐 저장되기 때문에 Hashing 하는 시간만큼 더 걸리는 것이죠.

Big-O notation으로 따지면, O(N*M)의 시간이 걸립니다.
(이 때, N = 넣고자 하는 학생 수, M = 각 학생의 이름 길이)
넣을 때의 시점에선 이전 방법보다 효율성이 좋다고는 하기 어려울 거 같습니다.

하지만, 물어보는 학생의 경우, 즉 쿼리를 처리할 때는 이전보다 훨씬 좋습니다.
이전에는 매번 가지고 있던 모든 데이터를 체크해야 했지만 이번에는 그렇지 않습니다.
각 학생은 자신의 이름을 Hash-func에만 넣기만 하면 바로 Index를 얻을 수 있습니다.
이 때 얻은 Index의 slot은 Dynamic-array의 마법으로 바로 접근할 수 있습니다.

Big-O notation으로 보면, O(K*M)의 시간이 걸립니다.
(이 때, K = Query의 수, M = 각 Query 학생의 이름 길이)
이 시간이 걸리는 이유는 각 Query들은 Hash-func 과정을 해야하기 때문에 어쩔 수 없이
Hashing에 걸리는 시간인 O(M)을 소모할 수 밖에 없습니다. 하지만 Search하는 시간은
O(1)으로 Linear하게 바로 원하는 값에 접근할 수 있습니다.
따라서, 이전보다 훨씬 좋은 Query 처리 속도를 가진다고 할 수 있습니다.

HashTable과 관련된 용어:

구현 언어에 따라 또는 구현 방법에 따라 또는 잠깐 언급한 Collision 전략에 따라
관련 용어들은 조금씩 다릅니다. 자주 쓰이는 것들로 HashMap, Map, Dictionary가 있습니다.
하지만 핵심은 Key-Value로 pair이 된 Collection이라는 것에서 같습니다.

참고로, Python에서는 Dictionary, Set이 대표적인 HashTable로 구현된 DataType입니다.

Python에서는 Set이 Value가 Binary인 HashTable로 되어있습니다.

실제 구현 by Python

구현 아이디어:

Dynamic-array
Hash

Code:

import os
import sys

# 한글-LUT
LUT = {'동': 1, '훈': 2, '명': 3, '수': 4
        '형': 5, '돈': 6, '준': 7, '하': 8
        '광': 9, '희': 10, '재': 11, '석': 13
        '홍': 14, '철': 17}

class HashTable:

  def __init__(self):
    self.Num_of_Slots = 10
    self.slots = [None]*10 # dynamic array

  # Hash-fun
  def _hash(self, name):
      global LUT
      index = 0
      #proc-1
      for chr in name:
        index += LUT[chr]
      #proc-2
      index %= self.Num_of_Slots

      return index

  def insert(self, name, data):
    index = self._hash(name)
    self.slots[index] = data

  def search(self, name):
    index = self._hash(name)
    value = self.slots[index]

    if value: # if it is not None
      return value
    else:
      return None