나의 개발일지 TIL(Today I learned) - 자료구조와 알고리즘(해시)

Today I learned

• 해시(hash)

 

해시(hash)

해시(hash) 구조란, 키(key)와 데이터(value)가 쌍으로 이루어진 데이터 구조이다

해시 구조에서는 키(key)를 이용하여 데이터(value)를 빠르게 찾을 수 있는 장점이 있다

우리는 파이썬에서 딕셔너리를 학습하고 사용해 본 적이 있다

딕셔너리가 바로 해시 구조이다!

 

해시와 관련된 영어들을 알아보자

키(key): 해시 함수의 input이 되는 고유한 값

해시(hash): 임의의 값을 고정 길이로 변환하는 것

해시 테이블(hash table): 키(key) 값의 연산에 의해 직접 접근이 가능한 데이터 구조

버킷(bucket), 슬롯(slot): 해시 테이블(hash table)에서 하나의 데이터가 저장되는 공간

해시 함수(hashing function): 키(key) 값에 대해 연산을 통해 데이터(value) 위치를 찾는 함수

hash value, hask address: 키(key) 값을 이용해 해시 함수(hashing function)를 연산하여 value를 알아내고

이를 기반으로 해시 테이블(hash table)에서 해당 키(key)에 대한 데이터 주소(address)를 찾을 수 있다

 

만약 해시 값 혹은 인덱스가 중복되어 충돌이 일어난다면?

체이닝과 개방 주소법 방법으로 해결할 수 있습니다.

연결리스트를 이용한 체이닝

class LinkedTuple:
    def __init__(self):
        self.items = []

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

    def get(self, key):
        for k, v in self.items:
            print(k, v)
            if k == key:
                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)

        return

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

        return self.items[index].get(key)

dict = LinkedDict();
dict.put("asde", "test1")
dict.put("bcde", "test2")
dict.put("bcd1", "test3")
dict.put("bcd4", "test4")
dict.put("cse4", "test5")
dict.get("bcd4")

 

문제를 풀면서 학습해보자

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


def get_absent_student(all_array, present_array):
    students_dict = {}

    for key in all_array:
        students_dict[key] = True

    for key in present_array:
        del students_dict[key]

    for key in students_dict.keys():
        return key


print(get_absent_student(all_students, present_students))

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