알고리즘 3주차 - 해쉬

해쉬

해쉬 테이블이란?

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

• 해시 함수를 사용하여 색인(index)을 버킷(bucket), 슬롯(slot)의 배열로 계산

• 데이터의 저장과 검색이 아주 빠르게 진행된다.

• 파이썬에서는 딕셔너리 = 해쉬 테이블

딕셔너리

• 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 매우 빠름

• 찾는 데이터에 대해 배열을 전부 다 둘러보지 않고도 바로 값을 조회할 수 있는 자료구조

• 딕셔너리는 내부적으로 배열을 사용

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

• 이와 같은 구조에서 해쉬 함수를 이용하여 저장과 검색을 진행

해쉬 함수

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

    def put(self, key, value):
        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"))

• 랜덤의 값을 생성하고 이를 배열의 크기만큼 % 연산 함으로써 0 ~ 배열 크기 -1 만큼의 인덱싱을 해줄 수 있다.

• 하지만 여기서 문제점은 인덱스 값이 동일해질 때가 있다는 것이다. 이를 충돌이라고 한다.

충돌

• 똑같은 위치에 value를 넣기에 이전 값이 덮어 씌워져버리는 현상이 ㅂ

충돌 해결법

링크드 리스트: 링크드 리스트를 만들어서 추가해서 노드로써 이어주게 만듬. 인덱스가 충돌이 나더라도 데이터 손실에 대한 걱정이 없음. 키도 같이 저장해주어야 함.

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

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            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].add(key, value)

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

• 이와 같은 기법을 체이닝(chaining) 기법이라고 함

• 각 배열에 링크드 리스트를 연결함으로써 동일한 키로 저장되려고 한다면 기존 아이템의 뒤에 아이템으로 만들어 저장

• 키가 도달하게 되면 키에 대한 링크드 리스트를 조회해서 키가 가진 값을 리턴

배열에 다음 공간에 넣기

💡

특정한 값의 해쉬 값이 3이 나와서 items[3] 에 들어갔다는 가정. 다음값 의 해쉬 값이 동일하게 3이 나왔다면 그 다음 items[4]를 확인하고 비었다면 그곳에 넣고 아니라면 계속 다음 빈 주소를 찾아서 넣는 방식. 개방 주소법(Open Addressing) 이라고 함

정리

💡

해쉬 테이블(Hash Table)은 "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조입니다. 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수입니다. 해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다. 그렇기 때문에 즉각적으로 데이터를 찾고, 추가할 수 있는 것 입니다. 만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면? 체이닝과 개방 주소법 방법으로 해결할 수 있습니다! # 출처: 스파르타코딩클럽

문제

❓

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

# 코드 스니펫

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


def get_absent_student(all_array, present_array):
    # 구현해보세요!
    return


print(get_absent_student(all_students, present_students))

• 여기서 이중 for문을 사용한다면 O(N^2)의 매우 비효율적인 구조가 되기에 해쉬를 사용

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


def get_absent_student(all_array, present_array):
    student_dict = {}
    for key in all_array:
        student_dict[key] = True

    for key in present_array:
        del student_dict[key]

    for key in student_dict.keys():
        return key


print(get_absent_student(all_students, present_students))

• 해당 함수의 시간복잡도는 O(N) + O(N) = O(N)

• 하지만 반대로 공간의 경우는 많이 사용하므로 공간복잡도도 O(N) 만큼 걸림

해쉬는 시간을 아낄수 있지만 반대로 공간을 사용하는 자료구조 라는 것을 알 수 있음