📌 Hashing

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

✔️ Static Hashing

키를 인덱스에 맵핑하여 배열(해시 테이블)에서 키를 저장하고 검색하는 기술

• 테이블의 entry를 버킷이라고 함 !

=> 검색, 삽입, 삭제 Performance : O(1)

✅ 예시 : 첫번째 글자를 키를 사용해서 해싱함

--------------------
| index |  bucket |
------------------
|   0   |  Korea  |
|   1   |  Japan  |
|   2   |  China  |
|   3   |  Thiwan |
|   4   |  Spain  |
--------------------

하지만 데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함

-------------------------------------
| index |  bucket |                  |
--------------------------------------
|   0   |  Korea  |                  |
|   1   |  Japan  |                  |
|   2   |  China  |                  |
|   3   |  Thiwan |     Thailand     |
|   4   |  Spain  |     Singapore    | -> Sri Lanka (overflow)
-------------------------------------

✅ 해시테이블의 장점

그럼에도 불구하고 해시테이블을 사용하는 이유?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐!

1. 인덱스에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있음.
   해시함수는 언제나 동일한 해시값을 리턴 하고, 해당 인덱스만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 인덱스는 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다.
   즉, 퍼포먼스가 O(1)이기 때문

2. 해시테이블을 다른 자료구조와 비교해봤을 때,

• 이진탐색트리는 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 𝑂(log n)
• 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 𝑂(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적 ❌
  즉, 해시가 훨씬 효율적임

3. 해시는 보안 분야에서도 널리 사용된다고 함. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문.
   또한 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 데이터 축약 기능도 수행할 수 있습니다.

🚀 Hashing의 궁극적인 목적

1. Collision 최소화
2. 오버플로우 최소화
3. 해시 테이블 사이즈 최소화
   => 해시 테이블 ?
   n개의 인덱스 & 인덱스 별로 k개의 버킷 => n*k 개의 키값 저장 가능

🚀 Hashing의 두가지 요소

1. Hash function 고르기

• modulo function : 가장 많이 사용하는 방법
  • H(key) = key mod hash_table_size
• digital selection : key에서 몇개를 골라서 사용하는 방법
  • key 값이 9010302051218면 몇개만 골라서 000011를 사용하는 방법
    엄청난 collision을 조심해야 함..

2. Collision 해결하기
   👇🏻

✅ Collision 해결

✔️ Collision 자체를 줄이는 것도 의미가 있지만, 중요한 것은 collision이 해시값 전체에 걸쳐 균등하게 발생하게 하는 것이 포인트!

현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 함
그만큼 collision이 아예 안 일어나게는 ❌, 그리고 어쨌든 collision이 일어난 키를 저장할 곳이 필요함.

1. Closed addressing

계산된 인덱스에 그대로 !

✔️ 각각의 인덱스에 collision이 난 키들을 저장할 수 있는 넉넉~한 버킷을 둠
✔️ 빠른 access, overflow ❌
✔️ 공간낭비 최악 => 실질적으로 사용하지 못함

📌 2D - array 사용

-------------------------------------------------------
| index |  bucket |                  |                |
-------------------------------------------------------
|   0   |  Korea  |                  |                |
|   1   |  Japan  |                  |                |
|   2   |  China  |                  |                |
|   3   |  Thiwan |     Thailand     |                |
|   4   |  Spain  |     Singapore    |    Sri Lanka   |
-------------------------------------------------------

📌 Overflow chaining (no collision bucket)

-------------------
| index |  bucket |
-------------------
|   0   |  Korea  |
|   1   |  Japan  |
|   2   |  China  |
|   3   |  Thiwan | -> Thailand
|   4   |  Spain  | -> Singapore -> Sri Lanka
-------------------

📎 탐색하는 방법

• insert할 때랑 같은 함수 사용
• 인덱스에 나온 버킷에서 키를 찾음
• 못 찾으면 chain을 확인하면서 찾음

2. Open addressing

다른 인덱스의 가능한 버킷을 찾아 떠남 !

📌 1) Linear Probing
collision이 발생하면 연속적으로 쭉 검색하면서 비어있는 버킷을 찾음

-------------------
| index |  bucket |
-------------------
|   0   |  Korea  |
|   1   |         |
|   2   |         |
|   3   |  Thiwan | 
|   4   |  Spain  | -> Singapore (Collision !!) 👇🏻
-------------------

-------------------
| index |  bucket |
-------------------
|   0   |  Korea  | 👇🏻
|   1   |Singapore| -> find free space ! 
|   2   |         |
|   3   |  Thiwan | 
|   4   |  Spain  | 
-------------------

📎 탐색하는 방법

• insert할 때랑 같은 함수 사용
• 못 찾으면 맞는 것을 찾기 위해 linear probing함

📎 문제점

• homeless 키가 삭제될 수도 있음
  => 여기서 발생하는 문제 : 삭제된 homeless 키가 삭제되고, 그 다음의 homeless 키를 찾고 싶을 때 문제가 발생함

0	Korea
1	Singapore
2	Qatar
3	Sri Lanka
4	China
5	Taiwan
6	Spain

여기서 homeless key인 Singapore를 삭제함

0	Korea
1	👈🏻 여기서 서치가 멈춤
2	Qatar
3	Sri Lanka
4	China
5	Taiwan
6	Singapore

그 후에 Sri Lanka를 찾으려고 할 때 서치가 멈춰버림

✔️ 문제를 해결하기 위해 State 를 두기 시작 => Occupied / Empty / Deleted

• 하지만 큰 문제점이 있음
  homeless key를 위해 빈 공간을 줬지만 그걸로 인해 연쇄적으로 homeless key가 발생
  => 결국 search performane가 O(n)

📌 2) Quadratic Probing
Linear probing의 수정 버전임
collision이 발생하면 k^2만큼 움직이면서 검색해서 비어있는 버킷을 찾음

• 부분적으로 Linear probing의 문제점이었던 그 연쇄적으로 homeless key 발생을 해결함
• 처음에 k=1, 1만큼 움직여서 빈칸을 찾고 빈 버킷이 아니라면 k=2, 2^2만큼 움직여서 빈 버킷을 찾음

📌 3) Double Hashing
두개의 hash function을 사용함
하나는 인덱스를 찾는데 사용, 하나는 homeless key를 넣는 interval 인덱스를 찾기 위해 사용함

• 예를 들어, h1 = key mod 13 / h2 = 1 + key mod 11 이렇게 사용
• h2는 h1과 같으면 ❌

✔️ linear & quadratic과의 차이점 : 인덱스가 key값에 따라 결정된다.

🚀 Hashing의 문제점

• Range 쿼리에 사용할 수 없음
• 어레이를 사용해서 어레이를 사용할 때의 보편적인 문제점이 발생