[Algorithm] 해쉬 맵

1. 해시 테이블이란?

해시테이블이란?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조중 하나로 빠르게 데이터를 검색할 수 있는 자료구조.
해시 테이블은 각각의 Key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다.
실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

해시이미지1 \

예를 들어 (“John Smith”, “521-1234”)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function(“John Smith”) % 16 연산을 통해 index값을 게산한다. 그리고 array[index] = “521-1234”로 존화번호를 저장하게 된다.
Key 값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다.
해시 테이블의 평균 시간복잡도는 O(1)이다.

해시 함수

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것. 해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 3가지가 있다.
- Division Method
- Digit Folding
- Multipllication Method
- Univeral Hashing

2. 해시 값이 충돌하는 경우

해시 값이 충돌하는 경우

해시 함수를 돌려 나온 값이 동일하다면 분리연결법, 개방주소법 크게 2가지 방법으로 해결할 수 있다.

분리 연결법

해시이미지2

Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것
위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 실제로 Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.
이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

개방 주소법(Open Addressing)

Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재함.
- Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
- Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
- Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

해시이미지3

Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다.

3. 해시테이블 시간복잡도

각각의 Key 값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다. 하지만 덱이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

4. 파이썬에서의 해시 사용법

Python은 Dictionary라는 형태로 해시 자료구조를 제공. 그리고 Dictionary는 dict 클래스로 구현되어있음

해시는 언제 사용?

리스트를 쓸 수 없을 때
- 리스트는 숫자 인덱스를 이용해 원소에 접근. my_l[1] 처럼만 쓸 수 있고, my_l[‘abc’] 처럼 쓸 수 없다.
- 인덱스 값이 숫자가 아니라 다른 값 - 문자열, 튜플 등이여야 할 때, 딕셔너리를 쓸 수 있다.
빠른 접근/탐색이 필요할 때
- 딕셔너리는 함수 대부분의 시간 복잡도가 O(1)이다.
집계를 할 때
- collections 모듈의 Counter클래스를 사용하여 쉽게 집계 가능

Dictionary와 리스트의 시간 복잡도 비교

Operation	Dictionary	List
Get Item	O(1)	O(1)
Insert Item	O(1)	O(1) ~ O(N)
Update Item	O(1)	O(1)
Delete Item	O(1)	O(1) ~ O(N)
Search Item	O(1)	O(N)

Dictionary init

{}를 사용하거나 dict 함수를 호출하여 빈 딕셔너리 선언

# 빈 딕셔너리 생성하기

empty_dict1 = {}
empty_dict2 = dict()

empty_dict1, empty_dict2

# 특정 key-value쌍을 가진 dictionary 선언하기

person = {
    'name': '최연식',
    'age': 28
}

person # {'name': '최연식', 'age': 28}

Dictionary - Get

딕셔너리의 원소를 가져올 때에는 주로 두가지 방법을 이용합니다.

[] 기호 사용
get 메소드 사용
- get(key,x)는 key에 해당하는 value가 없으면 x를 return 하라는 뜻

person = {
    'name': '최연식',
    'age': 28
}
person['name'] # '최연식'

# get 메소드를 이용해 원소 가져오기 1
# 딕셔너리에 해당 key가 없을 때 Key errorㄹㄹ 내는 대신 특정한 값을 가져온다
person.get('height',180) # 180

# get 메소드를 이용해 원소 가져오기 2
# 딕셔너리에 해당 key가 있는 경우 대응하는 value를 가져온다.
person.get('height',180) # 180

Dictionary - Set

딕셔너리에 값을 집어넣거나, 값을 업데이트할때는 [] 기호를 사용

person = {
    'name': '최연식',
    'age': 28
}
person['height'] = 180
person #  {'name': '최연식', 'age': 28, 'height':180}

# 값 수정하기1
person = {
    'name': '최연식',
    'age': 28
}
person['age'] = 30
person #  {'name': '최연식', 'age': 30, 'height':180}

# 값 수정하기2
person = {
    'name': '최연식',
    'age': 28
}
person['age'] += 2
person #  {'name': '최연식', 'age': 30, 'height':180}

Reference

https://mangkyu.tistory.com/102