해시(Hash)

해시란?

해시, 해시 테이블, 해쉬 등으로 불리는 이 자료구조는

컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다. 

 

해시 테이블의 특징

• 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
• 데이터를 다루는 기법 중에 하나로 '키'와 '데이터'를 저장함으로써
  즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용한다.
  한줄로 요약하자면 데이터의 검색과 저장이 아주 빠르게 진행된다. ex) 파이썬의 딕셔너리

 

* 여기서 이 파이썬의 딕셔너리가 내부적으로는 배열을 사용하는데 어떤식으로 사용되는지 알아보자

'fast'와 'slow'의 값인 '빠른'과 '느린'이 배열 어딘가에 있다고 치자.

그 인덱스를 몇번에 넣어야 하는지, 몇번에서 찾아야 하는지 어떻게 알 수 있을까?

-> 바로 해시 함수라는걸 이용한다.

 

해시 함수(Hash Function)

해시 함수는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해시값을 출력하는 함수이다.

파이썬에서 hash(object)를 제공하고 있기 때문에 바로 사용해볼 수 있다.

hash('fast')
# -6945650989697689412
hash('slow')
# -5094026523457299975

이상한 숫자가 출력되는데 이걸 배열의 길이로 나눈 나머지 값을 쓰면 된다.

예를 들어 배열의 길이가 8이라면 8로 나눈 나머지는 항상 0~7이기 때문에

무조건 배열 내부의 인덱스로 연결될 것이라는 걸 알 수 있다.

items = [None] * 8
items[hash('fast') % 8] = '빠른'
items  			# [None, None, None, None, '빠른', None, None, None]
items[hash('fast') % 8]	# '빠른'

이걸 응용해 딕셔너리 클래스를 만들어 보면 다음과 같다.

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        # index = hash(key) % 8
        index = hash(key) % len(self.items)
        self.items[index] = value

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]

my_dict = Dict()
my_dict.put('test', 3)
print(my_dict.get('test'))

 

문제발생 - index 충돌

근데 만약 나중에 해쉬 값이 동일한 값이거나 해쉬 값에 의해 얻어진 인덱스 값이 동일한 값이 들어오면 어떻게 할까?

그렇게 되면 이전 값이 덮어씌워져 버리는 현상이 발생할 것이다. 이를 충돌이 발생했다고 표현한다.

 

이걸 해결하려면 어떻게 해야할까?

 

해결방법

1. 링크드리스트 사용 - 체이닝(Chaining)

# 추가되기 전
key1 -> self.items[7] = [('key', 'test')]
# 같은 인덱스에 값이 추가된 경우
key2 -> self.items[7] = [('key', 'test')] -> [('key2', 'test2')]

이런식으로 연결을 통해 덮어씌워지는 충돌 현상을 피할 수 있다. 

대신, 키를 같이 적어주어 값을 판별할 수 있게 해야한다.

체이닝(Chaining)

각 index마다 LinkedTuple이 존재하는걸 볼 수 있다.

코드로 구현해보자

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):  # .add('key', 'test')
                                # .add('key2', 'test2')
        # [('key', 'test)]
        # [('key', 'test), ('key2', 'test2)]
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:  # k: key, v: value
            if key == k:
                return v

class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        # self.items[index] = value
        # 위 코드가 기존에 했던 구조. 
        # but, 현재 self.items[index]에 LinkedTuple이 들어있다.
        # []
        # [(key, value)]
        self.items[index].add(key, value)
        return

    def get(self, key):
        index = hash(key) % len(self.items)
        # LinkedTuple
        # [(key1, value1), (key2, value2)]
        return self.items[index].get(key)

 

2. 개방 주소법(Open Addressing)

해쉬 값으로 얻은 index에 해당하는 위치에 이미 차있다면

그 다음 index, 그 다음 index... 이런식으로 비어있는 곳을 찾아 value를 넣는 방식을 개방 주소법이라고 한다.

 

예시문제

딕셔너리를 이용해 아래 문제를 풀어보자.

참고로 파이썬에서는 위에서처럼 어렵게 클래스로 딕셔너리를 안만들어도

아래처럼 이미 제공하는 함수를 통해 사용할 수 있다.

# 선언
test = {} # 또는
test2 = dict()
# 값 추가
test['a'] = 123
# 값 제거
del test['a']

# Q. 오늘 수업에 많은 학생들이 참여했습니다. 단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다.
# 모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때, 출석하지 않은 학생의 이름을 반환하시오.

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]

def get_absent_student(all_array, present_array):
    all_dict = {}  # 이렇듯 간단하게 딕셔너리를 선언할 수 있다.

    for student in all_array:
        all_dict[student] = True  # 넣었다는 사실만 중요하기에 간단하게 Boolean 값으로 입력

    for student in present_array:
        del all_dict[student]  # del target으로 해당 딕셔너리에서 간단하게 값을 제거할 수 있다.

    # 출석을 안 한 학생이 한명이라는 가정하에 이렇게 만들었지만 여러명을 체크해야 될 경우
    # 바뀌어야 할 코드.
    for student in all_dict.keys():  
        return student

# 풀이 검증
print(get_absent_student(all_students, present_students))
print("정답 = 예지 / 현재 풀이 값 = ",get_absent_student(["류진","예지","채령","리아","유나"],["리아","류진","채령","유나"]))
print("정답 = RM / 현재 풀이 값 = ",get_absent_student(["정국","진","뷔","슈가","지민","RM"],["뷔","정국","지민","진","슈가"]))

 

정리

위 문제에서 풀이에 대한 시간 복잡도는 O(N)만큼 걸리는 걸 알 수 있는데,

딕셔너리에 학생 수 만큼 공간을 배정하는 등 공간 복잡도를 고려해야 할 상황이 생길 수 있다.

이렇듯 해시 테이블은 시간 복잡도는 극대화할 수 있되, 공간을 대신 사용하는 자료구조라는 것을 기억하자.