[1028알고리즘 19]해쉬

해쉬 테이블 : "키", "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트 하고 싶을 때 사용하는 자료구조

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

해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.

만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면? 체이닝과 개방주소법으로 해결.

items = [None]*8

hash("가") %86

hash("나")%8

5

items[hash("가") %8]="가위"

items[hash("나") %8]="나비"

결과 :: items[None, None, None, None, None, '나비', '가위', None]

items[hash("나") %8]'나비'

O(N)

인덱스 값이 동일했을때.. "충돌발생"

해결 1) 링크드 리스트 사용.   >> 체이닝

해결 2)  배열의 다음 남는 공간에 넣는것.   >> 개방주소법(Open Addressing)

 

 

 

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)
        #LinkedTuple
        self.items[index].add(key,value)

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

#hash("사") %8   >>1
#hash("다") %8   >>1
l = LinkedDict();
a ="바"
b ="자"
print(a,b,(hash(a) %8)==(hash(b) %8))
l.put(a,"사자")
l.put(b,"다리미")
print(l.get(a))
print(l.get(b))