Data Structure(3) Hash Table

1. Hash Table

어떤 특정 키값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다.

그렇다면 "해시 함수"는 뭐고 "해시"는 뭘까?

해시 함수 : 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시(Hash) : 
1. 간단히 말하면, 해시함수가 뱉어내는 결과물이다.
2. 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 변환하는 것을 의미한다.
3. 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.

해시값(Hash value) : 매핑 후 데이터의 값을 의미한다. 저장소(bucket, slot)에 최종적으로 저장되는 값이다.

해싱(hashing) : 매핑하는 과정을 말한다.

* 해쉬값을 생성해주는 사이트도 있다 : 링크

여기선 입력값에 따라 다른 해쉬값을 가진다.

---

Hash Table : Methods :

아래 코드는 Linked List의 Method들을 구현하기 위해 Linked List를 Class로 만들어준 것이다.

 

Hash Table 예시

다음, Lined List에 사용되는 Method들을 모두 직접 아래와 같이 구현해봤다.

1. Insert(key, value) : Hash Table에 주어진 키와 값을 저장한다.

이미 해당 키가 저장되어 있다면 값을 덮어씌운다.

Insert 예시

2. retrieve(key) : 주어진 키에 해당하는 값을 반환한다.

만약 반환하는 키가 없다면 undefined를 반환한다.

Retrieve 예시

3. remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환한다.

만약 키에 해당하는 값이 없다면 undefined를 반환한다.

Remove 예시

4. _resize(newBucketNum) - 해시 테이블의 Storage 배열을 새 저장 공간(newBucketNum)으로 Resizing하는 함수이다.

* Hash table에 저장된 key-value 쌍이 최대 저장 공간(bucketNum)의 75%를 넘는 경우, 공간을 2배로 늘린다.

* 만약, 최대 저장 공간이 25%보다 작아지는 경우, 공간을 절반으로 줄여준다.

_Resize 예시

---

Speed

Hash Table에서 갖는 시간 복잡도는 모두 O(1)이다.

* 다만, 최악의 경우 O(n)도 가능하다.

* 이유는, 해시 충돌로 인해 모든 칸(bucket)의 value들을 찾아봐야 하는 경우도 있기 때문이다.

Method	Big O Complexity
Insert(key, value)	1
Remove(key)	1
Search	1
LookUp	1

---

Hash Collision

위에 언급한 것처럼 Hash Table의 작업 속도는 O(1) Constant Time으로서 굉장히 빠르다.

하지만, 자료구조가 정렬이 되지 않는다는 가장 큰 단점이 있다.

 

Hash Table은 메모리 공간에서 주소에 순차적으로 값을 부여 및 저장하지 않고, random하게 값을 부여하게 된다.

* 0, 1, 2 총 3개의 메모리 주소가 있다고 가정해보자.

* 첫번째 데이터가 0번째 메모리 주소에 들어갔다고 하더라도, 반드시 두번째 데이터가 1번째 메모리 주소에 들어가지 않는다는 얘기다.

* 즉, 해쉬 함수에 통해 출력된 결과물에 따라서 랜덤하게 주소가 배정되는 것이다.

이렇게 되면, 나머지 메모리 저장소들은 비워져있고 [n]번째 메모리 저장소에 데이터가 몰려 저장될 수도 있게 된다.

 

Hash Collision 설명

여기서, John Smith와 Sandra Dee라는 두 개의 Key가 해쉬 함수를 거쳐 나온 해쉬값이 동일하여 메모리 주소 152에서 같이 보관이 됬다.

* 즉, 메모리 주소 152에서 해쉬 충돌이 발생한 것이다.

---

Hash Collision Solution

1. Open Addressing : 다른 여분의 인덱스에 설정하기

* 모든 키를 해시 테이블 자체에 저장한다.

* 테이블의 각 칸(slot)에는 1개의 키만 저장하는 방법이다.

* 충돌 해결 기법 : 

1. Linear probing (선형 탐사) :

- 선형으로 검사하여 처음으로 빈 슬롯에 저장 테이블의 끝에 도달하면 다시 처음으로 선형탐사로 돌아간다.

- 만약 1번 칸이 비어 있다면 2번 칸이 비어 있는지 검사 후, 비어 있다면 2번 칸에 넣는 방법이다.

- Linear probing의 단점 : primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미한다.
- 검색시간이 클러스터의 길이에 비례하게 되므로 바람직하지 않다.

 

2. Quadratic probing (제곱 탐사) :

- 충돌 발생시 h(k), h(k) + 1^2, h(k) + 2^2, h(k) + 3^2, … 순서로 시도한다.

- 선형 탐사법 때와 동일한 상황에서 제곱 탐사법을 사용하면 해시 테이블은 아래와 같다.

첫번째 충돌 시 :  6은 충돌이 난 1번 인덱스로 부터 1^2 =1 만큼의 옆 칸에 위치.
두번째 충돌 시 : 13은 충돌이 난 1번 인덱스로 부터 2^2 =4 만큼의 옆 칸에 위치하게 된다.
세번째 충돌 시 : 21은 충돌이 난 1번 인덱스로 부터 3^2=9 만큼의 옆 칸에 위치하게 된다.

0	1	2	3	4	5	6	10
	2020	6			13		21

- Quadratic Probing의 장점 : 이 방법을 이용하면 충돌이 발생하더라도, 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.

- Quadratic Probing의 단점 : 하지만, 해시값로 1이 여러번 나온다면 충돌은 매번 불가피하고, 데이터의 군집은 피할 수 없는 숙명이기 때문에 이 현상을 이차 군집화(Secondary Clustering)이라고 부른다.

 

 

3. Double hashing (이중 해싱) :

- 위 두가지 방법의 단점을 보완한 방법이다.

- 하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.

 

2. Close Addressing : 충돌이 일어나도 해당 위치에 저장하기.

- 'Tuple'이라는 여러 개를 둘 수 있는 다른 방법을 사용함.

- 충돌이 일어나는 각 버켓/칸 내부에 또다른 배열이 있기에, 해시 충돌이 일어나게 되면 요소 안의 배열로 쌓인다.

- Chaining : 충돌된 값들을 연결 리스트로 연결.

---

Hash Table - [Pros & Cons]

장점 :

** 1. 해싱된 키를 가지고 배열의 인덱스를 사용하여 검색하기 때문에 추가, 삭제 및 탐색이 아주 쉽고 빠르다.
2. 해시 충돌이 없을 때는 O(1)의 상수 시간에 가까워지지만 해시 충돌이 많아질수록 O(n)에 가까워진다.

 

단점 :

1. 해시 함수를 사용하는 데에 추가적인 연산이 필요하다.

2. Hash Table의 크기가 유한적이고, 해시 함수의 특성상 해시 충돌을 일으킬 수 있다.
3. 공간 효율성이 떨어진다.

- 데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 한다.

- 공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.

4. 순서가 있는 배열에는 어울리지 않는다.

- 순서가 중요한 데이터의 경우 Hash Table은 어울리지 않다.

- 순서와 상관없이 Key 만을 가지고 Hash 를 찾아 저장하기 때문이다.

5.  Hash Function의 의존도가 높다.

- 평균 데이터 처리의 시간복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않는 결과이다.

- 해시함수가 매우 복잡하다면 해시테이블의 모든 연산의 시간 효율성은 증가할 것이다.

 

가장 강력한 예시로, 주소록이 있을 것이다.

- 이름  & 전화번호의 매칭을 이용하여 데이터를 처리하기 때문이다.