Chaining 이외에도 해시테이블의 충돌을 해결하는 방식 중 Open Addressing이 있다.
Open Addressing의 개념은, 해시테이블에 동일한 해시함수 값을 가진 데이터들이 저장될 경우 다른 비어 있는 자리를 찾아 해당 데이터를 삽입한다는 것이다.
Open Addressing은 선형탐사(Linear probing), 제곱탐사(Quadratic probing), 그리고 이중해싱(Double hashing)가 있다.
1. 선형탐사 (Linear probing)
선형탐사는 데이터가 삽입될 자리에 이미 다른 데이터가 있다면, 한 칸씩 내려가며 빈 자리에 데이터를 저장한다.
76, 93, 40은 각각의 해시함수값이 6, 2, 5로 서로 겹치지 않아 해당 인덱스에 저장된다.
다음으로 삽입되는 47은 해시함수값이 5로, 이미 삽입된 40의 자리와 겹치게 된다. 따라서 한 칸씩 밑으로 내려가며 빈 칸을 탐색한 후, 빈 칸이 나올 경우 해당 위치에 데이터를 삽입한다. (6번 인덱스와 0번 인덱스는 연결되어 있다고 가정하기 때문에 5 - 6 - 0번 인덱스에 위치하게 된다)
또한, 마지막으로 삽입되는 55의 해시함수값은 6으로 역시 맨 처음 삽입된 76과 위치가 겹치기 때문에 47이 삽입될 때처럼 한 칸씩 밑으로 내려가며 빈 칸에 삽입되게 된다.
선형탐사 방식의 해시테이블의 연산은 다음과 같은 로직으로 진행된다.
1) 데이터 탐색 :
1. 주어진 데이터 key에 대한 해시함수값을 구하고 그 값에 맞는 인덱스에 접근한다.
2. 만약 인덱스에 저장된 값이 찾고자 하는 데이터와 일치하지 않을 시 다음 인덱스의 값과 비교한다. 이 과정을 알맞은 데이터를 찾거나 혹은 빈 인덱스를 만날 때까지 반복한다.
3. 빈 인덱스를 만나면, 찾고자 하는 데이터가 테이블에 존재하지 않는 것이므로 찾지 못했다는 표시(None) 혹은 해당 빈 인덱스를 리턴해준다.
2) 데이터 추가 or 수정
1. 입력된 key값을 통해 1)에서 정의된 데이터 탐색 작업을 한다.
2. 만약 주어진 key와 동일한 key값을 가진 데이터를 발견한다면 그 값의 value를 새로 입력된 value로 업데이트 한다.
3. 만약 데이터를 찾지 못했다면 빈 인덱스에 새로운 key - value를 추가한다.
3) 데이터 삭제
1. 입력된 key값을 통해 1)에서 정의된 데이터 탐색 작업을 한다.
2. 만약 주어진 key와 동일한 key값의 데이터를 발견하지 못한다면 찾지 못했다는 표시(None)를 해준다.
3. 만약 주어진 key와 동일한 데이터를 찾았다면, 해당 데이터를 삭제한다.
4. 데이터가 삭제된 인덱스부터 순차적으로 테이블을 돌면서, 삭제된 데이터의 존재로 인해 다른 위치에 저장된 다른 값들을 찾고, 해당 값들을 알맞은 위치로 당겨준다.
-> 데이터 삭제 연산에서는 4번 과정이 매우 중요하다. 이 과정을 제대로 수행하지 않을 경우 데이터 탐색과정이 불가능해지게 된다.
2. 제곱탐사 (Quadratic probing)
선형탐사를 통한 해시테이블의 데이터 관리는 자칫 데이터들이 특정 부위에 몰려 있게 되는 일명 클러스터를 형성할 가능성이 높다.
클러스터가 커질수록, 데이터를 탐색, 삭제, 추가하는 연산의 횟수가 증가할 수 밖에 없기 때문에, 클러스터가 형성되는 것을 잘 제어하는 것이 해시테이블을 관리하는 필수적 요소이다.
이에 따라서, 단순히 순차적으로 비어있는 곳에 충돌 데이터를 저장하는 것이 아닌 기존 위치의 제곱번째 위치에 데이터를 저장하는 제곱탐사 방식이 존재한다.
제곱탐사 방식은 선형탐사 방식에서보다 클러스터를 일으킬 가능성이 더 적어진다.
3. 이중해싱 (Double Hashing)
제곱탐사는 선형탐사에서 발생하는 군집화의 문제를 일정부분 해결하기 위해 고안되었지만, 데이터가 충돌시 다른 인덱스를 찾는 과정에서 점핑하는 과정 자체 단순히 제곱값으로 같기 때문에, 군집화의 문제에서 완전히 자유로울 수 없다.
따라서, 군집화 문제의 완전한 해결을 도모하고자 이중해싱 방식이 소개되었다.
이중해싱은 말 그대로 인덱스값을 구하는 해시함수를 두 개 사용하여, 구한 값들을 연산하여 인덱스를 구해준다는 것이다.
예를 들어, h1(key) = key % size , h2(key) = size - (key % size) 라는 두 개의 해시함수가 있다고 가정할 때,
첫 번째 해시함수 h1(key)을 통해 구한 인덱스에 이미 다른 데이터가 존재한다면,
첫 번째 함수값과 두 번째 함수값을 더한 값 h1(key) + h2(key)를 인덱스로 사용한다.
혹시나 또 해당 자리에 데이터가 존재한다면 h1(key) + h2(key)에 또 다시 h2(key)를 구하는 방식으로 이중해싱을 구현할 수 있다.
'그 외 공부 > 자료구조' 카테고리의 다른 글
| 스택 (Stack) 자료구조 (0) | 2021.01.15 |
|---|---|
| 큐 (Queue) 자료구조 (0) | 2021.01.15 |
| 해시테이블의 충돌해결 - Chaining 방식 with 파이썬(Python) (0) | 2021.01.12 |
| 해시테이블이란? (0) | 2021.01.12 |
| 더블리 링크드 리스트의 구현 및 연산, 링크드 리스트와의 차이점 - 파이썬 (Python) (0) | 2021.01.11 |
