해쉬(Hash)

해쉬란?

• 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조
• key : value의 형태를 갖는 자료구조
• ex)전화번호부 (이름 : 전화번호) (검색어 : 검색결과)
• 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
• 모든 데이터 타입으로 접근 가능
• 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
• 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다.

 

파이썬 터미널로 작성해보면, 이미 해쉬 함수가 제공되고 있음을 알 수 있음

>>> hash("fast")
-146084012848775433
>>> hash("slow")
7051061338400740146

 

get 함수 / put 함수 / getOrDefault 함수는 hash를 이해하는 데 있어 반드시 필요한 함수

class Dict:
    def __init__(self):
        self.items = [None] * 8 # len(self.items) == 8

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

	def get(self, key):
        index = hash(key) % len(self.items) # len : items 배열의 인덱스 + 1
        return self.items[index]


my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test")) # 3

# Hash 함수 시간복잡도 : O(1) >> 어떤 작업을 해도 한 번만 하면 된다는 뜻
# array랑 비교했을 때 훨씬 빠름

 

해시 충돌

 

위의 식에서는 인덱스가 8개인데,

만약 아이템이 8개를 넘어간다면? 배열 길이를 초과하게 되면서

어떤 것들은 반드시 같은 인덱스 값을 부여받게 될 것이다.

 

하나의 인덱스에 두 개의 key가 들어가는 것을 이전에는 생각해본 적이 없다.

여기서는 그것을 해쉬 충돌(Hash Conflict)이라고 부른다.

 

일반적으로 이렇게 될 시에는 기존 데이터에 새 데이터가 덮어씌우는 결과를 낳게 되는데,

충돌을 해결하는 첫번째 방법은 링크드 리스트를 사용하는 방식이다.

이 방식을 연결지어서 해결한다고 해서 체이닝(Chaining) 이라고 부른다.

 

class LinkedTuple:
    def __init__(self):
        self.items = []

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v
                
# 이렇게 되면 추가적인 선형검색이 필요하기 때문에 시간복잡도가 다소 증가할 수 있다.

아래 예시처럼 되는데, 이것을 이해하기 어렵다면 링크드 리스트에 대해 공부하는 게 먼저.

ex) [None, None, (fast, "빠른") → (slow, "느린"), ... ]

 

응용

 

그렇다면 어떤 문제를 풀 때 Hash 개념이 필요할까?

 : String을 기반으로 정보를 기록하고 관리해야 할 때, 단순 배열을 쓸 수 없으니 Hash로 관리

>> 대부분 key가 string이다.

 

이러한 면에서 Hash는 시간복잡도가 적기 때문에 그 측면에서 다른 문제풀이보다 유용함.

또한 해시 함수는 내장함수이기 때문에 전혀 코드 작성 면에서도 걱정할 것이 없음.