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α)에 영향을 받는다. 적재율이 높으면 충돌이 증가하여 검색 시간이 길어질 수 있다.
1️⃣ 충돌 해결 방법 #1 - 체이닝 (Collusion resolution - Chaining)
해시 테이블의 충돌(Hash Table Collision)
💡요약: 해시 테이블 충돌(Hash Table Collision)이란 하나의 슬롯에 두 개 이상의 데이터가 저장되어 충돌이 발생하는 상황이다. 이를 해결하기 위한 여러 방법이 있으며, 충돌 관리 기법을 통해 해시 테이블의 효율성을 유지할 수 있다. 오늘 그 해결 방법에 대해 공부한다.
해시 테이블은 데이터를 효율적으로 저장하고 검색하는 자료 구조입니다. 그러나 충돌(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)
💡요약: 충돌을 해결하는 방법에는 체이닝(Chaining)과 개방주소(Open Addressing)가 있다. 체이닝은 충돌된 데이터를 연결 리스트로 저장하고, 개방주소는 테이블 내 빈 슬롯을 찾아 저장하는 방식이다.
☑️ 체이닝(Chaining): 같은 주소로 매핑된 데이터를 연결 리스트(linked list)로 연결하여 저장한다. 이 방법을 사용하면 한 슬롯에 여러 데이터를 연결하여 충돌 문제를 해결할 수 있다.
☑️ 개방주소(Open Addressing): 충돌이 발생하면 다른 빈 공간에 데이터를 할당하는 방식이다. 추가적인 연결 리스트(linked list)가 필요 없고, 테이블 내에서 빈 공간을 찾아 데이터를 재배치한다.
💡예시
체이닝: 해시 함수
h(x) = x mod 3을 사용하고 데이터 9, 12, 15를 삽입할 때 9과 12는 같은 슬롯에 저장된다. 이 경우, 체이닝을 사용하여 12를 9와 연결하여 저장한다.개방주소: 같은 상황에서 개방주소를 사용하면, 12가 들어갈 다른 빈 공간을 찾아 저장하게 된다.
충돌의 해결방법(Collision Resolution) #1
: 체이닝의 예(Example of Chaining)
💡요약: 체이닝을 사용하면 충돌이 발생했을 때 같은 슬롯에 여러 데이터를 연결 리스트(linked list)로 저장하여 문제를 해결할 수 있다. 새로운 값은 항상 리스트의 맨 앞에 삽입하여 접근 속도를 높인다.
체이닝은 충돌 해결 방법(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)
💡요약: 체이닝 방식의 해시 테이블에서는 삽입(Insert), 검색(Search), 삭제(Delete) 작업을 통해 데이터를 효율적으로 관리할 수 있다. 각 작업은 리스트를 이용하여 충돌이 발생하더라도 문제를 해결할 수 있도록 설계되었다.
체이닝을 사용한 해시 테이블에서 가장 중요한 세 가지 작업은 삽입(Insert), 검색(Search), 그리고 삭제(Delete)이다.
chainedHashInsert(T[], x): 이 함수는 원소
x를 해시 테이블T의 적절한 리스트에 삽입한다. 삽입할 때, 리스트의 맨 앞(front of the list)에 삽입하여 효율을 높인다.chainedHashSearch(T[], x): 해시 테이블
T의 적절한 리스트에서 값x를 찾는다. 충돌이 발생한 경우에도 리스트를 통해 원하는 값을 빠르게 찾을 수 있다.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)
💡요약: 개방 주소(Open Addressing)는 해시 테이블에서 빈 슬롯을 찾을 때까지 새로운 해시 값(hash value)을 반복 생성하여 데이터를 저장한다. 충돌이 발생해도 빈 공간이 있을 때까지 다른 슬롯을 찾아 데이터를 삽입한다. 이를 통해 충돌을 해결하고 데이터를 해시 테이블에 안전하게 저장할 수 있게 된다.
개방 주소 방법으로 슬롯을 찾는 과정은 다음과 같다.
입력값
x로 해시 함수를 적용하여 첫 번째 해시 값 h_0(x)을 생성한다.h_0(x)의 슬롯이 비어 있다면, 그곳에
x를 삽입하고 작업을 종료한다.h_0(x) 슬롯이 이미 차 있으면, 다음 해시 값 h_1(x)을 생성하여 다른 슬롯을 시도한다.
빈 슬롯이 나올 때까지 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)
💡요약: 개방 주소 방법(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)
💡요약: 아래 이미지는 선형 조사를 사용해 데이터를 충돌 없이 저장하는 과정을 시각적으로 설명하며, 각 입력값이 슬롯을 찾는 과정을 보여주고 있다.
선형 조사는 개방 주소 방식(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)
💡요약: 선형 조사(Linear Probing)는 간단하고 효율적일 수 있지만, 이 방식에는 1차 군집(Primary Clustering)이라는 문제가 있다. 1차 군집이란 특정 영역에 데이터가 몰려있는 현상으로, 이로 인해 추가적인 충돌이 발생하기 쉽고, 새로운 데이터를 삽입할 때 더 많은 이동이 필요해진다. 결과적으로 테이블의 성능을 저하시키는 것이다.
입력값 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)
💡요약: 1차 군집을 방지하여 충돌을 해결하는 더 나은 방법으로는 이차원 조사(Quadratic Probing)가 있다. 선형 조사보다 1차 군집(Primary Clustering) 문제에 강한 해시 테이블 충돌 해결 방식이다. 충돌이 발생할 때마다 2차 함수에 따라 이동 간격이 점점 커지므로, 데이터가 특정 구간에 몰리지 않고 더 균일하게 분포(spread out)될 수 있다.
여기서 h(x)는 기본 해시 함수, c_1과 c_2는 상수이며, i는 충돌 횟수이다. 충돌이 발생할 때마다 i 값을 증가시키며 2차 함수에 따라 다른 슬롯을 시도한다.
개방 주소 방법의 유형(Types of Open Addressing) #2
: 이차원 조사의 예(Example of Quadratic Probing)
💡요약: 충돌이 발생할 때마다 보폭을 i²로 설정하여 이동하는 방식으로, 보폭을 2차 함수(quadratic function)로 증가시키며 빈 슬롯을 찾는 방법이다. 1차 군집 문제를 줄이는 데 효과적이다. 충돌이 발생할 때마다 h_i(x) = (x+i²) mod 13과 같이 보폭이 i² 로 주어진다. 이로인해 탐색이 한 칸씩 이동하지 않고, 이동 거리가 점점 커지기 때문에 특정 영역에 데이터가 몰리는 것을 방지할 수 있다.
입력값: 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)
이차원 조사를 통해 데이터가 해시 테이블 내에서 보다 고르게 분포하는 과정을 소개한다.
입력 순서: 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)
💡요약: 이차원 조사(Quadratic Probing)는 충돌을 해결하기 위해 보폭을 2차 함수로 설정하지만, 2차 군집 문제로 인해 데이터가 특정 슬롯에 몰리는 현상이 발생할 수 있다. 2차 군집은 여러 개의 원소가 동일한 초기 해시 함수 값을 가질 때 발생하며, 이로 인해 같은 순서로 슬롯을 탐색하게 되는 현상을 뜻한다. 이로 인해 해시 테이블의 효율이 떨어지게 된다.
입력 순서: 15, 28, 21, 41, 67, 54
예를 들어, 15가 먼저 슬롯 2에 저장된다.
이후 28도 같은 해시 값을 가지기 때문에 2차 조사에 따라 다른 슬롯을 찾게 되고, 슬롯 3에 저장되었다.
이후 54와 같은 값들도 2차 조사를 통해 비슷한 순서로 탐색하여 특정 슬롯에 몰리게 되는 2차 군집 문제가 발생하고 있다.
개방 주소 방법의 유형(Types of Open Addressing) #3
: 더블 해싱의 개요(Overview of Double Hashing)
💡요약: 더블 해싱(Double Hashing)은 1차, 2차 군집 문제를 피하기 위해 두 개의 해시 함수를 사용하여 충돌 시 보폭을 다르게 설정한다. 이를 통해 데이터를 해시 테이블에 고르게 분포시키는 효과가 있다.
더블 해싱(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)
💡요약: 아래 이미지는 더블 해싱을 사용하여 2차 군집 문제를 해결하는 방법을 보여주며, 데이터를 해시 테이블 내에서 고르게 분포시키는 장점을 강조하고 있다. 더블해싱은 각 충돌 시 두 개의 해시 함수를 사용하여 다른 간격으로 이동하며 데이터가 특정 슬롯에 몰리는 현상을 방지하고, 데이터를 보다 균일하게 분포시킨다.
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)
💡요약: 해시 테이블에서 원소를 삭제할 때 문제(issue)가 발생할 수 있다. 특히, 개방 주소 방식(Open Addressing)을 사용할 경우 삭제된 위치를 처리하지 않으면 검색에 문제가 생긴다. 삭제된 자리를 제대로 표시하지 않으면 이후 원소 탐색 시 해당 자리가 비어 있다고 판단하여 탐색 실패로 이어질 수 있기 때문이다. 따라서 삭제된 자리는 "삭제됨"(DELETED)과 같은 표시를 남겨주어야 한다.
아래 이미지는 해시 테이블에서 원소를 삭제할 때 주의해야 할 사항을 설명하며, 삭제된 자리를 표시하지 않으면 탐색 시 문제가 발생할 수 있음을 보여주고 있다.
(a) 원소 삭제 후: 원소 1이 삭제된 상태이다. 이 경우 38을 탐색할 때, 원래 1이 있던 자리에서 탐색을 멈출 수 있어 문제가 생긴다.
(b) 문제 발생: 원소 1이 단순히 삭제되어 비어 있는 자리로 처리되면, 38을 찾으려 할 때 중간에 비어 있는 자리 때문에 38이 없는 것으로 판단할 수 있다.
(c) "삭제됨" 표시 적용: 삭제된 자리를 **"DELETED"**로 표시하면 38을 탐색할 때 중간의 삭제된 자리를 무시하고 탐색을 계속할 수 있어 문제가 발생하지 않는다.
❓해시 테이블에서 원소를 삭제해야 하는 경우❓
주로 데이터의 동적 관리가 필요한 상황에서 원소를 삭제한다. 예를들어…
만료된 데이터: 캐시처럼 만료 시간이 있는 데이터는 시간이 지나면 삭제하는 경우
조건에 맞지 않는 데이터: 점수나 빈도 등 특정 조건을 만족하지 않는 데이터를 삭제하는 경우
적재율 조정: 테이블이 너무 꽉 찼을 때 필요 없는 데이터를 삭제하여 공간을 확보하는 경우
개방 주소 의사코드(Pseudocode for Open Addressing)
💡요약: 개방 주소 방식에서 hashInsert는 빈 슬롯 또는 삭제된 자리를 찾을 때까지 해시 값을 계산하여 원소를 삽입하는 과정이고, hashSearch는 원하는 원소를 찾기 위해 해시 값을 계산하며 탐색하는 과정이다. 개방 주소 방식을 사용할 때 테이블이 꽉 찬 경우를 주의해야 하며, 삭제된 자리를 "DELETED"로 표시하면 검색 성능이 유지된다.
개방 주소 방식에서 해시 테이블 작업은 크게 두 가지로 나뉜다: 삽입(Insert)과 검색(Search)이다. 이 의사코드는 해시 테이블에 원소를 삽입하고, 특정 원소를 찾기 위한 과정을 설명한다. 여기서 T는 해시 테이블(Hash Table)을, x는 삽입 또는 검색하려는 원소(element)를 나타내며, h_i(x)는 해당 원소의 해시 값을 계산하는 해시 함수(Hash Function)이다.
- hashInsert(T[], x): 원소를 해시 테이블에 삽입하는 과정이다.
먼저 i를 0으로 설정하고, 빈 슬롯을 찾을 때까지 반복한다.
해시 값 j를 계산하여, 슬롯 T[j]가 비어 있거나 삭제된 자리인 경우, 그 자리에 원소 x를 삽입하고 인덱스 j를 반환한다.
만약 테이블이 모두 차있다면, 오버플로우(overflow) 에러가 발생하게 된다.
- hashSearch(T[], x): 해시 테이블에서 원소를 찾는 과정이다.
i를 0으로 설정하고, 원하는 원소를 찾을 때까지 반복한다.
해시 값 j를 계산하여, 해당 슬롯 T[j]에 원하는 원소 x가 있으면 그 인덱스 j를 반환한다.
만약 해당 슬롯에 원소가 없거나 테이블의 끝에 도달하면 검색을 종료하고 NIL을 반환한다.
해시 테이블의 검색 효율(Efficiency of Hash Table Search)
💡요약: 해시 테이블의 검색 효율(search efficiency)은 적재율(Load Factor)인 α와 밀접한 관련이 있으며, 이는 해시 테이블이 얼마나 꽉 차 있는지를 나타낸다. 높은 적재율은 충돌을 증가시켜 검색 성능을 저하시킬 수 있다.
아래 설명은 적재율을 통해 해시 테이블의 검색 성능이 어떻게 영향을 받는지 설명한다.
적재율 α(알파)는 해시 테이블이 얼마나 꽉 찼는지를 의미하는 수치이다.
예를 들어, m개의 슬롯을 가진 해시 테이블에 n개의 원소가 저장되어 있다면, 적재율 α는 위의 식과 같이 계산된다. 여기서 n은 저장된 원소의 개수, m은 해시 테이블의 총 슬롯 수를 의미한다.
적재율이 높아지면 충돌이 발생할 가능성이 커져 검색 속도가 느려질 수 있다. 반대로, 적재율이 낮으면 해시 테이블의 공간이 비효율적으로 사용될 수 있다.
💡예시: 학생들의 시험 점수를 저장하는 해시 테이블을 만든다고 가정해보자. 이 해시 테이블은 학생의 이름을 키(key)로, 점수를 값(value)으로 저장한다. 적재율이 높아질수록 검색 속도가 느려지는 것을 확인할 수 있다.
우선, 해시 테이블을 크기 10으로 설정하고 몇 개의 데이터를 넣어본다.
# 해시 테이블 초기화 (크기 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이다. 이 적재율이 너무 높아지면 충돌이 증가해 검색 속도가 느려질 수 있다.
예를 들어, 검색을 할 때 체이닝으로 연결된 슬롯이 많아질 경우, 리스트의 모든 항목을 확인해야 하므로 검색 효율이 떨어진다.
# 검색 예시
print(search("Alice")) # 85
print(search("Frank")) # 80
print(search("Heidi")) # 70
print(search("Nonexistent")) # None
3. 적재율을 줄여 검색 효율 개선하기
해시 테이블의 크기를 늘려 적재율을 줄이면 검색 효율이 개선될 수 있다. 예를 들어, 해시 테이블의 크기를 20으로 늘리면 적재율은 8/20 = 0.4로 낮아지게 된다. 이는 충돌을 줄여 검색 속도를 빠르게 할 수 있다.
# 해시 테이블 크기 증가 및 데이터 재배치 (적재율 감소)
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)
💡요약: 체이닝에서의 검색 시간에 관한 수식을 통해, 적재율이 검색 성능에 어떻게 영향을 미치는지를 알아보자
체이닝을 사용하는 해시 테이블에서 검색 시간(search time)은 적재율 α에 의해 결정된다. 실패 시에는 조사 횟수의 기대치가 α이다. 성공시에는 조사 횟수의 기대치는 아래와 같다.
정리 1 (Case 1): 실패하는 검색(Unsuccessful Search)의 경우
- 체이닝을 사용하는 해시 테이블에서 적재율이 α일 때, 실패하는 검색에서 조사 횟수의 기대치는 α이다. 이는 찾으려는 원소가 없을 때 평균적으로 조사해야 하는 슬롯의 개수를 의미한다.
정리 2 (Case 2): 성공하는 검색(Successful Search)의 경우
- 체이닝을 사용하는 해시 테이블에서 적재율이 α일 때, 성공하는 검색에서 조사 횟수의 기대치는 위의 캡쳐본과 같다. 이는 찾으려는 원소가 있을 때 평균적으로 조사해야 하는 슬롯의 개수를 나타낸다.
개방 주소에서의 검색 시간
(Search Time in Open Addressing)
💡요약: 개방 주소 방식을 사용할 때, 검색 시간(search time)은 적재율(Load Factor, α\alphaα)에 의해 영향을 받는다. 적재율이 높을수록 충돌이 증가하여 검색 시간이 길어진다. 이 경우, 성공적인 검색과 실패한 검색에 따른 기대 조사 횟수가 달라진다.
정리 3 (Case 3): 실패하는 검색(Unsuccessful Search)의 경우
- 적재율이 1보자 작을때, 검색이 실패할 경우 최대 조사 횟수 기대값이다. 즉 찾으려는 원소가 해시 테이블에 없을 때 조사해야 하는 평균적인 슬롯 수를 나타내고 있다.
정리 4 (Case 4): 성공하는 검색(Successful Search)의 경우
- 적재율이 1보다 작을 때, 검색이 성공할 경우의 최대 조사 횟수 기대값이다. 즉 이는 찾으려는 원소가 해시 테이블에 있을 때 평균적으로 조사해야 하는 슬롯 수를 의미한다.
적재율의 조정(Adjusting Load Factor)
💡요약: 해시 테이블에서 적재율(Load Factor)이 높아지면 해시 테이블의 효율(efficiency)이 떨어진다는 점을 배웠다. 적재율이 높다는 것은 테이블이 꽉 차서 원소 간의 충돌이 많이 발생하고, 검색과 삽입 속도가 느려지는 것을 의미한다. 이를 방지하기 위해 임계값(threshold)을 설정해두고, 적재율이 이 값에 도달하면 테이블의 크기를 조정하여 성능을 유지하는 방법이 있다.
해시 테이블의 크기를 두 배로 늘림 (Double the size of the hash table):
- 테이블이 꽉 차기 시작하면, 테이블의 크기를 두 배로 늘려 더 많은 원소를 수용할 수 있도록 한다.
해시 테이블에 저장된 모든 원소를 다시 해싱하여 저장 (Rehash all elements in the hash table):
- 테이블 크기를 늘린 후, 기존에 저장된 모든 원소를 새 크기의 테이블에 맞게 다시 해싱(rehashing)하여 저장한다. 이렇게 하면 충돌이 줄어들고, 검색 성능이 개선된다.
