[자료구조] 해시 테이블(Hash Table)이란?

이거 아닙니다

Hashing이란?

 

영어 사전에 hash를 검색하면 다음과 같은 뜻이 나온다.

실제로 처음에 해쉬라는 것을 들었을 때, 맨 처음 떠올렸던 것이 햄버거에 들어가있는 그 감자 아닌가? 라고 생각하기도 했다.

하지만, 자료구조에서의 해싱(Hashing)은, 각각의 데이터를 고유한 숫자 값으로 표현하고(임의의 값을 고정된 길이로 변환), 이를 이용하여 특정 데이터의 존재 여부를 확인하거나 데이터를 추출하는 작업을 의미한다.

이러한 해싱(Hashing)의 과정에는, 해시 함수(Hash Function)와 해시 테이블(Hash Table)이 사용된다.

 

해시 함수(Hash Function)

해시 함수(Hash Function)란, 주어진 데이터(Key)를 고유한 숫자 값인 해시 값(Hash Value)으로 표현해주는 함수이다.

키(Key)란, 해시 함수의 입력 부분이며, 입력 데이터 자체이거나 입력 데이터를 구분하는 값을 의미하며,

해시 값(hash value)란, 해시 함수의 출력 부분이며, 이러한 해시 값은 뒤에 후술할 해시 테이블(hash table)의 인덱스가 된다.

 

이러한 해시 함수를 통해 데이터를 고유한 숫자 값으로 변환하고, 해시 테이블에 접근하여 데이터를 조회하거나, 추출하게 된다.

 

해시 테이블(Hash Table)

해시 테이블(Hash Table)은 데이터가 저장되는 곳으로, 해시 함수를 통해 산출된 해시 값(Hash value)을 인덱스로 하여 해당 데이터를 저장한다.

 

솔직히 처음 해시 테이블을 접했을 때, 헷갈리는 부분이 없지 않았다. 그럴 때 도움이 된 것이 그림과 같은 시각 자료였는데, 아래의 그림을 같이 살펴보며 해시 테이블을 이해해보자.

각 과일별 가격을 저장한다고 가정해보자. 이때, 우리가 해시 테이블에 저장해야하는 값은 각 과일의 가격일 것이고, 이를 구분하는 값인 과일 이름은 키(Key)가 될 것이다.

그러면, 우리는 키를 해시 함수(Hash Function)에 넣는다. 과일 중 바나나를 살펴보자. 바나나를 해시 함수에 넣게 되면 04라는 값이 나온다고 가정해보자. 그러면 바나나라는 키의 해시 값(Hash Value)은 04가 되는 것이다.

이렇게 해시 함수를 통해 산출된 해시 값은 해시 테이블의 인덱스가 된다. 즉, 해시 테이블의 04번 인덱스가 가리키는 곳에는(Hash Table[4]) 바나나의 가격인 1800원이 저장되는 것이다.

사과의 경우, 해시 함수를 통해 산출된 해시 값이 02로, 해시 테이블의 02번 인덱스가 가리키는 곳에 사과의 가격인 3000원이 저장된다.

이는 꼭 데이터의 삽입이 아니어도, 추후 데이터를 조회할때도 동일한 원리로 작동한다.

 

그런데, 만약 서루 다른 키가 해시 함수를 통과하면서 같은 해시 값을 가지게 된다면 문제가 발생한다. 해시 테이블의 같은 공간에 두 개 이상의 값을 저장해야할까? 이러한 문제를 아래에서 알아보도록 하겠다.

 

 

해시 충돌(Collision)

위에서 언급한 것처럼, 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써 해시 테이블의 같은 위치에 두 개 이상의 데이터가 저장되려는 현상을 해시 충돌(Collision)이라고 한다. 

이러한 해시 충돌을 해결하는 대표적인 방법으로는 Chaining 기법과, Linear Probing 기법이 있다.

 

Chaining 기법

Chaining 기법은 Open Hashing 기법 중 하나로, 해쉬 테이블 저장공간 이외의 공간을 활용하는 기법이다.

즉, 충돌이 일어나게 되면 해당 인덱스가 가리키는 해쉬 테이블 공간 뒤로 연결 리스트를 사용하여 추가적으로 연결시킨다음 저장한다.

예시를 통해 살펴보도록 하겠다.

위의 예시에서, 사과와 배가 해시 함수를 통해 02라는 같은 해시 값을 가지게 되었다. 그러나, 해시 테이블의 02 부분에는 사과의 가격인 3000원이 이미 저장되어있는 상태인데, 배의 가격은 어떻게 저장할까? Chaining 기법에 따라, 사과 가격 3000원 뒤에 연결 리스트를 사용하여 배 가격을 추가해보자.

다음과 같이, 배의 가격인 3200원을 사과 가격 뒤에 추가로 연결시켜서 저장함을 볼 수 있다.

 

 

Linear Probing 기법

Linear Probing 기법은 Close Hashing 기법 중 하나로, 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법이다.

충돌이 일어나게 되면, 해당 해시 값의 다음 값부터 순회를 시작하여 처음으로 나오는 해시 테이블의 빈 공간에 저장하는 기법이다.

마찬가지로 예시를 통해 함께 알아보자.

아까와 같은 예시이다. 현재 발생하고 있는 사과와 배의 충돌 문제를 Linear Probing으로 해결하면 어떤 형태가 될까?

우선, 중복되는 해시 값인 02 다음 값 03부터 순회를 시작하여 빈 해시 테이블 공간을 찾는다.

여기서는 03이 비어있으니, 03에 배의 가격 데이터를 입력하면 된다.

다음과 같이, 비어있던 공간인 03 부분의 해시 테이블에 배의 가격인 3200원이 저장된 것을 볼 수 있다.

 

 

 

해시 테이블(Hash Table)의 장단점과 주요 용도

해쉬 테이블은 데이터 저장과 검색 속도가 빠르다는 장점이 있다.

해시 테이블로 저장된 데이터들 중에서, 특정 데이터를 검색할 때 나타나는 시간 복잡도는 O(1)이다. (단, Collision이 없는 경우)

이는 동일한 양의 데이터를 저장한 배열에서 특정 데이터를 검색할 때 나타나는 시간 복잡도인 O(n)과 비교하면 매우 우수한 성능을 지닌다.

또한, 해당 키에 대한 데이터가 이미 존재하는지 중복 확인이 쉽다는 장점이 있다.

 

그러나, 저장 공간이 많이 필요하다는 점과, 여러 키에 해당하는 해시 값이 동일 할 경우, 충돌을 방지하기 위한 별도의 자료구조(연결 리스트, 배열 등등)가 필요하다는 단점도 존재한다.

 

이러한 해시 테이블의 주요 용도는 다음과 같다.

• 데이터의 저장, 삭제, 검색이 많이 필요한 경우 사용
• 중복 확인이 쉽기 때문에 웹 페이지에서 흔히들 볼 수 있는 캐쉬를 구현할 때 사용된다. (중복 확인이 빨라 바뀐 정보가 있는지 없는지를 빠르게 조회할 수 있기 때문이다.)

 

 

 

 

구현해보기

해시 테이블의 구현은 다음과 같다.

 

다음 구현은 hashlib 라이브러리의 SHA-256 해쉬 알고리즘을 사용하였으며, Chaining 기법을 사용하였다.

 

import hashlib


class HashTable:

    def __init__(self):
        # 해시 테이블 0으로 초기화
        self.hash_table = [0 for i in range(8)]


    # 문자열을 정수로 바꿔주어 key가 되게끔 함
    def get_key(self, data):
        # SHA-256 알고리즘 사용
        hash_convert = hashlib.sha256()
        hash_convert.update(data.encode())
        # 16진수로 return
        return int(hash_convert.hexdigest(), 16)


    # 간단하게 나머지를 이용한 해시 함수 구현
    def hash_function(self, key):
        return key % 8

    # 데이터를 해시 테이블에 저장하는 함수
    def save(self, data, value):
        # 키 생성
        key = self.get_key(data)
        # 생성된 키를 해시 함수에 투입
        hash_value = self.hash_function(key)

        # 해시 테이블의 해당 해시 값 부분이 비어있지 않으면(초기화한 값 0이 아니면)
        if self.hash_table[hash_value] != 0:
            for index in range(len(self.hash_table[hash_value])):
                # 한 hash address 안에 리스트가 있고, 그 리스트 안에는
                # key와 value값으로 이루어진 리스트가 또 존재함
                # ([key, value]를 요소로 가지는 연결 리스트)

                # 해시 값이 같을 때, chaining 기법으로 연결 된 연결 리스트를 순회하다가
                # key값도 같은 요소가 있을 시 해당 key의 value값 update
                if self.hash_table[hash_value][index][0] == key:
                    self.hash_table[hash_value][index][1] = value
                    return

            # 해시 값이 같을 때, key값이 같은 요소가 없었으면
            # 해당 해시 값을 인덱스로 하는 해시 테이블에 [key, value]를 요소로 하는 연결 리스트 추가
            self.hash_table[hash_value].append([key, value])

        # 해시 테이블의 해당 해시 값 부분이 비어있으면(초기화한 값 0이면)
        else:
            # [key, value]를 요소로 하는 연결 리스트 추가
            self.hash_table[hash_value] = [[key, value]]

    # 해시 테이블의 데이터 조회하는 함수
    def read(self, data):
        # 키 생성
        key = self.get_key(data)
        # 생성된 키를 해시 함수에 투입
        hash_value = self.hash_function(key)

        # 해시 테이블의 해당 해시 값 부분이 비어있지 않으면(초기화한 값 0이 아니면)
        if self.hash_table[hash_value] != 0:
            for index in range(len(self.hash_table[hash_value])):
                # 해시 테이블의 해당 해시 값 부분에 key값도 같은 요소가 있으면
                # 해당 key값의 value값 return
                if self.hash_table[hash_value][index][0] == key:
                    return self.hash_table[hash_value][index][1]
            return None

        # 해당 해시 값 부분에 데이터가 들어가 있지 않으면
        # 데이터가 없는 것이기 때문에 none값 return
        else:
            return None

다음과 같은 결과를 볼 수 있다.