[Python] Hash ?

해쉬 (Hash)

해쉬함수를 사용하여 색인을 버킷이나 슬롯의 배열로 계산한다.
데이터의 검색과 저장이 아주 빠르게 진행된다

여기서 헤드를 셋팅하는건 자료구조 마다 다르니 잘 기억 하도록 하자 !

시작 !

class Dict:
    def __init__(self):
        self.items = [None] * 8 #테스트할 배열 8개를 생성함

---

기능 ! 

put() : 받은 키 벨류값을 저장

def put(self, key, value):
    index = hash(key) % len(self.items) #해쉬값(랜덤)키로 받은 임의의 숫자를
                                #배열의 최대길이로 나눈 값을 인덱스번호로 저장
    self.items[index] = value #위에 생성한 인덱스 번호에 데이터값을 넣어준다
    return

get() : 받은 키로 인덱스 번호 호출

def get(self, key):
    index = hash(key) % len(self.items)
    return self.items[index] #인덱스 번호 호출

그런데 이것을 임의의 문자열을 같은 값으로 나누면 인덱스번호가 중복이 될 경우도 있다 !! -충돌
이것을 해결 하기 위해 여러가지 방법이 있다 

1 - Chaining 

 튜플(LinkedTuple)로 된 배열을 만든다. *튜플은 값을 변경하는것이 안된다.

class LinkedDict:
    def __int__(self):
        self.items = [] #[LinkedTuple(),...*8]
        for i in range(8):
            self.items.append(LinkedTuple())

키와 벨류가 들어간 링크드 리스트가 된다

put(): 받은 키와 밸류를 튜플형식으로 삽입한다

def put(self, key, value):
    index = hash(key) % len(self.items)
    self.items[index].add(key, value) #위에서 받은 add메서드를 활용하여 인덱스에 데이터를 넣어준다.
    return

앞서나온 해쉬에서의 put은 키값에 인덱스번호를 지정해줫지만
여기선 키값으로 인덱스번호를 지정하는것은 같지만 그 안에 키벨류를 또 넣어주어서 중복을 해결한다.

get(): 인덱스값을 찾은 후 키값을 불러온다. 

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