해시테이블과 성능에 대한 고뇌

김재만·2022년 1월 20일

많이 들어본 해시(Hash) 그리고 해시테이블

분명 해시는 어디서 많이 들어본 단어다. 해시태그 때문인지, 래퍼 해쉬스완 때문인지도 모르겠지만 말이다. 암호화폐가 상당히 이슈가 되는 현재에, 그리고 컴퓨터의 용량 자체보다 처리속도가 중요해진 현대에 해시는 더욱 일반적으로 사용되는 단어가 될 것으로 보인다.

그렇다면 해시는 무엇일까. 해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다. 어떤 데이터가 가진 특정 키값을 받아, 밸류값을 호출할 수는 있으나 밸류값을 가지고는 원하는 키 값을 호출할 수 없는 데이터 교환 형태에 많이 활용된다. 일상 생활에서 비슷한 사례를 찾는다면 고객의 개인정보를 통해 객실 넘버와 키를 받을 수 있지만, 객실 넘버와 키로 개인정보를 얻을 수 없는 것과 유사하다.(호텔이 고객의 정보를 지켜준다면!)

해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실되는데, 이러한 특성 때문에 하나의 원 데이터는 하나의 해시값만 가진다. 하나의 해시값을 만들어 낼 수 있는 원본 데이터는 매우 많아서, 해시값만 가지고는 아무리 용을 써도 이미 뭉개져버린 원문을 복원해해는 것은 불가능하다. 때문에 비밀번호, 전자서명, 전자투표, 전자상거래같은 방면에 활용되고 있다.

해시테이블은 이러한 해시함수와 해싱의 특징을 활용해, 특정 값에 최단으로 접근할 수 있는 형태로 구축된 자료구조다. 자료구조를 순회하면서 특정 값을 찾는 형태가 아니라, 이미 저장돼있는 키 값을 활용해야 접근 가능한 자료구조이기도 하다.

해시테이블의 장점과 단점

해시테이블의 구조는 사전의 구조와 유사합니다. 이와 연관지어 해시테이블이 갖는 장점과 단점을 알아보겠습니다.

장점
- 특정 정보를 확인하기위한 값을 활용해서 해당위치에 정보를 저장하거나, 요청하거나, 삭제합니다. 정보 처리 비용이 매우 효율적이기 때문에, 데이터의 크기에 상관없이 권장할만한 자료구조입니다.
- 해시테이블의 핵심인 해시함수는 데이터의 크기에 상관 없이, 고정된 크기의 값으로 매핑하여 손쉽게 매핑값들을 관리할 수 있습니다.
단점
- 키 값이 다르더라도, 해시함수를 거친 매핑값은 중복될 수 있습니다. 마치 사전에서 같은 글자로 기재된 동음이의어와 같습니다. 또는, 호텔에서 동시에 전화가 온 손님에게 배정한 방의 번호가 겹친 경우, 조금이라도 늦은 손님을 다른 방에 배정하는 것과도 유사합니다. 사전에서 이런 동음이의어를 나름의 순서에 맞춰 숫자를 매겨 주욱 나열하는 형태나 호텔에서 손님을 다른 방으로 배정하는 것처럼, 자료구조인 해시테이블도 비슷한 해결법을 취합니다.
  
  사전처럼 같은 매핑값에 일정한 순서를 가진 구조를 형성하는 해결방식을 개별 체이닝이라고 합니다.
  
  한편, 호텔의 해결법처럼, 키값과 직접적인 연관이 없는 매핑값이 가리키는 데이터의 빈 공간에 데이터를 저장하는 해결방식을 오픈 어드레싱이라고 합니다.
- 위와 같은 문제점의 근본적인 원인은 저장공간의 유한함입니다. 저장공간의 유한함은 물론 자원의 문제일 수도 있지만, 무지막지하게 큰 사전이나 호텔을 생각하면 효율 외적인 관리의 문제에서 권장하기 어려운 형태가 될 수 있습니다. 때문에, 데이터에 맞춘 적절한 테이블 크기설정이 중요합니다.
  
  해시테이블은 때문에 공간 효율을 표현하는 로드팩터(데이터저장공간수/테이블전체공간수)라는 값을 가집니다.

해시테이블의 구조와 기능

해시 테이블의 구조는 입구와 출구가 없이, 오로지 키 값 만으로 정보를 활용합니다. 아래는 해시테이블은 파이썬을 활용하여 데이터를 넣는 put(키값 중복시 업데이트), 조회하는 get, 삭제하는 remove를 기능으로 갖는 형태를 구현했습니다. 또한, 아래 구현한 해시테이블은 개별 체이닝(사전)형태의 해시테이블입니다.

1. 컬렉션 호출과 클래스 ListNode 생성

# 키:밸류 형태의 구현을 위한 defaultdict 활용
import collections

# 키, 벨류값을 가지면서 개별체이닝을 위해 노드 클래스를 생성
class ListNode:
                      # key, value값 초기화(None)
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

일반적인 상황에서 키, 벨류값은 인자로 받을 것이기에 self.key, self.value로 접근할 수 있지만, 값이 없는 상황에 key와 value가 None인 노드를 넣어주기 위해 초기값을 설정해줍니다. next의 경우 체이닝 되는 경우에만 함수를 통해 값을 넣어주게 됩니다.

2. 클래스 HashTable 생성

# 해시테이블 클래스 생성
class HashTable :
    def __init__(self):
        # 공간 크기를 1000으로 고정하여 생성
        self.size = 1000
        # 테이블의 기본 구조를 collections의 defaultdict로 형성
        self.table = collections.defaultdict(ListNode)

적당히 큰 사이즈와 키-벨류 구조인 defaultdict를 활용했습니다.

3. 클래스 안에 함수 선언 - 1 :put

    # put함수 선언. key와 value를 인자값으로 받음
    def put(self, key, value):
        # index에 매핑값(key값으로 계산한 해쉬함수의 결과값)저장
        index = key % self.size
        
        # 해당 인덱스에 저장된 값이 없는 경우, 리스트노드를 생성하여 저장
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return
        
        # 해당 인덱스에 저장된 값이 있는 경우,
        # self.table[index]에 관련한 계산만 진행되므로 p에 저장하여 계산
        p = self.table[index]
        # index가 가리키는 노드가 있으면 계속 반복
        while p :
        
            # 만약 같은 키 값을 가진 데이터가 이미 존재하는 경우, p.value값을 새 value 값으로 갱신한다.
            if p.key == key:
                p.value = value
                return
                
            # 반복할 때마다 p = p.next로 갱신하기 때문에, p.next가 None이라는 것은 p가 체이닝의 마지막 노드를 가리킨다는 것. 마지막 노드에 도착하면 반복을 멈춤.
            if p.next is None:
                break
            # 반복할 때마다 p 갱신
            p = p.next
        # 반복이 끝나면 새 노드값 생성하여 마지막 노드인 p의 next 값으로 연결
        p.next = ListNode(key, value)

해시 테이블의 경우, 인덱스가 가리키는 값의 여부에 따라 없는경우, 있는 경우를 가려 작성한다. put의 경우 가리키는 값이 없으면 바로 저장, 있는 경우는 해당 체이닝의 끝을 찾아 저장한다.

4. 클래스 안에 함수 선언 - 2 : get

    # 함수선언. key값만 인자로 받음
    def get(self, key):
        # index에 맵핑값 저장
        index = key % self.size
        
        # index값이 가리키는 값이 없는 경우 -1을 반환
        if self.table[index].value is None:
            return -1
        
        # p = p.next로 갱신하며 반복
        p = self.table[index]
        while p:
            # 만약 key값과 같은 값을 가진 p.key를 찾으면, p의 value값을 반환
            if p.key == key :
                return p.value
            p = p.next
            
        # 반복하고도 일치하는 key값을 찾지 못한 경우 -1을 반환
        return -1

get의 경우 가리키는 값이 없으면 -1을 반환하고, 있으면 해당 value값을 반환한다. 가리키는 값이 없는 경우는 해당 인덱스 자체가 없는 경우와 일치하는 인덱스는 있으나 키 값이 다른 두 가지 경우를 나누어 작성했다.

5. 클래스 안에 함수 선언 - 3 : remove

    # 함수선언. key값만을 인자로 받는다.
    def remove(self, key)
        # 해싱
        index = key % self.size
        
        # 해당 인덱스가 가리키는 값이 없으면 아무것도 반환하지 않는다.
        if self.size[index].value is None:
            return 
            
        # 만약 인덱스의 첫 번째 노드일 때
        p = self.table[index]
        if p.key == key:
            # 해당 노드를 지운다. self.table[index] 값에 next가 없는 경우 빈 노드를 생성하고, 있으면 next로 갱신한다.
            self.table[index] = ListNode() if p.next is None else p.next
            return
            
        # 찾는 값이 체이닝 된 노드인 경우
        # 찾는 값의 전, 후 값을 이어줘야 하기 때문에 prev 값을 선언하고, p값보다 한 칸 앞의 노드로 갱신한다.
        prev = p
        while p:
            # 만약 해당 키 값을 찾으면
            if p.key == key:
                # prev의 next값을 p.next로 연결한다.
                prev.next = p.next
                # 특정 값을 반환하지 않으며, 반복문과 함수를 종료한다.
                return
                
            # 반복할 때 마다, prev에는 p, p에는 p.next를 갱신한다.
            prev, p = p, p.next

좋은 해시함수의 특징
- 해시 함수 값 충돌이 최소
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높음
시간복잡도
- Insertion O(1)
- Deletion O(1)
- Search O(1)
  단, 개별 체이닝의 경우 충돌하여 체인길이가 m일 때, 최악의 경우 O(m) 나올 수 있다.