[Data Structure] 해쉬 테이블(Hash Table)이란? (feat. 이론)

 

안녕하세요 Foma 💻  입니다!

오늘은 우리가 아주 흔하게 사용하고 있는 해쉬 테이블, Swift로 말하면 딕셔너리에 대해서 알아볼 거에요!

 

이미 구현되어 있는 코드로 쉽게 사용했는데 직접 구현하려고 하니 진짜 복잡하더라구요.

 

그래서 오늘은 해쉬 테이블에 대해서 정리해보려고 합니다!

 

바로 시작할게요~

---

해쉬 테이블(Hash Table)이란?

 

정의는 아래와 같습니다.

 

해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.
해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. - 위키 백과 -

 

즉, key와 value를 사용해서 데이터를 저장하는 자료구조입니다.

 

key값으로 value를 한 번에 찾을 수 있기 때문에 삭제,삽입,검색이 평균 O(1)이 걸리는 아주 효율적인 자료구죠이죠.

 

하지만 해쉬 함수를 사용해 키값을 인덱스로 변환하는 과정에서 충돌을 막기 위해 일반적으로 큰 공간복잡도가 필요하고

 

충돌이 발생한 최악의 경우 O(n)의 시간복잡도가 발생할 수 있습니다.

---

Hash란?

 

왜 "해쉬" 테이블일까요?

 

해쉬는 아래와 같은 뜻을 가지고 있어요.

 

• 잘게 썰다
• 엉망으로 만들다
• 섞다

 

즉, 마음대로 섞어버리는 테이블을 의미하는 것입니다.

 

마음대로 섞어버린 테이블이라니..? 좀 이상하죠? 왜 이렇게 이름 지은건지 차근차근 설명해드릴게요.

 

해쉬 테이블은 특정한 자료구조로 이뤄져 있는 것이 아니라 그냥 "배열"로 되어있어요.

 

이 "배열"을 해쉬 테이블에서는 버킷 혹은 슬롯이라고 부릅니다. (아래는 사이즈가 5인 버킷입니다.)

 

 

 

그리고 여기 이 버킷에 들어갈 키,밸류 값이 아래와 같이 있다고 가정할게요.

 

 

---

Hash Function

 

그런데 이 키,밸류 값들을 어떻게 버킷 안에 넣을까요?

 

이 때 사용되는 것이 바로 해쉬 함수(Hash Function) 입니다.

 

바로 아래처럼 키,밸류 값을 버킷 안에 마음대로 섞어버려서 넣어버리게 도와주는 것이죠. 

 

 

 

 

하지만 진짜 맘대로 섞는 것은 아니고 효율적으로 섞어서 배치해야 합니다.

 

1. 버킷 안에 들어가야 하므로 버킷 사이즈 이하인 인덱스가 나와야 하게 섞어야 합니다.

 

2. 버킷 안의 인덱스가 중복되지 않게 섞어야 합니다.

 

위 두가지 규칙을 지키면서 어떻게 효율적으로 섞을까를 많이 고민하신 선배님들이 고안한 대표적인 4가지 알고리즘이 있습니다.

 

1. Division Method

 

말 그대로 Division(나누기)를 이용하는 것입니다.

 

입력값을 버킷의 사이즈로 나눠서 나머지 값을 전체 버킷 사이즈에서 뺀 인덱스로 사용하는 것입니다.

 

예를 들어 입력값이 5이고 버킷 사이즈가 10이라면 10 - (5%10) = 5가 됩니다.

 

이 때 버킷의 사이즈는 소수로 정하고, 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 합니다.

 

2. Digit Folding

 

이 방법은 키값이 문자열일 때 사용하는 방법인데요.

 

문자열을 ASCII 코드로 바꾸고 합한 값을 인덱스로 사용하는 것입니다.

 

만약 FOMA라면 F:70, O:79, M:77,A:65 = 291이 인덱스로 되는 것입니다.

 

근데 인덱스가 버킷 사이즈보다 더 크면 어떻게 할까요? 바로 첫 번째 방법인 Division Method로

 

나눠서 사용합니다.

 

 

3. Multiplication Method

 

숫자로 된 Key값(k)과 0과 1사이의 실수 A, 2의 제곱수인 m을 사용하여 아래와 같은 식을 만들어 인덱스로 사용합니다.

 

floor(k*A mod 1)*m

 

k가 100 , A가 0.12345 , m이 2³ 이라면

 

100*0.12345%1 * 8 = 2.76 이므로 인덱스는 2가 됩니다.

 

4. Universal Hashing

 

위 해쉬함수를 포함해 여러 해쉬함수를 집합에 넣어두고 무작위로 꺼내서 인덱스로 만들어 사용합니다.

---

Collision(충돌)

 

위의 해쉬함수를 사용해서 최대한 중복을 피한다고 해도 중복되는 숫자가 나올 수 있겠죠?

 

예를 들면 key,value가 (5,Five) 값과 (15,Fifteen) 값이 있고 버킷의 크기가 10이라고 하겠습니다.

 

Division Method를 사용하면 5/10 -> index =5 , 15/10 -> index = 5로 중복이 발생하게 되죠?

 

이것을 바로 충돌이라고 부릅니다.

 

이렇게 충돌이 발생했을 때는 버킷 안에 값을 어떻게 저장해야 할까요?

 

이것 또한 선배님들이 먼저 고안해낸 방법이 대표적으로 2가지 있습니다.

 

1. Chaining 

 

체이닝은 연결리스트를 사용해서 중복된 값을 연결해 놓는 방법입니다. (연결리스트를 모르시면 여기 에서 확인해주세요!)

 

 

 

 

위에서 최악의 경우 O(n)의 시간복잡도가 필요할 수도 있다고 했는데, 체이닝을 사용하고 모든 수가 충돌했을 경우

 

모든 연결리스트를 탐색해야 하기 때문에 O(n)의 시간복잡도가 듭니다.

 

2. Open Addressing

 

개방 주소법은 인덱스가 중복되었다면 해당 인덱스를 피하고 다른 비어있는 인덱스를 활용하는 방법입니다.

 

하지만 비어있는 인덱스에 무작위로 값을 넣으면 안되겠죠?

 

비어있는 인덱스를 찾는 것 또한 이미 정해진 규칙이 대표적으로 3가지 있습니다.

 

2-1. Linear Probing

 

중복된 인덱스에서 가장 가까운 비어있는 인덱스를 찾아서 값을 넣습니다.

 

만약 아래와 같이 0번째 인덱스가 중복되었다면 

 

 

비어있는 가장 가까운 인덱스인 1번째에 값을 넣습니다.

 

 

2-2. Quadratic Probing 

 

중복된 인덱스에서 비어있는 인덱스를 발견할 때까지 폭을 제곱만큼 탐색하는 방법입니다.

 

아래와 같이 0번째 인덱스가 중복되었다면 1^2 뒤인 1번째 인덱스 2^2 뒤인 4번째 인덱스 3^2 뒤인 9번째 인덱스....

 

이런식으로 숫자를 늘려가며 제곱수만큼의 뒤의 인덱스를 탐색하는 방법입니다.

 

2-3. Double Hasing Probing

 

중복된 인덱스에서 비어있는 인덱스를 찾을 때까지 해쉬 함수로 계산하는 방법입니다.

 

h1(k)→ 충돌 → h1(k)+1*h2(k)→충돌→ h1(k)+2*h2(k)→충돌→h1(k)+3*h2(k)→... 로 진행합니다.

 

예를 들면 h1(k) = key % 7 , h2(k) = 5 - (key%5) 설정하였다면 아래와 같이 비어있는 인덱스를 탐색하게 됩니다.

 

https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld025.htm

---

오늘은 이렇게 해쉬 테이블의 개념,해쉬 함수,충돌,충돌방지법에 대해서 알아보았습니다.

 

원래는 구현까지 하려고 했으나 글을 쓰다보니 너무 길어져서 다음 포스팅에서 구현을 해보도록 하겠습니다!