HashTable / HashMap

1. HashTable / HashMap 이란

HashTable이란 원소가 저장될 자리가 원소의 값에 의해 바로 결정되는 자료구조이다.

key와 value의 쌍으로 데이터를 저장하는 방법으로 HashMap이라고도 한다. 

예시로, 파이썬의 Dictionary를 떠올리면 편하다.

 

2. HashTable의 특징

• 삽입, 삭제, 검색 모두 평균 시간복잡도 O(1) 시간
  • 매우 빠른 응답을 요구하는 응용에 사용됨 
• 다른 연산은 지원 X
  • ex) 이진 탐색 트리는 최소 값, 특정 값 바로전의 값, 바로 다음의 값 등을 확인 가능 
  • but, hashTable은 그런 연산은 할 수 없음 
• 수정 가능
• key는 중복 x, value는 중복 o
• key를 통해 value값 얻기 

3. Hash Function / Hashing (해시함수/해싱)

Hash Function이란 임의의 길이를 갖는 데이터를 해시함수를 통해 고정된 크기의 데이터로 mapping하는 함수이다. 

출처 : https://velog.io/@taeha7b/datastructure-hashtable

key를 갖고 value를 찾는 방법에 수학적인 방법을 적용해 본 것이 Hashing이다.

즉, key값에 직접 산술적인 연산을 적용하여 찾고 싶은 value가 있는 테이블의 주소로 계산하여

value를 찾아가는 과정을 Hashing이라 한다.

 

이렇게 해싱을 통해 value로 이동할 수 있는 구조로 정리해둔 테이블을 HashTable이라 하는 것이고

HashTable을 통한 탐색 과정을 Hashing이라 한다. 

 

정리ver.

 

 

4. 충돌

이제 해시함수를 이용해서 HashTable을 작성해보자.

대부분 산술적인 연산(=해시함수)은 모듈러 연산을 이용한다.

 

💡모듈러 연산💡

 

A mod B

어떤 정수 A를 다른 정수 B로 나누면 나오는 나머지 

 

example.

h(x) = a mod 13

h(16) = 16 mod 13 = 나머지 3

h(29) = 29 mod 13 = 나머지 3 

 

 

h(16)과 h(29) 모두 value가 3이 나왔다.

이럴 경우 HashTable에서 충돌이 일어난다. 

 

즉, 충돌이란 여러개의 key값이 해시함수를 통해 같은 해시 값을 같는 경우 발생한다.

 

이 충돌을 해결하는 방법을 HashChain이라 한다.

 

 

 

 

 

 

5. 충돌 해결방법

충돌이 발생하는 경우를 위에서 살펴봤다.

이런 충돌을 해결하는 방법에는 2가지가 있다.

1) 선형조사 

해당 칸에서 충돌이 일어나면 빈 칸이 나올 때까지 다음 칸으로 이동하는 방법

 

 

1-1) 1차원 조사

 

💡 일차 군집 

example.

25, 13, 15, 16, 28, 31, 20, 1, 38 등

 

h(x) = a mod 13

 

h(15) = h(28) = 2이기 때문에 

h(28)은 index 2에 들어가지 못하고 

다음 칸들 중 가장 가까운 빈칸인 index 4칸에 들어간다.

 

이를 함수로 표현하면,

hi(x) = (h(x) + i) mod m 이 된다.

----------------------------------------------------------------

 

h(25) = 25 mod 13 = 12

h(38) = 38 mod 13 = 12

 

h(25) = h(38) = 12 인데 h(38)은 계속 밀려서

결국 index 6칸에 들어가게 된다.

 

특정 영역에 원소들이 몰릴 경우,

상관없는 값을 읽고 비교하게 되기 때문에 해시의 효율을 낮춘다. 

이렇게 몰리는 공간을 일차군집이라 한다.

 

 

 

1-2) 2차원 조사 

 

💡이차 군집

example.

25, 15, 16, 28, 31, 44, 29

 

h(x) = a mod 13

 

16까지는 알맞게 들어가다가

28부터 h(15)= h(28) = 2라서 

h(28)은 index 2에 들어가지 못한다.

 

이때, 16(마지막)을 기준으로 1칸 (제곱수) 띄운 곳으로

들어가는 방법을 이차원 조사라 한다. 

 

이를 함수로 표현하면, 

hi(x) = (h(x) + i^2) mod m

--------------------------------------------------------------

h(31) = h(44) = 5 이기 때문에

같은 방법으로 h(44)는 32(마지막)을 기준으로 1칸 (제곱수) 띄운 곳으로

들어간다. 

 

h(29) = 3인데 이미 index 3이 차있다. 2차원 조사는 이때, 한칸씩 이동하지 않고 4칸 (제곱수)로 이동한다. 

 

일차군집과 마찬가지로 이차군집은 특정 구간에 원소들이 몰린 공간을 의미한다. 

 

근데, 문제는 일차원조사도, 이차원 조사도 h(x1) = h(x2)라면 계속 같이 움직이게 되는 문제가 생긴다. 

즉, 계속해서 충돌이 발생하는 것이다 !!! 

결국, 충돌을 해결하는 완전한 방법은 될 수 없다. 

 

2) 이중 해싱

이차 군집을 막기 위해선, 똑같은 칸 만큼 이동하는 선형조사 대신 다른 방법이 필요하다.

이때 나오게 된 방법인 이중해싱이다.

이중해싱은 또 다른 해시 함수 f(x)를 이용하는 방법이다.