Python으로 해시 테이블 만들어보기

https://koreanraichu.tistory.com/289

해시 테이블

여기서 이어진다.

 

솔직히 이론적인거 백날 설명해봐야 뭔 소린지 모르잖음? 그니까 같이 만들어봅시다. 참고로 이번에 참고한 곳은 https://wikidocs.net/193049

06. 파이썬으로 해시 테이블 구현하기

여기다. 

---

쿠키 틀 짜기

뭔 코딩하다말고 쿠키 타령이여? 아, 먹는 쿠키 말고... 클래스를 만들건데, 이 클래스를 보통 쿠키 틀에 비유한다. 쿠키 틀로 쿠키 찍는거랑 클래스가 비슷한가봄. 그거랑 별개로 치즈쿠키 먹고싶다...

 

class Hash_table:
    def __init__(self, length = 5):
        self.max_len = length
        self.table = [[] for _ in range(self.max_len)]
    
    def hash(self, key): # 해시 테이블에 key와 value를 넣는다. 
        res = sum([ord(s) for s in key])
        return res % self.max_len

    def set(self, key, value):
        index = self.hash(key)
        self.table[index].append((key, value))

    def get(self, key): # 해시 테이블에서 key의 value를 찾는다.
        index = self.hash(key)
        value = self.table[index]
        if not value:         # 찾는 키가 없으면 None을 반환
            return None
        for v in value:       # 리스트에서 값을 찾아 반환 
            if v[0] == key:
                return v[1]
        return None

이게 해시 테이블을 찍어내기 위한 쿠키 틀이다. 위쪽은 해시 테이블의 길이를 정하는 것 같고... hash는 키랑 밸류를 넣는 거고, 밑에 있는 게 해시 함수다. 여기서는 아스키 코드의 총 합을 테이블의 길이로 나눠서 해시를 만드는데(해시 함수가 만드는 게 해시), 이거 입력이 한글이면 다른 방법을 써야 한다. 밑에 있는 set은 아마 키값을 넣고 변환된 해시가 나오면 그 해시에 인덱싱하는 것 같고... 그 밑에 있는 건 해시 테이블에서 키를 이용해 값을 찾는 거다.

 

아, 밑에 if문이요? 해시 테이블에서 값 찾았는데 없을 때 None이라고 뜨게 하라는 얘기.

 

if __name__ == "__main__":
    capital = Hash_table()
    country = ["Korea", "America", "China", "England", "Türkiye"]
    city = ["Seoul", "Washington", "Beijing", "London", "Ankara"]
    for co, ci in zip(country, city):
        capital.set(co, ci)

    print("해시 테이블의 상태")
    print("===============")
    for i, v in enumerate(capital.table):
        print(i, v)
    print()
    print("해시 테이블의 검색 결과")
    print("====================")
    print(f"Captial of America = {capital.get('America')}")
    print(f"Captial of Korea = {capital.get('Korea')}")
    print(f"Captial of England = {capital.get('England')}")
    print(f"Captial of China = {capital.get('China')}")
    print(f"Captial of Japan = {capital.get('Japan')}")
    print(f"Captial of Türkiye = {capital.get('Türkiye')}")

그래서 이 과정을 거치면 해시 테이블이 완겅된다. 검색 결과에 있는 건 말 그대로 .get을 이용해 해시 테이블에서 검색한 결과.

 

if __name__ == "__main__":
    pokemon = Hash_table()
    name = ["Metagross", "Gengar", "Raichu", "Yveltal", "Glimmora"]
    nickname = ["김메탕", "최팬텀", "왕뚠뚠돈까스", "냉동차돌박이", "라피스라줄리"]
    for name, nickname in zip(name, nickname):
        pokemon.set(name, nickname)

    print("해시 테이블의 상태")
    print("===============")
    for i, v in enumerate(pokemon.table):
        print(i, v)
    print()
    print("해시 테이블의 검색 결과")
    print("====================")
    print(f"Metagross = {pokemon.get('Metagross')}")
    print(f"Gengar = {pokemon.get('Gengar')}")
    print(f"Raichu = {pokemon.get('Raichu')}")
    print(f"Yveltal = {pokemon.get('Yveltal')}")
    print(f"Glimmora = {pokemon.get('Glimmora')}")
    print(f"Beldum = {pokemon.get('Beldum')}")

해시 메소드 건들기 싫어서 포켓몬은 영칭으로 넣었음... 아무튼. 리스트가 클래스 안에 있는 게 아니기때문에 리스트 안에 있는 건 얼마든지 바꿀 수 있다. 키값은 포켓몬의 영어 이름(그니까 이름), 밸류는 내가 실제로 지어준 닉네임이다. 

 

아니 아스키코드 합을 5로 나눈건데 충돌만 세개 실화냐...

 

pokemon = Hash_table()
name = ["Swadloon", "Ferroseed", "Tinkaton", "Yveltal", "Raichu", "Nihilego", "Metagross", "Gengar", "Goodra", "Primarina", "Glimmora", "Brute Bonnet", "Iron bundle", "Heatran", "Zygarde", "Goomy", "Flutter Mane"]
nickname = ["망개떡", "김철시드", "웨폰브레이커", "냉동차돌박이", "왕뚠뚠돈까스", "김부추곱창씨", "김메탕", "김팬텀", "타로블루베리", "세탁기고장남", "라피스라줄리", "고혈압버섯", "메탈딸배몬", "모쏠드런선생", "우로보로스", "딸기바닐라", "퀘찰코아틀"]
for name, nickname in zip(name, nickname):
    pokemon.set(name, nickname)

for i, v in enumerate(pokemon.table):
    print(i, v)

해시 테이블을 만들 리스트 자체의 길이는 상관 없다. 길이 넘는다고 오류뜨는 거 아님.

 

아, 그래서 zip이랑 enu머시기는 뭐냐고? zip은 저기 리스트 두 개를 튜플로 묶어서 반환하는건데 리스트의 0번 0번끼리 묶는다. enu머시기는 반복문 도는거라는데 나중에 자세히 다뤄보겠음.