[파이썬 101] 해시(Hash)

해시 함수

- 임의의 길이를 갖는 데이터를 고정된 길이의 해시값으로 출력하는 함수 (해시값을 만들어주는 함수)

- Key에 대해 산술 연산을 이용해 데이터 위치를 찾도록 도와줌

- 키를 사용하지 않아 같은 입력에 대해서는 항상 같은 출력이 나옴

- 데이터 무결성을 보장하기 위해 사용되는 경우가 많음 (블록체인)

 

 

해시 테이블

- (Key, Value)로 데이터를 저장하는 자료구조 (Python의 Dictionary가 이에 해당. 하지만 3.6 이후 순서 유지로 바뀜)

- 각각의 Key를 해시 함수를 통해 고유한 index에 저장함

- 패턴 매칭 등을 하지 않아도 바로 데이터에 접근할 수 있어 시간 측면에서 매우 효율적임

- 해시 함수에 의해 같은 인덱스가 나올 경우가 생길 수 있음 (충돌 발생)

- 이를 사용하면 중복을 막고 서버 작업 없이 자료를 캐싱할 수 있다는 장점이 있다

 

 

해시 테이블 구현 코드 (ablue-1.tistory.com)

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, length):
        self.items = []
        for i in range(length):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)


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

menu = LinkedDict(4)
menu.put("apple", 1000)
menu.put("potato", 500)
menu.put("melon", 9000)
menu.put("iceCream", 1500)
print(menu.get("apple"))	# 1000
print(menu.get("potato"))	# 500

 

 

Python의 Dictionary와 List의 시간 복잡도 비교

작업	Dictionary (충돌 X)	List
Get	O(1)	O(1)
Insert	O(1)	O(1) ~ O(N)
Update	O(1)	O(1)
Delete	O(1)	O(1) ~ O(N)
Search	O(1)	O(N)

- List에 비해 굉장히 빠름 (코딩 테스트의 효율성 테스트나 성능 향승을 위해 사용)

- 충돌이 일어날 경우에도 O(N) 수준

 

 

hash() 메서드

- 파이썬에서 제공하는 hash() 메서드를 사용하면 Dictionary에 활용할 수 있음

- 다른 해시함수를 적용해야 하는 경우 __hash__ method를 override 해서 사용

 

 

hashlib 라이브러리

- 암호화와 관련된 해싱 라이브러리 제공

- sha256 등을 간편하게 사용할 수 있음

- hashlib은 추후 별도의 글로 설명

 

 

 

참조
 - ComDoc 님의 블로그
 - 2seunghey 님의 블로그
 - GeeksforGeeks
 - yunaaaas 님의 블로그