[알고리즘] 7강 - 탐색(2)

✅ 1. 레드-블랙 트리

(1) 레드-블랙 트리란?

• 레드-블랙 트리: 이진 탐색 트리의 구조를 그대로 가지고 있으며, 균형 탐색 트리이다. ( 즉, 이진 탐색 트리 업그레이드 버전 )
• 규칙1: 모든 노드는 검정 또는 빨강임.
• 규칙2: 루트 노드와 리프 노드는 항상 검정이며, 모든 리프 노드는 값이 없는 NULL 노드를 가진다.
• 규칙3: 빨강 노드의 부모 노드는 항상 검정이며, 빨강 노드는 항상 연달아 나타날 수 없다는 규칙임.
• 규칙4: 임의의 노드로부터 리프 노드까지의 경로상에는 항상 동일한 개수의 검정 노드가 존재한다.
• 규칙5, 규칙6: 이진 탐색 트리의 성질(특정 노드의 왼쪽 서브트리는 작고 오른쪽 서브 트리는 큰 규칙 등)

• 노드 구조: 이진 탐색 트리의 노드에서 color, parent, sibling 노드가 추가 된 노드 구조를 가지고 있음.

(2) 레드-블랙 트리 - 탐색 연산

• 탐색 연산: 이진 탐색 트리의 탐색 방법과 동일함. ( 대소 비교 후 더 크면 오른쪽 작으면 왼쪽 동일한 값 찾는 방식 )

(3) 레드-블랙 트리 - 삽입 연산

• 삽입 연산: 삽입할 원소(15)를 가지고 탐색을 진행 후, 탐색이 실패한 위치가 결국 삽입할 위치가 된다.
• 즉, NULL 노드인 잎노드에 빨강 노드를 추가하고 두 자식 노드를 NULL 노드로 만드는 과정이 삽입 연산임.

• 잎 노드(NULL)의 부모 노드가 빨강인 경우: 레드-블랙 트리는 삽입 시 항상 빨강 노드로 만들어지는데, 이유는 모든 경로에서 검정 노드 개수가 동일해야 하기 때문에, 만약 검정 노드로 넣게 되면 해당 경로의 검정 노드가 +1 이 더 많은 상황이 발생함.
• 즉, 규칙을 어긴 상황이 발생하며, 균형이 깨질 수 있는 문제가 있기 때문에 항상 빨강 노드로 삽입이 진행이 됨.
• 그래서 위의 45 원소를 삽입하는 상황에서 50 아래 NULL 노드에 45가 삽입이 되면 균형이 망가지게 됨.
• 이러한 문제를 해결하기 위해서는 루트 노드쪽으로 올라가면서 노드의 구조와 색깔을 조정해서 성질을 만족시켜야 함.

• 규칙1: 부모 노드의 형제 노드가 빨강인 경우는 단순히 같은 부모를 가지는 다른 형제를 의미 할 수 있음.
• ## 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔을 모두 변경 ##
• 규칙2: 부모 노드의 형제 노드가 검정인 상태에서 조부모 노드의 값이 20 부모 노드의 키값이 40 맨 아래 빨강 노드의 키값이 30 인 경우 조부모 노드와 부모 노드의 사이의 값인 경우를 의미함.
• ## 규칙2의 경우 현재 노드와 부모 노드를 회전시킴 ##
• 규칙3: 부모 노드의 형제 노드가 검정인 상태에서 현재 노드의 키값보다 부모 노드와 조부모 노드의 키값이 크거나 작은 경우는 쉽게 말해, 10(현재 노드), 20(부모 노드), 30(20의 부모노드) 이런 편향 트리 처럼 모양을 의미함.
• ## 규칙3의 경우 부모 노드와 조부모 노드를 회전 시키고 색깔을 변경함. ##

(4) 레드-블랙 트리 - 삽입 연산 (규칙 1)

• 규칙1: 현재 노드(45) 의 부모 노드(50)의 형제 노드(30)이 빨강인 경우 부모노드(50), 부모의 형제노드(30), 부모노드의 부모 노드(40)의 색깔을 변경시켜줌.

• 규칙1을 적용한 후: 현재 노드(40)의 부모 노드(60) 또한, 빨간색이므로 동일하게 구조 및 색깔을 바꿔줘야함.
• 이 경우 규칙1은 적용 할 수 없는 상태이지만, 규칙2는 적용이 가능한 상태임.

(5) 레드-블랙 트리 - 삽입 연산 (규칙 2)

• 규칙2: 부모노드(60)의 형제노드(10)가 검정이며, 현재 노드의 키값(40)이 부모 노드(60)와 부모 노드의 부모 노드(20)의 키값 사이인 경우이기 때문에 규칙2가 적용이 된다.
• 즉, 현재 노드(40)와 부모 노드(60)을 회전시키게 됨.

• 규칙 2 적용 후: 현재 노드(40)이 부모 노드(60)의 위치로 가게 되며, 60은 40의 자식 노드로 들어가게 된다.
• 이후, 이진 탐색 트리 규칙을 지키기 위해 40이 가지고 있던 자식 노드인 30, 50 중 하나인 50을 포기해 60 노드 자식으로 들어가게 됨.
• 하지만, 현재 상황에서도 결국 빨강 노드가 연달아 나타난 경우이기 때문에 구조 및 색깔을 바꿔줘야함.
• 이때, 규칙1(부모 노드의 형제 노드가 빨강인 경우), 규칙2(부모노드의 형제노드가 검정 및 부모 노드와 부모 노드 사이의 키값인 경우) 는 적용이 불가능한 상태이므로, 규칙 3을 통해서 해결 할 수 있음. 

(6) 레드-블랙 트리 - 삽입 연산 (규칙 2)

• 규칙3: 부모 노드(60)의 형제 노드(10)가 검정인 상태에서 현재 노드의 키값(60)보다 부모노드(40)와 부모노드의 부모노드(20)의 키값이 작은 경우에 해당 할 수 있음.
• 이때, 부모 노드(40)와 부모 노드의 부모 노드(20)을 회전시키고 색깔을 변경함.

(7) 레드-블랙 트리 - 삽입 연산 (규칙 3)

• 규칙3 적용한 후 상태: 20 - 40 - 60 의 편향 구조를 가지고 있던 상태에서 맨 상단에 있는 루트 노드가 왼쪽 서브트리로 빠지고, 그의 자식 노드 40 노드가 루트로 올라가고 60이 따라 올라가는 형태이다.

(8) 레드-블랙 트리 - 성능과 특징

• 규칙3: 빨강 노드는 연달아 나타날 수 없는 특징으로 인해, 루트 노드에서 리프 노드의 경로상에는 항상 빨강 노드의 개수가 검정 노드의 개수보다 작을 수 있음.
• 규칙4: 루트 노드에서 잎 노드까지의 모든 경로상에는 동일한 개수의 검정 노드의 개수가 존재함.
• 어떤 두 리프 노드의 레벨 차이가 2배를 넘지 않는 균형 탐색 트리:  경로상 검정 노드의 개수는 모두 동일하며, 검정 노드는 빨강 노드의 개수보다 항상 많기 때문에 두 리프 노드의 레벨 차이가 2배를 넘지않는 균형 탐색 트리임.
• 즉, 트리의 가장 짧은 경로 끝에 있는 리프 노드와 가장 긴 경로 끝에 있는 리프 노드를 비교하더라도 그 차이가 2배를 넘지 않는다는 의미를 가지는 것임.
• 탐색 O(log n): 일반적인 BST와 동일하게 동작하지만, 트리의 높이가 항상 제한되어 있어 최악의 경우에도 빠름.
• 삽입 O(log n): 삽입 위치를 찾는데 O(log n), 삽입 후 규칙 위반을 해결하기 위해 색 변경 및 회전 과정은 상수 시간 내에 처리됨.
• 삭제 O(log n): 삭제할 노드를 찾는데 O(log n), 삭제 후 불균형을 해소하기 위한 색 변경 및 회전 과정 역시 트리의 높이에 비례하여 수행이 됨
• 즉, 삽입과 삭제 연산은 최대로 트리의 높이 만큼 연산이 될 수 있기 때문에 상수시간내에 해결되기 때문에 시간 복잡도는 O(logn)임.
• 사실상 이진 탐색 트리: 탐색 연산은 이진 탐색 트리와 동일하지만, 삽입과 삭제에 대한 연산은 기존 이진 탐색 트리의 경우 편향트리가 만들어 질 수 있는 문제가 있지만, 레드블랙트리는 삽입과 삭제 연산에 대해서 색깔 변경, 회전과 같은 재구성을 통해 트리 구조의 균형을 맞추는 작업을 진행함.
• 즉, 균형을 맞춰두면 탐색 연산 및 삽입, 삭제를 하기 위한 탐색 연산이 logn 의 시간 복잡도를 가질 수 있게 됨. 삽입과 삭제의 연산은 탐색 연산에 종속적이며, 회전 및 색변경은 상수시간만 걸린다는 의미임.

• 2-3-4 트리를 이진 탐색 트리로 표현한 것: 빨강 노드와 그 부모 노드를 묶으면, 2-3-4 트리의 노드가 될 수 있음.
• ** 정리: 즉, 레드-블랙 트리는 2-3-4 트리를 이진 탐색 트리로 표현한 것임. **

---

✅ 2. B-트리

(1) B-트리란?

• t: 해당 트리 구조에 최소 차수를 의미한다. ( 즉, 각 노드가 가질 수 있는 최소한의 자식 노드 수를 의미함 )
• 즉, 해당 t 상수값을 가지고 밑에서 규칙을 정하는 개념으로 볼 수 있음.
• 성질1: 루트 노드는 1개 이상 2t개 미만의 오름차순 정렬된 키를 가짐. ( 1개도 가능하다는 말임 예외 상황으로 )
• 성질2: 루트 노드 제외 모든 노드는 t - 1 개 이상 2t 개 미만의 오름차순으로 정렬된 키를 가짐.
• 성질3: 내부 노드(루트를 제외한 노드)가 가진 키의 개수보다 하나 더 많은 자식 노드를 가진다는 의미.
• 성질4, 5: 이진 탐색 트리의 대소 비교에 대한 규칙과 동일함.
• 성질6: 모든 리프 노드의 레벨은 동일함.
• 정리: 루트 노드는 1개 이상 2t개 미만, 내부 노드는 t - 1개 이상 2t 개 미만의 오름차순 정렬된 키를 가지고, 모든 리프 노드의 레벨은 동일하다는 개념이 핵심임.

(2) B-트리 - 탐색 연산

• 2-3-4 트리와 동일하게 탐색을 진행함.

(3) B-트리 - 삽입 연산

• 삽입 연산: 2-3-4 트리와 동일하게, 루트 노드에서부터 탐색을 수행하고 리프 노드에도 존재하지 않으면 그때 해당 노드에 추가하지만, 2-3-4 트리의 노드 분할 과정과는 약간 차이가 존재함.
• 노드 분할: 탐색 과정에서 2t - 1개의 키를 갖는 노드(최대 차수를 가지는 노드)를 만나게 된다면, t = 3 번째 위치한 키인 30을 찾게 되며, t = 3 번째 키(30)를 기준으로 노드를 3개의 덩어리로 나누게 됨.
• 왼쪽 덩어리: t 번째 키보다 작은 키들 (1번부터 t - 1번까지) => (10, 20 -> t - 1 = 2)
• 중간 키: 정확히 t 번째 있는 키(30)로 무조건 1개임.
• 오른쪽 덩어리: t 번째 키보다 큰 키들 (t + 1번부터 2t - 1번까지) => (40, 50 -> t - 1 = 2)

• 삽입 키(18)을 예시로 들면, 루트 노드(10) 보다 크기 때문에 오른쪽 서브트리로 내려가게 되는데, 이때 (13, 19, 22, 26, 29) 로 2t - 1개의 키를 가지는 노드를 만나게 되고, 해당 노드를 분할을 하게 된다.
• 분할 과정: (13, 19, 22, 26, 29) 의 t 번째(3) 중앙 값인 22를 구한 뒤, 22를 부모 노드로 올려주게 된다. 이후, 왼쪽(13, 19) 부분과 오른쪽 (26, 29) 부분을 각각의 노드로 분할을 해주게 된다.
• 이후, 삽입 할 키(18)을 가지고 루트 노드(10, 22)에서 다시 탐색을 진행한 뒤, 10보다 크고, 22보다 작기 때문에 가운데 서브트리로 내려가게 되며, (13, 19) 가운데 서브트리로 또 내려가게 되면, 잎 노드로 내려가게 된다. 2t - 1개의 키를 가지지 않기 때문에 해당 부분에서 오름차순에 맞게 삽입이 되게 된다.

(4) B-트리 - 성능과 특징

1. 트리의 높이(h)만큼 내려가야 하므로 h번의 노드 방문이 필요함.
2. 한 노드 안에는 최대 2t-1개의 키가 있으므로, 순차 탐색을 하면 O(t) 시간이 걸림.
3. 따라서 전체 시간은 O(t*h) = O(th) 가 됨.

• O(th): 트리의 높이 h, 각 노드에서 키의 위치를 찾는 시간 O(t) 를 곱한 시간을 의미한다.
• O(th)는 일회성 탐색으로 볼 수 있고, 여기에 키의 개수 n이 증가함에 따라서 아래와 같이 log n 을 얻을 수 있음.

• O(log_t n): n은 키의 개수를 의미하며, 트리의 높이 자체가 log(3) 로그 시간에 비례하기 때문에 log 그리고, 키의 개수가 늘어남에 따라 시간 복잡도는 O(log n)이 된다.
• 레드-블랙 트리 최적화: 각 노드에서의 키 관리에 레드-블랙 트리를 이용하면 O(t) 시간이 들기 때문에 키가 증가하더라도, t 만큼의 상수 시간으로 관리가 가능하기 때문에 O(log t) 의 시간복잡도로 효율을 올릴 수 있음.

• 내부 탐색의 경우: t=2, t=3 정도의 작은 값으로 지정하면 가능함.
• 외부 탐색의 경우: 디스크를 사용하는 경우 t를 충분히 크게 지정, 한 노드의 크기가 디스크의 한 블록에 저장되도록 함.
• B-트리는 내부 탐색, 외부 탐색에 모두 활용이 가능함.

---

✅ 3. 해시 테이블

(1) 해싱이란?

• 해싱(Hashing): 데이터를 특정 숫자로 변환하는 '동작(행위)' 또는 알고리즘을 의미함.
• 해시 테이블(Hash Table): 해싱을 이용해 데이터를 저장하는 **'공간(자료구조)'**를 의미함.

• 기존 레드-블랙 트리, B-트리 등은 탐색 키(40)를 찾겠다고 하면, 키값의 대소를 비교하며 쭉 내려가는 원리였음.
• 하지만, 해싱은 해시테이블의 탐색 위치(40, 6번지)를 바로 찾아서 접근하는 탐색 방법으로 상수 시간 내에 저장, 삭제, 탐색을 할 수 있는 방법으로 볼 수 있음.

(2) 해싱 - 개념

• 키의 집합에서 키값을 해시 함수를 통해서 해시 테이블에 넣게 되는데, 이것이 해싱으로 볼 수 있음.
• 충돌: 키의 집합이 테이블보다 클 경우, 키값이 테이블에 같은 공간으로 매핑이 되는 현상이 생길 수 있는데 이걸 충돌이라함.
• 해당 충돌을 해결하는 방법을 통해서 이 문제를 해결 할 수 있음.

• 해싱이 적합한 형태의 응용 문제: 특정 키값 K를 갖는 데이터를 찾는 문제를 의미한다.
• (1) ~ (4)번까지는 모두 일일이 비교를 하며 탐색을 하는 과정이며, 해싱은 바로 찾을 수 있는 과정임.

(3) 해시 함수

• 해시 함수: 키값을 해시 테이블의 주소로 변환하는 함수를 의미한다.

• 함수의 종류: 정수를 사용하는 제산 잔여법, 중간 제곱법 등과 문자열을 위한 함수(비닝, 단순 합, 가중 합) 등이 존재함.
• 바람직한 해시 함수: 해시 함수를 현재 문제에 맞게 사용하는 것을 바람직한 해시 함수라고 함.
• 계산이 용이해야 함: 키값을 해시 테이블의 주소로 변환하는 계산 자체가 간단하면 좋음.
• 적은 충돌 발생: 각 키를 테이블의 각 슬롯에 균등하게 사상(매핑) 시킴으로써, 충돌을 최소화 하면 좋음.

(4) 해시 함수 - 제산 잔여법

• 제산 잔여법: 키 값을 해시 테이블의 크기(M)로 나눈 나머지를 주소로 사용하는 방법임.

• K: 저장하려는 데이터의 키값 (숫자)
• M: 해시 테이블의 전체 크기
• h(K): 계산된 결과값으로 실제 데이터가 들어갈 테이블의 인덱스(주소)임.
• 예시: 키값 123을 크기가 11인 테이블에 넣는다면, 123 mod 11 = 2번 인덱스에 저장을 시킴.

(1) 컴퓨터는 모든 숫자를 2진수로 처리하며, M이 2의 거듭제곱인 16(2^4)이라고 가정
(2) 어떤 숫자를 16으로 나눈 나머지는, 그 숫자의 2진수 마지막 4자리와 정확히 일치합니다.
키 A: ...1010 0111 (10진수 167) -> 나머지: 7 (0111)
키 B: ...1111 0111 (10진수 247) -> 나머지: 7 (0111)
결과: 10진수 마지막 수인 7이 결국 나머지가 되며, 충돌 가능성이 매우 높아짐!!!

• M의 선택에 주의: M = 2의 거듭제곱 형태를 피하는게 중요하며, 이유는 키값 10진수를 2의 거듭제곱을 나눈 나머지를 나누게 된다면, 항상 10진수의 마지막 수가 나머지로 나오기 때문에 랜덤하게 숫자가 들어가는 것이 아닌, 특정 칸에만 데이터가 몰려서 충돌 가능성이 매우 높아질 수 있는 문제가 있음.
• 그렇기 때문에, M은 2의 거듭제곱과 상당한 차이가 있는 소수로 선택하는 것이 바람직함.

(5) 해시 함수 - 비닝

• 비닝: 키값의 범위(U)를 해시 테이블의 크기(M) 등분하여 각 등분을 각 슬롯으로 해시 하는 함수임.

[ 비닝 ]
- 전체 키 범위: 0 ~ 999 (총 1,000개)
- 테이블 크기: 10칸
- 한 칸당 들어갈 범위: 1000 / 10 = 100개씩

[ 따라서 키값 / 100 을 한 몫이 곧 주소가 됨. ]
0 ~ 99 사이 숫자는? -> 몫이 0이므로 슬롯 0
100 ~ 199 사이 숫자는? -> 몫이 1이므로 슬롯 1
800 ~ 899 사이 숫자는? -> 몫이 8이므로 슬롯 8

• 쉽게 말해, 전체 키 범위와 테이블 크기를 나누면 한 칸당 들어갈 범위를 구할 수 있으며, 따라서 키값 / 100을 나누게 되면, 어떤 슬롯에 들어갈지 바로 구할 수 있음.
• 단점: 삽입 키가 범위가 비슷한 경우 똑같은 슬롯 하나에만 미친 듯이 몰릴 수 있음. 즉, 상위 비트의 분포가 고르지 못하면 몇 개의 슬롯에 집중이 되는 문제라고 볼 수 있음.

(6) 해시 함수 - 중간 제곱법

• 중간 제곱법: 키값을 제곱한 뒤, 그 숫자의 정중앙 부분만 쏙 빼서 주소로 쓰는 방법임.

• K^2: 키값(123)을 제곱하게 되면, 제곱값(15,129)이 나오며, 이걸 2진수(11 1011 0001 1001)로 바꿀 수 있다.
• /2^m: 키값을 제곱한 값에 2^m(7) 의 값을 나누는 과정이며, 이 과정은 기존 제곱값의 2진수 오른쪽 끝에서 7비트를 제거하는 것과 같은 과정임.
• r: 해시 주소로 취할 비트의 크기
• mod 2^r: 제곱 후 하위 비트까지 버린 상태에서 mod 2^r 을 통해 오른쪽 끝에서 부터 r만큼의 비트수만 남기는 과정임.
• 모든/대부분의 비트가 결과 생성에 기여: 어느 한 숫자도 소외되지 않고 주소 결정에 참여한다.
• 지배적인 영향을 받지 않는다: 데이터의 특정 부분이 중복되어도 주소는 중복되지 않고 랜덤하게 잘 퍼진다.

(7) 해시 함수 - 문자열 비닝

• 비닝 방식에 키값이 정수가 아닌 문자열이 주어진 경우를 의미한다.

• 문자열의 앞쪽 일부를 해시 결과로 사용하며, 예를들면 A~Z 까지 26개의 슬롯으로 해시를 해줌으로써 슬롯에 넣음.
• 단점: 입력 문열의 앞쪽의 중복이 많아 질수록 슬롯에 고르게 분포되지 못함.

(8) 해시 함수 - 문자열 단순 합(제산 잔여법 적용)

• 문자열의 각 문자들을 더한 후 제산 잔여법 적용(테이블 크기로 나눈 몫)에 해당하는 슬롯에 넣는 방식임.
• 예를들면, 각 문자의 아스키코드에 맞는 정수를 더한 값 775 를 해시 테이블 크기 100을 나누게 되면 75를 얻을 수 있음.
• 각 문자를 더한 값 sum 이 해시테이블 크기(M) 보다 클 경우에 유용한 방식임.
• 단점: 짧은 문자열에 대해서는 비효과적이며, 문자열이 다르더라도 동일한 문자들에 대한 숫자가 같다면, 충돌문제 있음.
• 즉, 문자의 출현 순서는 고려되지 않는다는 단점이 있음. 이걸 해결하기 위한게 아래 가중 합임.

(9) 해시 함수 - 문자열 가중 합(제산 잔여법 적용)

• 각 문자의 코드값에 자리에 따른 가중치를 곱한 값을 합한 후 제산 잔여법을 적용하는 방식임.
• 쉽게 말해, 자리에 따른 곱한 값을 가중치로 점점 높여가며, 제산 잔여법을 적용하는 방식으로 보면 됨.

(10) 충돌 해결 방법

• 충돌: 서로 다른 키값 x,y 에 대해여 h(x) = h(y) 인 경우이며, 쉽게 말해 다른 키값들을 넣을 때 같은 위치에 저장이 되는 것을 충돌이라고 생각하면 됨.
• 충돌 해결 방법: 크게 개방 해싱법, 폐쇄 해싱법 두 가지로 나눌 수 있음.
• 개방 해싱: 연쇄법으로 부르며, 충돌된 데이터를 테이블 밖의 별도의 장소에 저장 및 관리하는 방식 ( 연결 리스트 사용 )
• 폐쇄 해싱: 개방 주소법으로 부르며, 해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장 및 관리하는 방식임.
• 폐쇄 해싱의 종류로는 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱 등이 있음.

(11) 충돌 해결 방법 - 개방 해싱

• 개방 해싱: 충돌이 된 키값들을 같은 위치에 저장하되 연결 리스트에 이어서 저장을 하는 방식임. ( 연쇄법 개방 해싱 )
• 해시 테이블과 연결 리스트가 주기억장치 내에서 유지될 때 적합하며, 이유는 디스크로 관리가 되면 연결 리스트의 노드 접근이 결국 디스크에 접근으로 여러 번 접근 하면 오버헤드가 큼.

(12) 충돌 해결 방법 - 폐쇄 해싱 (버킷 해싱)

• 폐쇄 해싱: 개방 주소법으로 부르며, 해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장 및 관리하는 방식임.
• 버킷 해싱: 폐쇄 해싱의 한 종류로 테이블을 여러개의 그룹(버킷)으로 묶은 뒤, 충돌이 일어날 경우 같은 버킷 내에서 빈자리를 찾아서 들어가는 방식임.
• 만약 버킷 내의 공간이 다찼을 경우: 모든 버킷이 공유하는 오버플로 버킷에 들어가게 되는 원리임.
• 디스크에 저장된 해시 테이블 구현에 적합하며, 버킷 크기 = 디스크 크기, 오버플로는 작게 유지를 하는게 좋음.

(13) 충돌 해결 방법 - 폐쇄 해싱 (선형 탐사)

• 폐쇄 해싱: 개방 주소법으로 부르며, 해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장 및 관리하는 방식임.

• 탐사 순서: 슬롯 내의 빈 자리를 찾으러 다니는 경로를 의미하며, 처음 p(K, 0) = h(K) 는 처음엔 원래 내 주소(홈 위치)를 확인하며, 거기 누가 있다면 다음 후보지인 p(K, 1), p(K, 2) ... 형식으로 빈칸이 나올 때까지 반복하는 게 "탐사"임.
• 이러한 탐사 순서의 계산 방법에 따라 성능의 차이가 발생하며, 종류도 선형 탐사, 이차 탐사, 이중 해싱 등으로 나뉨.
• 즉, 빈 자리를 어떤 규칙(간격)으로 찾아다닐 것인가에 따라서 달라지는 것으로 보면 쉬움.
• 선형 탐사: i(반복 되는 숫자 0~M-1) 를 늘리면서, 빈 슬롯을 찾을 때까지 테이블의 다음 슬롯을 탐사하는 방식임.
• 선형 탐사 특징: 가장 간단하지만 성능이 매우 안좋은 최악의 방법임.

• 충돌이 나면 위와 같이 그 아래로 반복적으로 내려가면서 빈 슬롯을 찾아서 넣는 방식으로 보면 됨.
• 만약 맨 아래로 내려갔을 때에도 못 찾을 경우 다시 올라가서 빈 슬롯을 찾아서 넣게 됨.
• 즉, 모든 슬롯이 새로운 데이터가 삽입될 후보가 될 수 있음.

[ 1차 클러스터링 문제 ]
- (1) 선형 탐사는 충돌이 나면 바로 옆 칸을 확인 함.
- (2) 우연한 충돌: 데이터 몇개가 우연히 근처 슬롯에 저장 (예: 2,3번 슬롯 점유)
- (3) 덩어리 형성: 2,3번 들어가려던 새로운 데이터는 4번으로 밀려남 (예: 2,3,4번 슬롯 점유)
- (4) 자석 효과: 저렇게 연속적으로 저장이 되게 된다면, 덩어리가 커질 수 있음.
즉, 덩어리가 커질수록 그 구역에 걸릴 확률이 높아지며, 1,2,3,4번중 들어가게 되면 5번으로 밀림.
- (5) 폭발적 증가: 덩어리가 길어질수록 새로운 데이터가 이 덩어리에 합류할 확률이 점점 높아지며,
빈칸을 찾기 위해 탐사해야 하는 횟수가 급격히 늘어날 수 있음.

• 1차 클러스터링 문제: 긴 탐사 순서를 만들어 평균 탐색 시간의 증가를 초래 할 수 있는데, 쉽게 말해 선형 탐사는 충돌이 나면 바로 옆 칸을 확인 후 빈 슬롯에 넣어주는데, 이것이 결국 악순환을 초래할 수 있음.
• 1,2,3,4,5,6,7... 으로 데이터가 삽입이 될 확률이 높아, 이렇게 연속적으로 넣어진다면 특정 범위의 큰 덩어리가 많들어져 매번 새로운 데이터를 넣을 때마다 해당 덩어리에 걸릴 확률이 높아져 결국 탐사하는데 횟수가 급격히 늘어날 수 있음.

(14) 충돌 해결 방법 - 폐쇄 해싱 (이차 탐사)

• 선형 탐사의 1차 클러스터링 문제를 해결하기 위해서 등장한 것이 이차 탐사 이다.

• 이차 탐사: 기존 선형 탐사의 경우 i번째 마다 빈 칸을 찾았다면, 이차 탐사는 i^2 만큼 거리를 벌려가며 충돌이 발생하는 횟수의 제곱 형태로 탐사 순서를 결정하는 방식임.
• 장점: 서로 다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가질 수 있음.

• 예를들면, 이와 같이 2007의 키값이 7번에서 충돌이 났을 때, K + i^2 mod 10 = 2007 + 1 mod 10 = 8 로 8번 슬롯으로 넘어가서 빈 칸을 확인 후 키값이 이미 존재하므로, 다음  K + i^2 mod 10 = 2007 + 4 mod 10 = 1 로 1번 슬롯으로 넘어가 빈 칸 확인 후 키값이 또 존재하므로, K + i^2 mod 10 = 2007 + 9 mod 10 = 6 이 나오고 6번 슬롯은 비어있으므로, 그곳에 키값을 삽입하는 원리임.
• 이와 같이 i 가 늘어남에 따라서 제곱도 같이 해주기 때문에 거리를 벌리면서 찾아가게 될 수 있음.

• 문제점: 모든 슬롯이 탐사 순서에 사용이되지 않는 문제점이 있음.
• 2차 클러스터링 문제: 동일한 홈 위치를 갖는 두 키는 동일한 탐사 순서를 가질 수 있는 문제가 있음.
• 즉, 동일한 홈 위치를 가지기 때문에 동일한 탐사 순서를 가져 결국 한 번 거쳐간 과정을 또 거쳐가는 문제가 있는 것임.

(15) 충돌 해결 방법 - 폐쇄 해싱 (이중 해싱)

• 1차 클러스터링 문제, 2차 클러스터링 문제를 동시에 해결하기 위해서 등장한 것이 이중 해싱임.
• 즉, 클러스터링(데이터가 특정 구역에 뭉치는 현상)을 효과적으로 방지하기 위해 고안된 것임.

• 이중 해싱: 해시 함수 2개를 사용하는데, h1(K) 는 데이터가 처음 들어갈 홈 위치를 결정하며, h2(K) 는 충돌이 발생했을 때 건널 뛸 보폭(간격)을 결정하는 원리임. 즉, 키값(K) 자체가 다르면 보폭이 달라지기 때문에 유연함.
• 좋은 이중 해싱을 구하려면: 탐사 순서에 있는 모든 상수가 해시 테이블의 크기 M과 서로 소가 되어야 하며, 이는 테이블 전체를 다 돌아보지 못하고 일부 칸만 무한 반복해서 돌게 될 위험을 막기 위한 것임.

(16) 해시 테이블 - 삭제 연산

• 데이터 삭제 시 발생하는 문제: 충돌이 발생하면 정해진 규칙에 따라 옆 칸으로 이동하며 데이터를 저장하는데, 문제는 A를 저장하려다 충돌이 나서 B를 그 다음 칸에 저장하고, A를 삭제 한 뒤 만약 B를 탐색하는 과정에서 A를 먼저 보고 B로 가는 과정을 거칠텐데, A가 있던 빈 칸을 보고 B는 존재하지 않을 것이라고 판단 한 뒤, 탐색을 멈춰버리는 문제임.
• 비석: 삭제 이후에 여기는 원래 데이터가 있었지만 지금은 비어있다는 특별한 표식을 남기는 것을 의미함.
• 단점: 비석의 개수가 증가할수록 평균 탐색 거리가 증가 할 수 있는 문제가 있음.