# Conflict resolution and search time analysis in Hash Table (2/3)

**Contents**

---

**1️⃣** 충돌 해결 방법 #1 - 체이닝 (Collusion resolution - Chaining)  
**2️⃣** 충돌 해결 방법 #2 - 개방 주소 (Collusion resolution - Open Addressing)  
**3️⃣** 해시 테이블의 검색 시간 (Search time analysis in Hash Table)

---

# Summary

### 충돌 해결 방법 (Collision Resolution Methods)

* **체이닝**(Chaining): 충돌이 발생하면 해당 슬롯에 **연결 리스트**(linked list)를 사용해 여러 값을 저장하는 방법. 충돌이 발생한 값들을 리스트로 연결하여 저장하므로, 해시 테이블 자체의 크기를 변경할 필요가 없다.
    
* **개방 주소법**(Open Addressing): 충돌이 발생하면 다른 **빈 슬롯**을 찾아 값을 저장하는 방법. 이를 위해 **선형 조사**(Linear Probing), **이차원 조사**(Quadratic Probing), **더블 해싱**(Double Hashing) 등의 방법이 있다.
    

### 해시 테이블의 검색 시간 (Search Time in Hash Tables)

* 검색 시간은 주로 **적재율**(Load Factor, α\\alphaα)에 영향을 받는다. 적재율이 높으면 충돌이 증가하여 검색 시간이 길어질 수 있다.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730947925260/b91e7293-3ae3-4edf-93fc-e072c070879d.png align="center")

---

## **1️⃣** 충돌 해결 방법 #1 - 체이닝 (Collusion resolution - Chaining)

### **해시 테이블의 충돌**(Hash Table Collision)

**<mark>💡요약: </mark> 해시 테이블 충돌**(Hash Table Collision)이란 하나의 슬롯에 두 개 이상의 데이터가 저장되어 충돌이 발생하는 상황이다. 이를 해결하기 위한 여러 방법이 있으며, 충돌 관리 기법을 통해 해시 테이블의 효율성을 유지할 수 있다. 오늘 그 해결 방법에 대해 공부한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730938861576/7ba9a0a9-90b4-4a08-ae5d-d691270fad6a.png align="center")

해시 테이블은 데이터를 효율적으로 저장하고 검색하는 자료 구조입니다. 그러나 **충돌**(collision)이 발생할 수 있습니다. **충돌**이란 하나의 슬롯에 두 개 이상의 데이터가 할당될 때 생기는 문제입니다. 위의 이미지에서, 해시 함수 h(x)=xmod  13h(x) = x \\mod 13h(x)=xmod13을 사용하여 데이터를 저장하려고 할 때 29를 삽입하면 이미 16이 저장된 슬롯(슬롯 번호 3)에 할당됩니다. 이렇게 되면 데이터가 중복되어 문제를 발생시키는 상황이 됩니다.

**💡예시: 해시 함수**(Hash Function) 설정 `h(x) = x mod 5`

* 데이터를 차례대로 삽입: 12, 7, 10
    
* 12를 넣으면 `12 mod 5 = 2`, 슬롯 2에 저장
    
* 7을 넣으면 `7 mod 5 = 2`, 슬롯 2에 저장하려고 하자 **충돌**(collision) 발생
    

또한 실생활에서도 흔히 발생하는 문제로, 예를 들어 우체통에 동일한 주소가 여러 번 나오는 것과 비슷한 개념이다.

---

### **충돌의 해결방법**(Collision Resolution)

: **체이닝**(Chaining) & **개방주소**(Open Addressing)

**<mark>💡요약: </mark>** 충돌을 해결하는 방법에는 **체이닝**(Chaining)과 **개방주소**(Open Addressing)가 있다. 체이닝은 충돌된 데이터를 **연결 리스트**로 저장하고, 개방주소는 테이블 내 빈 슬롯을 찾아 저장하는 방식이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730939527602/67f32d15-a485-4212-8613-6bc19fee266d.png align="center")

☑️ **체이닝(Chaining)**: 같은 주소로 매핑된 데이터를 **연결 리스트**(linked list)로 연결하여 저장한다. 이 방법을 사용하면 한 슬롯에 여러 데이터를 연결하여 충돌 문제를 해결할 수 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730939574986/a4c74a20-7223-4c02-825e-8888e7350293.png align="center")

☑️ **개방주소(Open Addressing):** 충돌이 발생하면 다른 빈 공간에 데이터를 할당하는 방식이다. 추가적인 **연결 리스트**(linked list)가 필요 없고, 테이블 내에서 빈 공간을 찾아 데이터를 재배치한다.

**💡예시**

* 체이닝: 해시 함수 `h(x) = x mod 3`을 사용하고 데이터 9, 12, 15를 삽입할 때 9과 12는 같은 슬롯에 저장된다. 이 경우, **체이닝**을 사용하여 12를 9와 연결하여 저장한다.
    
* 개방주소: 같은 상황에서 개방주소를 사용하면, 12가 들어갈 다른 빈 공간을 찾아 저장하게 된다.
    

---

### **충돌의 해결방법**(Collision Resolution) #1

: **체이닝의 예**(Example of Chaining)

**<mark>💡요약: </mark>** 체이닝을 사용하면 **충돌이 발생했을 때** 같은 슬롯에 여러 데이터를 **연결 리스트**(linked list)로 저장하여 문제를 해결할 수 있다. 새로운 값은 항상 리스트의 **맨 앞**에 삽입하여 접근 속도를 높인다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730939635767/f4fc0762-8db5-4e45-9484-e1f52b49dfbd.png align="center")

체이닝은 **충돌 해결 방법**(collision resolution)의 대표적인 방법 중 하나로, **해시 함수**(hash function)를 사용하여 같은 슬롯에 할당되는 값을 **연결 리스트**(linked list)로 저장하는 방식이다. 위 예에서는 `h(x) = x mod 13` 해시 함수를 사용하여 값을 할당하려고 한다.

* 값 **39**와 **13**은 해시 함수 `x mod 13`에 따라 슬롯 0에 할당되었다. **13**은 **39**와 충돌하기 때문에, 39의 뒤에 연결 리스트로 연결된다.
    
* 슬롯 3에서는 **94**, **3**, **42**, **55**가 순서대로 연결 리스트를 통해 연결되어 있다.
    
* 슬롯 8에서도 **86**과 **47**이 연결 리스트로 연결되어 있으며, 충돌이 발생해도 데이터를 저장할 수 있음을 보여주고 있다.
    

충돌이 일어날 때마다 새로운 데이터는 **리스트의 맨 앞**(front of the list)에 삽입하여 효율을 높인다.

**💡예시:** 해시 함수 `h(x) = x mod 7`을 사용.

* 데이터: 10, 3, 17
    
* 10을 넣으면 `10 mod 7 = 3`, 슬롯 3에 저장.
    
* 3을 넣으면 `3 mod 7 = 3`, 같은 슬롯에 저장하려고 하니 충돌 발생 → **체이닝**으로 10의 앞에 3을 연결. \[3, 10\]
    
* 17을 넣으면 `17 mod 7 = 3`, 다시 충돌 발생 → **체이닝**으로 3의 앞에 17을 연결. \[17, 3, 10\]
    

---

### **충돌의 해결방법**(Collision Resolution) #1

: **체이닝 의사코드**(Pseudocode for Chaining)

**<mark>💡요약: </mark>** 체이닝 방식의 해시 테이블에서는 **삽입**(Insert), **검색**(Search), **삭제**(Delete) 작업을 통해 데이터를 효율적으로 관리할 수 있다. 각 작업은 리스트를 이용하여 충돌이 발생하더라도 문제를 해결할 수 있도록 설계되었다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730939983331/f4d4ab6b-1c1e-400e-bea4-cefa5a1d734d.png align="center")

체이닝을 사용한 해시 테이블에서 가장 중요한 세 가지 작업은 **삽입**(Insert), **검색**(Search), 그리고 **삭제**(Delete)이다.

1. **chainedHashInsert(T\[\], x)**: 이 함수는 원소 `x`를 해시 테이블 `T`의 적절한 리스트에 삽입한다. 삽입할 때, **리스트의 맨 앞**(front of the list)에 삽입하여 효율을 높인다.
    
2. **chainedHashSearch(T\[\], x)**: 해시 테이블 `T`의 적절한 리스트에서 값 `x`를 찾는다. 충돌이 발생한 경우에도 리스트를 통해 원하는 값을 빠르게 찾을 수 있다.
    
3. **chainedHashDelete(T\[\], x)**: 해시 테이블 `T`의 적절한 리스트에서 값 `x`를 삭제한다. 리스트에서 특정 노드를 찾아 제거하는 과정이 필요하다.
    

여기서, `T`는 해시 테이블이고, `x`는 삽입, 검색, 삭제할 데이터이다. `h(x)`는 해시 함수로, 주어진 값을 특정 슬롯에 할당하는 역할을 한다.

**💡예시:** 해시 함수 `h(x) = x mod 3`을 사용한다고 가정하자

* **삽입**: `chainedHashInsert(T, 6)`을 호출하면, `6 mod 3 = 0`이므로 슬롯 0의 리스트에 `6`을 삽입한다.
    
* **검색**: `chainedHashSearch(T, 6)`을 호출하여 슬롯 0에서 `6`을 찾는다.
    
* **삭제**: `chainedHashDelete(T, 6)`을 호출하여 슬롯 0의 리스트에서 `6`을 삭제한다.
    

---

### **충돌의 해결방법**(Collision Resolution) #2

: **개방 주소 방법의 개요**(Overview of Open Addressing)

**<mark>💡요약: </mark> 개방 주소**(Open Addressing)는 해시 테이블에서 빈 슬롯을 찾을 때까지 새로운 **해시 값**(hash value)을 반복 생성하여 데이터를 저장한다. 충돌이 발생해도 빈 공간이 있을 때까지 다른 슬롯을 찾아 데이터를 삽입한다. 이를 통해 충돌을 해결하고 데이터를 해시 테이블에 안전하게 저장할 수 있게 된다.

**개방 주소 방법**으로 슬롯을 찾는 과정은 다음과 같다.

1. 입력값 `x`로 해시 함수를 적용하여 첫 번째 해시 값 h\_0​(x)을 생성한다.
    
2. h\_0​(x)의 슬롯이 비어 있다면, 그곳에 `x`를 삽입하고 작업을 종료한다.
    
3. h\_0​(x) 슬롯이 이미 차 있으면, 다음 해시 값 h\_1(x)을 생성하여 다른 슬롯을 시도한다.
    
4. 빈 슬롯이 나올 때까지 h\_2(x), h\_3(x) 등 새로운 해시 값을 생성하여 반복한다.
    

**💡예시:** 해시 함수 `h(x) = (x + i) mod 7`를 사용한다고 가정하고, `i`는 0부터 시작하여 1씩 증가한다.

* 데이터를 10을 삽입하려고 할 때:
    
    * 첫 번째 해시 값: h\_0(10) = (10+0) mod  7 = 3
        
    * 슬롯 3이 비어 있으면 10을 삽입한다.
        
* 만약 슬롯 3이 차 있다면, 다음 해시 값을 생성하여 빈 슬롯을 찾는다.
    
    * h\_1(10) = (10+1) mod  7 = 4
        
    * 슬롯 4가 비어 있으면, 10을 그곳에 삽입한다.
        

---

### **충돌의 해결방법**(Collision Resolution) #2

: **개방 주소 방법의 유형**(Types of Open Addressing)

**<mark>💡요약: </mark> 개방 주소 방법**(Open Addressing)에서는 **선형 조사**(Linear Probing), **이차원 조사**(Quadratic Probing), **더블 해싱**(Double Hashing)을 통해 충돌이 발생한 데이터를 다른 슬롯에 저장할 수 있다. 각 방법은 슬롯을 찾는 방식에 차이가 있는데 그 이유로는 각 방식이 다양한 상황에서 다른 장단점을 제공하기 때문에, 특정 요구사항에 맞춰 선택할 수 있도록 여러 방식이 고안되었다.

개방 주소 방식에는 세 가지 주요 방법이 있다. 각각의 방법은 **충돌이 발생했을 때 빈 슬롯을 찾는 방법**에 차이가 있다.

**☑️선형 조사(Linear Probing)**

* **특징**: 충돌이 발생할 때 한 칸씩 이동하며 빈 슬롯을 찾는 방식
    
* **장점**: 구현이 간단하고, 메모리 접근 패턴이 순차적이기 때문에 **캐시 효율**이 높다.
    
* **단점**: **클러스터링**(Clustering) 문제가 발생할 수 있다. 데이터가 한 곳에 몰리게 되어 새로운 데이터를 삽입할 때 많은 충돌이 생길 수 있다.
    

**☑️ 이차원 조사(Quadratic Probing):**

* **특징**: 이동 간격이 점점 커지면서 빈 슬롯을 찾는다. 예를 들어, 첫 번째 충돌 시 1칸, 두 번째 충돌 시 4칸, 세 번째 충돌 시 9칸 등, **2차 함수**에 따라 이동한다.
    
* **장점**: **1차 클러스터링 문제**를 줄일 수 있다. 데이터가 한 곳에 몰리는 현상이 덜 발생하여, 선형 조사보다 충돌 관리에 효율적이다.
    
* **단점**: 슬롯이 고르게 분포되지 않으면 특정 슬롯에 접근할 수 없는 경우가 생길 수 있다. 따라서 해시 테이블 크기를 잘 설정해야 한다.
    

\*\*  
☑️ 더블 해싱(Double Hashing):\*\*

* **특징**: 두 개의 해시 함수를 사용해 충돌이 발생할 때마다 다른 해시 함수의 결과로 이동한다.
    
* **장점**: **이차 클러스터링**(secondary clustering)을 피할 수 있어, 데이터가 고르게 분포되기 때문에 충돌이 적고, 테이블이 꽉 차기 전까지 성능이 매우 좋다.
    
* **단점**: 구현이 복잡하고, 두 개의 해시 함수를 잘 선택하지 않으면 오히려 비효율적일 수 있다.
    

**💡예시:** 해시 함수 `h(x) = x mod 7`로 데이터를 저장한다고 가정하자.

* **선형 조사**: 데이터 10을 저장하려고 하다가 슬롯이 이미 차 있으면, 다음 슬롯을 한 칸씩 이동하여 빈 슬롯을 찾는다. **캐시 효율성**이 중요하다면 선형 조사가 유리할 수 있다.
    
* **이차원 조사**: 충돌이 발생하면, `h(x) + 1^2`, `h(x) + 2^2`, `h(x) + 3^2` 순으로 빈 슬롯을 찾는다. **클러스터링 문제**를 줄이고 싶다면 이차원 조사가 더 적합할 수 있다.
    
* **더블 해싱**: 첫 번째 해시 값 `h1(x)`로 충돌이 발생하면, 두 번째 해시 함수 `h2(x)`를 사용해 빈 슬롯을 찾아간다. **데이터가 고르게 분포**되도록 하고 싶다면 더블 해싱이 좋은 선택이다.
    

---

### ❓ 입력 데이터의 특성에 따라 달라지는 개방 주소 방법의 선택지❓

데이터 값이 **랜덤하게 주어진다면** 선형 조사만으로도 충분히 좋은 성능을 낼 수 있다. 데이터가 고르게 분포될 확률이 높기 때문에, 슬롯에 골고루 저장될 가능성이 크기 때문이다.

그러나 데이터가 특정 구간에 **밀집되어 있는 경우**라면, 선형 조사를 사용할 경우 계속 같은 공간에 데이터가 몰리게 되어 충돌 확률이 높아지게 된다. 이런 상황에서는 이차원 조사나 더블 해싱 같은 방식을 사용하여 데이터를 좀 더 **고르게 분포**시키는 것이 좋다.

따라서 개방 주소 방식이 다양한 이유는 **입력 데이터가 어떻게 분포되어 있느냐에 따라 충돌 해결 방법을 선택할 필요가 있기 때문**이다.

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #1

: **선형 조사**의 예 (Example of Linear Probing)

**<mark>💡요약:</mark>** 아래 이미지는 **선형 조사**를 사용해 데이터를 충돌 없이 저장하는 과정을 시각적으로 설명하며, 각 입력값이 슬롯을 찾는 과정을 보여주고 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730941657576/5cd1d0f3-f54f-4e7d-8cac-3a98c3a31a1b.png align="center")

선형 조사는 **개방 주소 방식**(Open Addressing) 중 하나로, **충돌**(collision)이 발생할 때마다 **한 칸씩 이동**하여 빈 슬롯을 찾는 방식이다. 여기서 사용하는 **해시 함수**(hash function)는 h\_i(x) = (h(x) + i) mod 13로, 충돌이 발생하면 `i` 값을 증가시켜 다음 슬롯을 검사한다.

* 입력값은 25, 13, 16, 15, 7, 28, 31, 20, 1, 38 순서로 들어온다
    
* 각 값이 해시 함수에 따라 슬롯에 저장된다.
    
* 예를 들어, **28**을 넣을 때 슬롯 4에 이미 데이터가 있어 충돌이 발생하면, 한 칸씩 이동하여 빈 슬롯을 찾고, 슬롯 4에 **28**이 저장된다.
    
* **20**을 넣을 때도 슬롯 8이 비어 있으므로 그대로 삽입된다.
    
* **38**은 슬롯 6에 삽입된다.
    

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #1

: **선형 조사의 단점**(Limitations of Linear Probing)

**<mark>💡요약: </mark> 선형 조사**(Linear Probing)는 간단하고 효율적일 수 있지만, 이 방식에는 **1차 군집**(Primary Clustering)이라는 문제가 있다. **1차 군집**이란 특정 영역에 데이터가 몰려있는 현상으로, 이로 인해 추가적인 충돌이 발생하기 쉽고, 새로운 데이터를 삽입할 때 더 많은 이동이 필요해진다. 결과적으로 테이블의 성능을 저하시키는 것이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730941897906/4b0d8960-2ab3-449e-9efa-d70bfc3b3625.png align="center")

* 입력값 15, 16, 28, 37, 31, 44, 29가 주어졌을 때 각 데이터가 해시 함수 `h(x) = (x + i) mod  13` 에 따라 해시 테이블에 배치된다.
    
* **15**는 슬롯 2에 저장되고, **16**은 슬롯 3에 저장된니다.
    
* **28**이 들어올 때 슬롯 4가 비어 있어 저장된다.
    
* **44**와 **29**가 추가될 때, 앞 슬롯들이 이미 차 있기 때문에 계속 다음 슬롯으로 이동하면서 빈 자리를 찾게 된다.
    
* 이 과정에서 데이터가 특정 영역(슬롯 2~7)에 몰리면서 **1차 군집** 문제가 발생하게 된다.
    

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #2

: **이차원 조사**(Quadratic Probing)

**<mark>💡요약: </mark>** 1차 군집을 방지하여 충돌을 해결하는 더 나은 방법으로는 **이차원 조사**(Quadratic Probing)가 있다. 선형 조사보다 **1차 군집**(Primary Clustering) 문제에 강한 해시 테이블 충돌 해결 방식이다. 충돌이 발생할 때마다 2차 함수에 따라 이동 간격이 점점 커지므로, 데이터가 특정 구간에 몰리지 않고 더 **균일하게 분포**(spread out)될 수 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730942056967/f0595f68-b506-4bff-bf0b-5dd72942408f.png align="center")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730942168357/0949d1e4-59d7-41cc-923b-70b8ebb8f9ea.png align="center")

여기서 `h(x)`는 기본 해시 함수, `c_1`과 `c_2`는 상수이며, `i`는 충돌 횟수이다. 충돌이 발생할 때마다 `i` 값을 증가시키며 2차 함수에 따라 다른 슬롯을 시도한다.

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #2

: **이차원 조사의 예**(Example of Quadratic Probing)

**<mark>💡요약: </mark>** 충돌이 발생할 때마다 보폭을 `i²`로 설정하여 이동하는 방식으로, **보폭을 2차 함수**(quadratic function)로 증가시키며 빈 슬롯을 찾는 방법이다. **1차 군집** 문제를 줄이는 데 효과적이다. 충돌이 발생할 때마다 h\_i(x) = (x+i²) mod  13과 같이 보폭이 `i²` 로 주어진다. 이로인해 탐색이 한 칸씩 이동하지 않고, 이동 거리가 점점 커지기 때문에 특정 영역에 데이터가 몰리는 것을 방지할 수 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730942262683/cf8f98b5-3657-474e-8508-b0f3d4448e7c.png align="center")

* 입력값: 15, 18, 43, 37, 45, 30
    
* 각 값을 해시 함수에 따라 슬롯에 저장다.
    
* **30**을 해시 테이블에 삽입할 때:
    
    * h\_0(30): 첫 번째 슬롯은 4지만 이미 차 있어서 충돌이 발생한다.
        
    * h\_1(30): 다음 보폭은 i² = 1² = 1 이므로 슬롯 5를 시도하지만, 이 역시 차 있다.
        
    * h\_2(30): 다음 보폭은 i² = 2²= 4 이므로, 슬롯 8로 이동하여 비어 있는지 확인한다. 슬롯 8이 비어 있으므로, **30**을 그곳에 삽입한다.
        

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #2

: **선형조사와 이차원군집 비교** (Comparison between Liner Probing and Quadratic Probing)

**이차원 조사**를 통해 데이터가 해시 테이블 내에서 보다 고르게 분포하는 과정을 소개한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730943008558/5d6fd755-e041-40d1-8909-d81b280e8518.png align="center")

* 입력 순서: 15, 16, 28, 37, 31, 44, 29
    
* **1차 군집 발생**:
    
    * 왼쪽 그림은 선형 조사로 충돌을 해결하려 할 때, 데이터가 슬롯 2부터 연속적으로 몰리는 **1차 군집** 문제가 발생하는 것을 보여주고 있다.
        
* **이차원 조사 적용**:
    
    * 오른쪽 그림에서 이차원 조사를 사용하여 충돌을 해결하는 경우, 보폭이 i²로 설정되어 충돌이 발생할 때마다 더 멀리 떨어진 슬롯을 찾아간다.
        
    * 예를 들어, **28**이 슬롯 4에 저장되고, 이후 충돌이 발생하는 **44**와 **29**는 각각 h\_1(44) 과 h\_2(29)에 따라 더 떨어진 슬롯에 저장된다.
        

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #2

: **이차원 조사**의 단점 (Disadvantage of Quadratic Probing)

**<mark>💡요약: </mark> 이차원 조사**(Quadratic Probing)는 충돌을 해결하기 위해 보폭을 2차 함수로 설정하지만, **2차 군집** 문제로 인해 데이터가 특정 슬롯에 몰리는 현상이 발생할 수 있다. 2차 군집은 여러 개의 원소가 동일한 **초기 해시 함수 값**을 가질 때 발생하며, 이로 인해 같은 순서로 슬롯을 탐색하게 되는 현상을 뜻한다. 이로 인해 해시 테이블의 효율이 떨어지게 된다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730943284029/032adef3-546a-4a6a-88c1-3f2709bed252.png align="center")

* 입력 순서: 15, 28, 21, 41, 67, 54
    
* 예를 들어, **15**가 먼저 슬롯 2에 저장된다.
    
* 이후 **28**도 같은 해시 값을 가지기 때문에 2차 조사에 따라 다른 슬롯을 찾게 되고, 슬롯 3에 저장되었다.
    
* 이후 **54**와 같은 값들도 2차 조사를 통해 비슷한 순서로 탐색하여 특정 슬롯에 몰리게 되는 **2차 군집** 문제가 발생하고 있다.
    

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #3

: **더블 해싱**의 개요(Overview of Double Hashing)

**<mark>💡요약: </mark> 더블 해싱**(Double Hashing)은 **1차, 2차 군집 문제**를 피하기 위해 두 개의 해시 함수를 사용하여 충돌 시 보폭을 다르게 설정한다. 이를 통해 데이터를 해시 테이블에 **고르게 분포**시키는 효과가 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730943395530/9df3f52a-530a-423d-87b5-58cbf503fc8b.png align="center")

**더블 해싱**(Double Hashing)은 **1차 군집**(Primary Clustering)과 **2차 군집**(Secondary Clustering) 문제를 해결하기 위해 두 개의 해시 함수를 사용하는 충돌 해결 방법이다.

이 방식은 **보조 해시 함수**(secondary hash function)를 추가로 사용하여, 충돌이 발생할 때마다 첫 번째 해시 값에 두 번째 해시 값에 따라 일정 간격으로 이동하게 만든다.

더블 해싱에서 해시 함수는 위의 사진과 같이 구성된다. 여기서 h(x)는 첫 번째 해시 함수, f(x)는 보조 해시 함수이며, i는 충돌 횟수이다. 충돌이 발생할 때마다 f(x) 만큼의 간격으로 이동하여 새로운 슬롯을 찾는다. 이로 인해 **동일한 순서로 탐색하지 않으므로** 군집 현상을 줄이는 데 효과적이게 된다.

---

### **개방 주소 방법의 유형**(Types of Open Addressing) #2

: **이차원군집과 더블 해싱 비교** (Comparison between Quadratic Probing and Double Hashing)

**<mark>💡요약: </mark>** 아래 이미지는 더블 해싱을 사용하여 2차 군집 문제를 해결하는 방법을 보여주며, 데이터를 해시 테이블 내에서 고르게 분포시키는 장점을 강조하고 있다. 더블해싱은 각 충돌 시 두 개의 해시 함수를 사용하여 다른 간격으로 이동하며 데이터가 특정 슬롯에 몰리는 현상을 방지하고, 데이터를 보다 **균일하게 분포시킨다.**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730943559210/5ea24828-d8bd-4aae-a477-51bcd94f3824.png align="center")

* **2차 군집의 예**(왼쪽): 입력 순서 15, 28, 21, 41, 67, 54로 데이터를 해시 테이블에 저장
    
    * `h_(x) = (h(x) + i²) mod  13` 함수를 사용했을 때, 여러 데이터가 같은 초기 해시 값으로 인해 동일한 슬롯들로 몰리게 된다.
        
    * 예를 들어, **15**, **28**, **41**이 같은 초기 해시 값으로 시작하여 차례대로 충돌이 발생하면서 동일한 슬롯들을 탐색하게 된다. 이로 인해 **2차 군집** 문제가 발생한다.
        
* **더블 해싱 적용**(오른쪽): 동일한 입력 순서를 더블 해싱을 이용하여 해시 테이블에 저장
    
    * 해시 함수 선형 조사 `h(x) = x mod  13` 와 보조 해시 함수 `f(x) = 1 + (x mod  11)`을 사용하여, `h_i(x) = (h(x) + i ⋅ f(x)) mod  13` 로 충돌 시 이동 간격이 달라지게 한다.
        
    * 예를 들어, **15**는 슬롯 2에 저장되고, 이후 **28**이 충돌하면 f(x)에 의해 새로운 간격으로 다른 슬롯을 탐색하게 된다.
        
    * 이를 통해 각 값이 더 고르게 분포되며, 특정 슬롯에 몰리는 **군집 현상**이 줄어든다.
        

---

### **해시테이블에서 원소의 삭제 시 주의사항**

(Precautions When Deleting Elements in Hash Table)

**<mark>💡요약: </mark>** 해시 테이블에서 원소를 삭제할 때 **문제**(issue)가 발생할 수 있다. 특히, **개방 주소 방식**(Open Addressing)을 사용할 경우 삭제된 위치를 처리하지 않으면 검색에 문제가 생긴다. 삭제된 자리를 제대로 표시하지 않으면 이후 원소 탐색 시 해당 자리가 비어 있다고 판단하여 **탐색 실패**로 이어질 수 있기 때문이다. 따라서 삭제된 자리는 **"삭제됨"**(DELETED)과 같은 표시를 남겨주어야 한다.

아래 이미지는 해시 테이블에서 원소를 삭제할 때 주의해야 할 사항을 설명하며, 삭제된 자리를 표시하지 않으면 탐색 시 문제가 발생할 수 있음을 보여주고 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730945293803/9cced287-b0b2-4aea-81b4-7d48ebc3e0be.png align="center")

* **(a) 원소 삭제 후**: 원소 **1**이 삭제된 상태이다. 이 경우 **38**을 탐색할 때, 원래 **1**이 있던 자리에서 탐색을 멈출 수 있어 문제가 생긴다.
    
* **(b) 문제 발생**: 원소 **1**이 단순히 삭제되어 비어 있는 자리로 처리되면, **38**을 찾으려 할 때 중간에 비어 있는 자리 때문에 **38이 없는 것**으로 판단할 수 있다.
    
* **(c) "삭제됨" 표시 적용**: 삭제된 자리를 \*\*"DELETED"\*\*로 표시하면 **38**을 탐색할 때 중간의 삭제된 자리를 무시하고 탐색을 계속할 수 있어 문제가 발생하지 않는다.
    

---

### ❓해시 테이블에서 원소를 삭제해야 하는 경우❓

주로 **데이터의 동적 관리**가 필요한 상황에서 원소를 삭제한다. 예를들어…

* **만료된 데이터**: 캐시처럼 만료 시간이 있는 데이터는 시간이 지나면 삭제하는 경우
    
* **조건에 맞지 않는 데이터**: 점수나 빈도 등 특정 조건을 만족하지 않는 데이터를 삭제하는 경우
    
* **적재율 조정**: 테이블이 너무 꽉 찼을 때 필요 없는 데이터를 삭제하여 공간을 확보하는 경우
    

---

### **개방 주소 의사코드**(Pseudocode for Open Addressing)

**<mark>💡요약:</mark>** 개방 주소 방식에서 **hashInsert**는 빈 슬롯 또는 삭제된 자리를 찾을 때까지 해시 값을 계산하여 원소를 삽입하는 과정이고, **hashSearch**는 원하는 원소를 찾기 위해 해시 값을 계산하며 탐색하는 과정이다. 개방 주소 방식을 사용할 때 테이블이 꽉 찬 경우를 주의해야 하며, 삭제된 자리를 "DELETED"로 표시하면 검색 성능이 유지된다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730945681352/0181979a-30fa-40bf-a752-fcb57262f8b2.png align="center")

개방 주소 방식에서 해시 테이블 작업은 크게 두 가지로 나뉜다: **삽입**(Insert)과 **검색**(Search)이다. 이 의사코드는 해시 테이블에 원소를 삽입하고, 특정 원소를 찾기 위한 과정을 설명한다. 여기서 T는 **해시 테이블**(Hash Table)을, x는 삽입 또는 검색하려는 **원소**(element)를 나타내며, h\_i(x)는 해당 원소의 해시 값을 계산하는 **해시 함수**(Hash Function)이다.

1. **hashInsert(T\[\], x)**: 원소를 해시 테이블에 삽입하는 과정이다.
    

* 먼저 i를 0으로 설정하고, 빈 슬롯을 찾을 때까지 반복한다.
    
* 해시 값 j를 계산하여, 슬롯 T\[j\]가 비어 있거나 삭제된 자리인 경우, 그 자리에 원소 x를 삽입하고 인덱스 j를 반환한다.
    
* 만약 테이블이 모두 차있다면, **오버플로우**(overflow) 에러가 발생하게 된다.
    

2. **hashSearch(T\[\], x)**: 해시 테이블에서 원소를 찾는 과정이다.
    

* i를 0으로 설정하고, 원하는 원소를 찾을 때까지 반복한다.
    
* 해시 값 j를 계산하여, 해당 슬롯 T\[j\]에 원하는 원소 x가 있으면 그 인덱스 j를 반환한다.
    
* 만약 해당 슬롯에 원소가 없거나 테이블의 끝에 도달하면 검색을 종료하고 **NIL**을 반환한다.
    

---

### **해시 테이블의 검색 효율**(Efficiency of Hash Table Search)

**<mark>💡요약:</mark>** 해시 테이블의 **검색 효율**(search efficiency)은 **적재율**(Load Factor)인 α와 밀접한 관련이 있으며, 이는 해시 테이블이 얼마나 꽉 차 있는지를 나타낸다. 높은 적재율은 충돌을 증가시켜 검색 성능을 저하시킬 수 있다.

아래 설명은 적재율을 통해 해시 테이블의 검색 성능이 어떻게 영향을 받는지 설명한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730945967502/53a4745a-e73b-4deb-a6f9-e3b9ee6a9a01.png align="center")

* 적재율 α(알파)는 해시 테이블이 얼마나 꽉 찼는지를 의미하는 수치이다.
    
* 예를 들어, m개의 슬롯을 가진 해시 테이블에 n개의 원소가 저장되어 있다면, 적재율 α는 위의 식과 같이 계산된다. 여기서 n은 저장된 원소의 개수, m은 해시 테이블의 총 슬롯 수를 의미한다.
    
* 적재율이 높아지면 충돌이 발생할 가능성이 커져 검색 속도가 느려질 수 있다. 반대로, 적재율이 낮으면 해시 테이블의 공간이 비효율적으로 사용될 수 있다.
    

**💡예시**: 학생들의 시험 점수를 저장하는 해시 테이블을 만든다고 가정해보자. 이 해시 테이블은 학생의 이름을 키(key)로, 점수를 값(value)으로 저장한다. **적재율**이 높아질수록 검색 속도가 느려지는 것을 확인할 수 있다.

우선, 해시 테이블을 크기 10으로 설정하고 몇 개의 데이터를 넣어본다.

```python
# 해시 테이블 초기화 (크기 10)
hash_table = [None] * 10

# 간단한 해시 함수: 이름의 첫 글자의 아스키 값을 테이블 크기로 나눈 나머지
def hash_function(name):
    return ord(name[0]) % len(hash_table)

# 해시 테이블에 삽입 함수
def insert(name, score):
    index = hash_function(name)
    if hash_table[index] is None:
        hash_table[index] = [(name, score)]  # 빈 슬롯일 경우 추가
    else:
        hash_table[index].append((name, score))  # 체이닝으로 충돌 해결

# 해시 테이블에 검색 함수
def search(name):
    index = hash_function(name)
    if hash_table[index] is not None:
        for entry in hash_table[index]:
            if entry[0] == name:
                return entry[1]  # 해당 학생의 점수를 반환
    return None  # 찾지 못했을 경우 None 반환

# 데이터 삽입
insert("Alice", 85)
insert("Bob", 90)
insert("Charlie", 78)
insert("David", 92)
insert("Eve", 88)
insert("Frank", 80)
insert("Grace", 95)
insert("Heidi", 70)
```

#### 2\. 적재율에 따른 검색 효율 확인

현재 해시 테이블의 적재율은 8/10 = 0.8이다. 이 적재율이 너무 높아지면 충돌이 증가해 검색 속도가 느려질 수 있다.

예를 들어, **검색**을 할 때 체이닝으로 연결된 슬롯이 많아질 경우, 리스트의 모든 항목을 확인해야 하므로 검색 효율이 떨어진다.

```python
# 검색 예시
print(search("Alice"))  # 85
print(search("Frank"))  # 80
print(search("Heidi"))  # 70
print(search("Nonexistent"))  # None
```

#### 3\. 적재율을 줄여 검색 효율 개선하기

해시 테이블의 크기를 늘려 **적재율**을 줄이면 검색 효율이 개선될 수 있다. 예를 들어, 해시 테이블의 크기를 20으로 늘리면 적재율은 8/20 = 0.4로 낮아지게 된다. 이는 충돌을 줄여 검색 속도를 빠르게 할 수 있다.

```python
# 해시 테이블 크기 증가 및 데이터 재배치 (적재율 감소)
new_hash_table = [None] * 20

def rehash():
    global hash_table
    global new_hash_table
    old_table = hash_table
    hash_table = new_hash_table
    for bucket in old_table:
        if bucket is not None:
            for name, score in bucket:
                insert(name, score)

# 테이블 크기를 늘린 후 데이터 재배치
rehash()
```

이제 적재율이 낮아져 검색할 때 각 슬롯에 연결된 원소가 줄어들므로, 검색 효율이 향상된다.

* **적재율이 높을 때**: 해시 테이블의 슬롯에 충돌이 많아져 검색 속도가 느려질 수 있다.
    
* **적재율이 낮을 때**: 충돌이 적어져 검색 속도가 빨라진다.
    

---

## **3️⃣** 해시 테이블의 검색 시간

(Search time analysis in Hash Table)

### **체이닝에서의 검색 시간**(Search Time in Chaining)

**<mark>💡요약: </mark>** 체이닝에서의 검색 시간에 관한 수식을 통해, 적재율이 검색 성능에 어떻게 영향을 미치는지를 알아보자

체이닝을 사용하는 해시 테이블에서 **검색 시간**(search time)은 적재율 α에 의해 결정된다. **실패 시**에는 조사 횟수의 기대치가 α이다. 성공시에는 조사 횟수의 기대치는 아래와 같다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730947212402/5f60b39b-b70e-45d9-8d11-f6535678b87d.png align="center")

* **정리 1** (Case 1): **실패하는 검색**(Unsuccessful Search)의 경우
    
    * 체이닝을 사용하는 해시 테이블에서 적재율이 α일 때, **실패하는 검색**에서 조사 횟수의 기대치는 **α**이다. 이는 찾으려는 원소가 없을 때 평균적으로 조사해야 하는 슬롯의 개수를 의미한다.
        
* **정리 2** (Case 2): **성공하는 검색**(Successful Search)의 경우
    
    * 체이닝을 사용하는 해시 테이블에서 적재율이 α일 때, **성공하는 검색**에서 조사 횟수의 기대치는 **위의 캡쳐본과 같다**. 이는 찾으려는 원소가 있을 때 평균적으로 조사해야 하는 슬롯의 개수를 나타낸다.
        

---

### **개방 주소에서의 검색 시간**

(Search Time in Open Addressing)

**<mark>💡요약: </mark>** 개방 주소 방식을 사용할 때, **검색 시간**(search time)은 **적재율**(Load Factor, α\\alphaα)에 의해 영향을 받는다. 적재율이 높을수록 충돌이 증가하여 검색 시간이 길어진다. 이 경우, 성공적인 검색과 실패한 검색에 따른 기대 조사 횟수가 달라진다.

**정리 3** (Case 3): **실패하는 검색**(Unsuccessful Search)의 경우

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730947452325/022a10f0-eb0b-4268-91fe-f7cb522f6f4b.png align="center")

* 적재율이 1보자 작을때, 검색이 실패할 경우 최대 조사 횟수 기대값이다. 즉 찾으려는 원소가 해시 테이블에 없을 때 조사해야 하는 평균적인 슬롯 수를 나타내고 있다.
    

**정리 4** (Case 4): **성공하는 검색**(Successful Search)의 경우

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730947508074/6d8a6109-03e1-4d79-beeb-3356c264a3cb.png align="center")

* 적재율이 1보다 작을 때, **검색이 성공할 경우**의 최대 조사 횟수 기대값이다. 즉 이는 찾으려는 원소가 해시 테이블에 있을 때 평균적으로 조사해야 하는 슬롯 수를 의미한다.
    

---

### **적재율의 조정**(Adjusting Load Factor)

**<mark>💡요약: </mark>** 해시 테이블에서 **적재율**(Load Factor)이 높아지면 해시 테이블의 **효율**(efficiency)이 떨어진다는 점을 배웠다. 적재율이 높다는 것은 테이블이 꽉 차서 원소 간의 충돌이 많이 발생하고, 검색과 삽입 속도가 느려지는 것을 의미한다. 이를 방지하기 위해 **임계값**(threshold)을 설정해두고, 적재율이 이 값에 도달하면 테이블의 크기를 조정하여 성능을 유지하는 방법이 있다.

* **해시 테이블의 크기를 두 배로 늘림** (Double the size of the hash table):
    
    * 테이블이 꽉 차기 시작하면, 테이블의 크기를 두 배로 늘려 더 많은 원소를 수용할 수 있도록 한다.
        
* **해시 테이블에 저장된 모든 원소를 다시 해싱하여 저장** (Rehash all elements in the hash table):
    
    * 테이블 크기를 늘린 후, 기존에 저장된 모든 원소를 새 크기의 테이블에 맞게 **다시 해싱**(rehashing)하여 저장한다. 이렇게 하면 충돌이 줄어들고, 검색 성능이 개선된다.