[Algorithm] 해시를 사용한 집합(set)과 맵(map)

🌵 Hash Function (해시 함수) 또는 Hash Algorithm (해시 알고리즘)

 

임의의 길이의 데이터(key)를 고정된 길이의 데이터(hash)로 매핑하는 함수

이 과정을 hashing이라 한다.
즉, 해시 함수 : key (Input) -> Hash (Output)
이때의 Hash는 저장 위치가 된다.

 

 

 

🌵 Hash Table (해시 테이블) 또는 Hash Map (해시 맵)

 

해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.

파이썬의 딕셔너리(dictionary) 자료형은 해시 테이블로 구현되어 있다.

 

 

 

장점

해시 테이블은 key-value가 1:1로 매핑되어 있기 때문에
삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있다.
따라서 데이터를 아주 빠르게 '삽입'하거나 '가져올 때' 유용하다.

 

 

 

단점

1. 최솟값이나 최댓값을 찾을 때 (전체 자료를 검색해야 할 때)는 비효율적
2. 해시 충돌 발생
3. 순서/관계가 있는 배열에는 어울리지 않는다.
4. 공간 효율성이 떨어진다. 
5. Hash function이 복잡하다면 Hash를 만들어 내는 데 오래 걸린다.

 

 

 

🌵 해시 충돌(Hash Collision)과 해결방법

 

key의 전체 개수와 동일한 크기의 버킷(데이터가 저장되는 곳)을 가진 해시테이블을 만들게 되면, 

해시 충돌 문제는 발생하지 않는다. 

하지만 실제 사용하는 키의 개수가 현저히 적을 경우, 

전체 key의 개수만큼의 테이블 크기를 유지하는 것은 메모리 낭비이다. 

따라서 보통 실제 키의 개수보다 적은 크기의 해시 테이블을 사용하고, 이 과정에서 해시 충돌이 발생한다.

 

즉, 해시 테이블의 특성 상 key - value 는 각각 1:1로 대응되어야 하지만, 서로 다른 2개 이상의 key가 hash function을 통해 얻은 해시 값이 동일할 경우 해시 충돌이 발생한다.

 

 

해결방법

 

1. Chaining (체이닝)

 

저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법

 

 

장점

• 미리 공간을 만들어 놓을 필요 없이, 충돌 발생 시 공간을 만들어 새로운 값을 연결하면 된다.
• 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

 

단점

• 체인이 길어지면 검색이 느려진다.
• 같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아진다.

 

 

 

2. Open Addressing (개방주소법)

* 파이썬에서의 해시 충돌 발생 시 개방 주소법으로 해결한다.

 

 

위의 그림에서 John과 Sandra의 hash가 동일해 충돌이 일어난다. 이때 Sandra는 바로 그 다음 비어있던 153 hash에 값을 저장한다. 그 다음 Ted가 테이블에 저장을 하려 했으나 본인의 hash에 이미 Sandra로 채워져 있어 Ted도 Sandra처럼 바로 다음 비어있던 154 hash에 값을 저장한다.

 

Open Addressing (개방주소법)이란 해시충돌이 일어나면 다른 저장소에 데이터를 삽입하는 방식

이 때, 비어있는 해시를 찾아가는 방법으로는 대표적으로 3가지 방식이 존재한다.

 

1) 선형 탐색(Linear Probing)

: 해시 충돌이 일어난 해시값에서 고정폭(1개 또는 n개)으로 건너 뛰면서 비어있는 해시가 나오면 저장

 

 

장점

• 추가적인 메모리가 필요하지 않다.

 

 

단점 

• 한 번 충돌이 발생하면 부근에 충돌이 몰리는 군집화 현상이 발생하기 쉽다.
• 삭제 시 복잡

 

 

2) 제곱 탐색(Quadratic Probing)

: 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

 

• 군집화를 막기위한 방법으로 고정폭이 아닌 폭을 제곱으로 늘리면서 공간을 찾는다.
• 하지만, 선형 탐색에 비해 공간을 많이 확보해놔야 한다.

 

 

3) 이중 해싱(Double Hashing)

: 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용

 

• 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
• 삽입, 삭제시 오버헤드가 적다.
• 저장할 데이터가 적을 때 더 유리하다.

 

 

 

---

 

 

🌵 관련 문제

 

🥈[백준 알고리즘 1920번 : 수 찾기]

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

[SOLUTION]

https://gyurisinzorba.tistory.com/46

[Python] 백준 알고리즘 1920번 : 수 찾기

 

---

 

🥈[백준 알고리즘 10816번 : 숫자 카드 2]

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

[SOLUTION]

 

---

🥈[백준 알고리즘 9375번 : 패션왕 신해빈]

https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

[SOLUTION]

https://gyurisinzorba.tistory.com/36?category=1019803 

[Python] 백준 알고리즘 9375번 : 패션왕 신해빈

 

---

 

 

 

 

 

---

~ 해당 포스팅은 업데이트 중 ~