해시 테이블 Hash Table (2) [ 충돌 회피 방법 및 성능평가 ]

• 삽입 하려는 곳에 이미 키값이 지정이 되어있다면 여기에서 충돌이 발생한다.
• perfect hash function 이 아닌 이상 해시테이블에 계속 삽입 하다 보면 충돌이 발생한다. 충돌이 일어났을때 대처하는 방법을 알아보자. Perfect hash function 에 대해 조금이나마 궁금하다면 해시 테이블 Hash Table (1) 편을 참고

---

 

Linear Probing

• open addressing 의 한가지 방법으로 충돌이 일어났으면 다른 비어있는 슬롯에 저장하는 것이다.
• 한칸씩 밑으로 내려가면서 빈칸을 찾는것
• 처음으로 빈칸이 나타나는 slot 에 키값을 저장

 

★ 예시  ★

길이가 10인 해시테이블이 있고 해시테이블의 길이를 key 로 나눈 나머지가 해시함수라고 하자.
key가 A5, A2, A3, B5, A9 있다고 가정하자.
A5는 5번째 slot, A2는 2번째 slot, A3는 3번째 slot 에 저장될것이다.

이제 B5를 해시함수에 넣어보면 해시함수의 결과값은 5가 된다.

하지만 이미 5번째 slot 에는 A5가 저장되어있으므로 충돌이 일어나게 된다.

Linear Probing 을 적용해서 5에서 한칸 내려와 6번째 slot 을 확인한다.

6번째 slot 에는 아직 저장된게 없으므로 B5는 6번째 slot 에 저장되게 된다.

그리고 마지막으로 A9는 9번째 slot 에 저장이 된다.

최종적으로 해시테이블에 저장된 값을 확인해보면 다음과 같다.

Idx	Slot
0
1	A2
2	A3
3
4	A5
5	B5
6
7
8	A9
9

위 해시테이블을 보면 A5와 B5와 같이 키값들이 연속된 슬롯에 모여있는 경우가 있다.
이것을 클러스터라고 한다.
물론 클러스트는 적을수록 효율적이 될것이다.
클러스터가 클수록 그만큼 충돌이 많이 일어날거기 때문이다.

 

자 이제 해시테이블에 저장되어있는 key 를 찾고, key 를 저장하고, 저장되어있는 key를 삭제하는 3가지의 연산을 알아보자

3개의 연산 ( set, remove, search ) 을 위해 필요한 함수인 find-slot 에 대해서 먼저 알아보겠다.
여기에서 작성되는 코드는 pseudo 코드이다.

• find slot

# 찾고자 하는 키값의 slot 이 비어있으면 해당 slot 번호를 리턴 
# 또는 키값의 slot 이 차있는데 내가 찾는 키값과 동일하다면 slot 번호 리턴
def find_slot ( key ): // key 값이 있으면 slot 번호 리턴, key 값이 없다면 key 값이 삽입될 slot 번호 리턴

    i = hash_func(key)

    start = i

    while ( hashTable[i] is occupied and hashTable[i].key !== key )
        # 슬롯이 차있고 내가 찾는 키값과 다르다면
        i = (i+1) % hashTableLength # 길이의 index 를 넘어가면 다시 0부터 시작
        if i == start: # 한바퀴를 다 돌았다면 다른 값으로 다 차있는 것이다.
            return 'Full'

    # while 문에서 full 을 리턴을 안했다는 것은 슬롯이 차있지 않았거나 차있었는데 내가 찾는 키값이었을 경우
    # slot 번호 return
    return i

• set

def set(key, value = None):
    i = find_slot(key)
    if i == 'FULL': # 만약 full 이면 더이상 저장할곳이 없는 것이다. 
        return None
    if HashTable[i] is ocuupied: # 만약 키의 hash table slot이 차있다면
        HashTable[i].value = value # 새로운 value 로 바꿔준다.
    else: # hash table slot이 차있지 않다면
        HashTable[i].key, HashTable[i].value = key, value # 새로운 value 를 넣어준다.

    return key # key 값이 return 되면 성공적으로 set 을 했다는 의미

• search

def search(key):
    i = find-slot(key)
    
    if i == 'FULL':
    	return False
    if HashTable[i] is occupied: # 찾는 키의 slot 이 차있다면 search 할수 있다.
        return True
    else:
    	return False # 비어있으면 search 할수 없다.

• remove

remove pseudo 코드를 작성하기 전에 고려해야할 사항에 대해 먼저 예시를 통해 알아보자

다음과 같이 Hash Table 이 있다고 가정해보자

Idx	Slot
0	B9
1
2	A2
3	A3
4	B2
5	A5
6	B5
7	C2
8
9	A9

여기에서 A3를 지운다고 해보자.

A3가 들어있는 slot 을 찾아서 지우면 다음과 같다.

Idx	Slot
0	B9
1
2	A2
3
4	B2
5	A5
6	B5
7	C2
8
9	A9

다음으로 B2 를 찾아보자.

처음으로 hash_func(B2) 를 하면 2가 나온다. 현재 2번째 slot 에는 A2 가 들어있다.

한칸을 내려와서 확인을 했더니 3번재 슬롯이 비어있다. search 는 끝나고 B2는 없다는 결론이 나온다.

하지만 실제 해시테이블에는 4번째 슬롯에 B2는 들어있다. 탐색의 고리가 끊어지게 된것이다.

그래서 remove 를 하고 빈칸이 되었을때 비워진 슬롯에 키값이 들어올수 있는지 확인을 해서 있다면 해당 빈칸에 채워줘야 한다.

A3를 remove 하고 B2를 A3 가 있었던 3번째 슬롯으로 옮겨줬어야 한다.

밑의 해시테이블과 같이 말이다.

Idx	Slot
0	B9
1
2	A2
3	B2
4
5	A5
6	B5
7	C2
8
9	A9

B2를 옮기면서 4번째 슬롯이 또 비게 된다. 

그러면 A5를 4번째 슬롯으로 옮겨야 할까? 아니다!

A5는 정상적으로 5번째 슬롯으로 들어간것이다. 왜냐하면 hash_func(A5) 가 5이기 때문이다.

그러면 6번째 슬롯의 B5를 4번째 슬롯으로 옮겨야 할까? 예상했겠지만 아니다!!

B5는 A5에 의해서 한칸 내려간것이기 때문이다.

그렇다면 7번째 슬롯의 C2는 어떤가? 바로 C2를 4번째 슬롯으로 옮겨야 한다.

이유는 다들 이제 알겠지만 C2가 바로 B2에 의해서 밀리고 계속 밀려서 7번째 슬롯으로 온것이기 때문이다.

Idx	Key
0	B9
1
2	A2
3	B2
4	C2
5	A5
6	B5
7
8
9	A9

그렇다면 도대체 언데 비워진 슬롯으로 옮겨야 할까?

3가지 경우의 수가 있다.

방법을 설명하기 전에 세가지의 slot index 를 정의해보겠다.

• i : 삭제가 되어서 빈칸이 된 slot index
• j : i 로 옮길 예정인 slot index
• k : HashFunc(HashTable[j].key)   →  실제 j 에 있는 key 가 있어야 할 위치가 k

Idx	1경우 ( k < i < j )	2경우 ( i < j < k )	3경우 ( j < k < i )
0		★	★
1	k	i	j
2	★	★
3	i	j	k
4	j		★
5		k	i

1 경우 : j 는 원래 k 에 있어야 하는데 기존의  i 에 밀려서 j 에 있는 경우

2 경우 : j 는 원래 k 에 있어야 하는데 k는 마지막 슬롯에 있어서 다시 0번째 부터 내려오게 되고  i 에 밀려서 j 로 온경우

3 경우 : j 는 원래 k 에 있어야 하는데 i 에 마지막 슬롯 i 에 밀려서 j 로 온경우

이 3 가지 경우르 모두 고려해 remove pseudo 코드를 구현하면 다음과 같다.

def remove(key):
    i = find-slot(key)
    # 비어있으면 아무것도 안하면 된다.
    if HashTable[i] is unoccupied: 
    	return None 
    # i 를 지우면 빈곳을 매꿔줄 j 를 찾아야 한다.
    # HashTable[i] : 빈 슬롯, HashTable[j] : i로 옮겨야할 slot
    j = i 
    while True:
    	# H[i] 를 비워준다.
    	HashTable[i] = None 
        # HashTable[i] 로 이사할 HashTable[j] 를 찾는것
        while True: 
        	j = (j+1) % m
            # 밑으로 내려가는데 비어있는 슬롯을 만나면
            if HashTable[j] is unoccupied: 
            	# 지우고 채우는 것을 마쳤다는 것으로 key return
            	return key 
            # j slot에 있는 key의 실제 해시 함수의 output 을 k
            k = HashFunc(HashTable[j].key)
            # circular 로 연결되어있어서 3가지 경우를 모두 체크
            # 체크해서 옮겨야 한다면 해당 while break
            if (k < i <= j or i < j < k or j < k < i): 
            	break
        # j slot 에 있는 key 를 i slot 으로 옮겨준다.
        HashTable[i] = HashTable[j]
        # j 를 i 에 할당하면서 다시 while 문을 돈다
        i = j

 

---

Quadratic Probing / Double Probing

Linear probing 은 한칸씩 내려가는 것인데 Quadratic Proing 과 Double Probing 은 몇칸씩 내려간다.

 

먼저 Quadratic Probing 부터 간단히 알아보겠다.

k, k+1 (k + 1의 제곱), k+4 (k + 2의 제곱), k+9 (k + 3의 제곱), .. 으로 칸을 내려가는 것이다.

클러스터의 사이즈가 늦게 증가하지만 제곱으로 증가하기때문에 remove 구현이 복잡해 질수 있다.

 

Dobule Probing 은 해시함수를 두개 쓰는 것이다.

f(key), g(key) 두개의 해시함수가 있다고 가정하자.

만약 f(key) 가 차있다면 f(key) + g(key) 를 구한다. 여기에도 차있다면 f(key) + 2g(key) → f(key) + 3g(key)

이런식으로 f(key) + kg(key) 를 빈칸을 찾을때까지 한다.

Double Probing 은 해시함수를 2개 준비해야 한다는 것이 있지만 큰 무리 없이 돌아간다고 한다.

 

---

Chaining

기존에 우리가 봐았던 Linear Probing, Quadratic Probing, Double Probing 은 Open Addressing 방법이다.

Open Addressing 은 하나의 슬롯에는 하나의 key 만 저장할수 있어서 충돌이 일어나게 된다.

충돌이 발생하면 한칸씩 내려가며 빈 슬롯을 찾아서 저장한다.

하지만 체이닝은 본질적으로 하나의 슬롯에 여러개의 아이템을 저장할수 있다.

체이닝은 각 슬롯에 한방향 연결리스트를 만든다.

Idx	1	2	3	4	5	6
0	D0	B0
1	A1	B1	C1
2	B2	C2	D2	E2	F2	G2
3	A3	C3	B2

set 같은 경우는 hash 값 구하고 push front 로 저장하는 방식이어서 상수시간 O(1) 이 걸린다.

search 와 remove 는 최악의 경우에는 단방향 리스트의 노드갯수 ( 연결리스트의 길이 ) 가 될것이다.

 

---

성능 평가

 

성능은 클러스터의 길이(사이즈)에 비례한다. 

클러스터의 사이즈는 hash function 과 collision resolution, load factor 에 영향을 받는다.

여기에서 load factor 는  n / m ( n : Hash table 에 저장된 item 갯수, m : 총 slot 갯수 )

load factor 가 0에 가까울수록 충돌이 덜 발생하게 될것이다. 결국 load factor 에 비례해서 수행시간이 들게 된다.

 

Open addressing 의 경우 만약 항상 빈 슬롯이 전체 슬롯의 50 프로 정도만 유지한다면 set, remove, search 가 평균적으로 O(1) 이 될수 있다. 실제로 연산 속도가 중요하다면 해시테이블을 많이 사용한다고 한다.

 

Reference

한국외대, 컴퓨터전자시스템공학부, 자료구조 2020-1 유투브 강의를 보며 정리한것입니다.

https://www.youtube.com/watch?v=ghjWopXXUeA&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=19