해쉬

해쉬

특징

 - 키를 값에 맵핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조

 - key, value system

 - 데이터의 검색과 저장.

 - 파이썬의 딕셔너리

 - 해쉬테이블 (Hash Table) : 키와 데이터를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용.

 - 해쉬 함수(Hash Function) : 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력. 

    * hash()로 사용 가능.

 

 

딕셔너리 구현

 - 해쉬테이블 내부구현 : 키를 해쉬 함수를 통해 임의의 값으로 변경하고 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장

 

put(저장하기)

class Dict:
    def __init__(self):
        self.items = [None] * 8      # 길이 8의 배열을 생성

    def put(self, key, value):
        index = hash(key) % len(self.items)  # hash 함수를 사용하여 해쉬값을 출력, 저장할 인덱스를 구한다.
        self.items[index] = value            # value를 해당 키에 저장
        

my_dict = Dict()
my_dict.put("test", 3)

 

get(가져오기)

    def get(self, key):
        index = hash(key) % len(self.items) # 키값을 해쉬함수를 사용하여 인덱스로 변환
        return self.items[index]   # 해당 인덱스를 가진 원소를 반환
        
print(my_dict.get("test"))

---

충돌

체이닝(Chaining)

 - 해쉬의 값이 같으면 같은 인덱스로 매핑이 되어 데이터를 덮어 써버리는 충돌이 발생한다.

 - 링크드 리스트를 사용하여 체이닝(chaining)으로 해결한다.

 

LinkedTuple

 - 각 인덱스마다 LinkedTuple이 존재. 해당하는 인덱스의 LinkeTuple에 새로운 값을 추가.

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

 

put

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)      # 해당 인덱스에 키와 밸류 값을 링크드튜플로 저장

 

get

    def get(self, key):
        index = hash(key) % len(self.items) # 해쉬함수를 사용하여 인덱스 값으로 변환
        return self.items[index].get(key)   # 해당 인덱스 내의 링크드튜플에서 해당 키값의 데이터 반환

---

개방 주소법(Open Addressing)

 - 배열의 다음 남는 공간에 넣는 방법

 - items[3]에 데이터가 존재하면, items[4]에 데이터를 넣는다.

 - 만약 items[4]에도 데이터가 존재한다면 비어있는 다음 인덱스인 items[5]에 데이터를 넣는다.

---