알고리즘 [Hash Map]

해시 맵이란?(해시 맵 == 해시테이블)(swift 는 딕셔너리처럼되어있다.)

: Key - Value로 값을 저장한다.

Key        Value

100         변요한

101          박휘순

102         최우식

103         이병헌

키값을  해쉬로 바꿔 메모리를 효율적으로 관리하도록한다.

 

키값에 대해 해쉬함수를 key%4로 정의 하게된다면 길이 4인 배열에 저장 할 수있다.

ex) key 100인 경우, hash 값은 0 (=100%4) 이 되므로 empList[0] = 변요한 출력

 

하지만 서로 다른 키에 대해 동일한 해시 값이 생성되는 경우에는 충돌이 발생된다.

 

충돌문제 해결책

1. 열린 어드레싱 방법

충돌이 발생했을때, 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장한다.

 

-선형 조사법

k라는 키에서 충돌 발생 시 조사 순서는 f(k)+1 -> f(k)+2 -> f(k)3 -> f(k)+4...

특정 영역에 데이터가 집중적으로 몰리는 클러스터(Cluster)현상이 발생하기 쉽다는 단점이있다.

 

-이차 조사법

k라는 키에서 충돌 발생 시 조사순서는 f(k)+1^2 ->f(k)+2^2 ->f(k)+3^2 ->f(k)+4^2 ->..

선형 조사법에 비해 클러스터 현상이 완화된다.

 

-이중 해시(Double Hash)

이차 조사법도 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률이 여전히 높기 때문에 이를 보완하기 위해

이중 해시를 사용 할 수있다.

1차 해시 함수 : 키를 근거로 저장 위치를 결정하기 위함.

2차 해시 함수 : 충돌 발생 시 몇칸 뒤를 살필지 결정하기 위한 것

 

h1(k) = k% 배열의 길이

h2(k) = 1 +(k%c), c는 배열의 길이보다 작은 소수

(c가 소수인 이유는 클러스터 현상이 발생 확률이 현저히 낮다는 통계가 있다.)

 

"닫힌 어드레싱 방법"이다.

이방법은 무슨 일이 일어나도 자기 자신의 자리에 저장한다는걸 의미한다. 즉, 충돌이 발생해도 자기 자리에 꼭 들어가야한다는 것이다.

​

이게 가능하려면 자리를 여러개 만들 수 밖에 없다. 이를 구현하기 위한 적당한 모델이 바로

2차원 배열 그리고 연결 리스트이다.

​

그림에서 볼 수 있듯, 2차원 배열을 이용해서 해쉬값 별로 다수의 슬롯을 만들 수 있지만

메모리 낭비가 심하고 또한 충돌 최대 횟수도 고려해야하므로 부담이 간다.

 

 

따라서 연결리스트릉 이용한 "체이닝" 기법을 사용한다. (링크드 리스트 개념으로 들어간다)

슬롯을 생성하고 연결 리스트로 모델을 체인처럼 이어나가는 방식으로 해결한다.

그림에서 보이듯 하나의 해쉬 값에 여러개의 슬롯을 둘 수 있다. 따라서 탐색을 위해선 동일한 해쉬값에 대해, 묶여있는 슬롯을 모두 조사해야하긴 하지만 해쉬함수를 잘 정의한다면, 그래서 충돌 확률을 낮출 수 있다면 이는 별로 부담스럽지 않다.

해시 맵의 시간 복잡도

원하는 값을 찾기 위해 0번 index부터 순회해야 하는 배열의 O(n)과 달리,

Key 값을 해시하여 바로 Index에 접근하기 때문에

해시 테이블의 시간 복잡도는

O(1)

임! 배열에 비해 매우 빠른 것!

다만, 이는 일반적인 경우이고

최악의 경우, 모든 충돌이 다 발생한 경우 배열처럼 O(n)이지만,

해시 테이블은 일반적인 경우를 생각하고 만들기 때문에 O(1)이라고 말할 수 있음

 

5. 해시 테이블의 장단점 및 용도

장점	단점
- 데이터 저장/읽기 속도가 빠르다 - 키에 대한 데이터의 중복 확인이 쉽다	- 일반적으로 저장 공간이 많이 필요하다 (충돌 문제를 해결하기 위해 저장공간을 넓게 잡음) - 충돌이 발생 시 해결하기 위한 별도의 자료구조가 필요하다

 

 

리사이징 적기