[파이썬 알고리즘] Ch 6-4. 해싱(Hashing) (2) Linear Probing

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021

1. 선형 조사에 의한 오버플로 처리

해시 함수로 계산된 버킷에 빈 슬롯이 없으면 그 다음 버킷들을 순서적으로 조사하여 빈 슬롯이 있는지를 찾는다. 이때 비어있는 공간을 찾는 것을 **조사(probing)**라고 한다.

**선형 조사법(linear probing)**은 해시 테이블의 k번 째 위치인 ht[k]에서 충돌이 발생했다면, 다음 위치인 ht[k+1]부터 순서대로 버킷의 빈 슬롯이 있는지를 살피고(probing), 빈 공간이 있다면 저장하는 방법이다.

$e.g.$

키값이 45, 27, 88, 9, 71, 60, 46, 38, 24인 레코드
테이블의 크기 $M$ = 13
해시 함수 $h(k)$ = $k$ % $M$

2. 선형 조사법의 삽입 연산

45, 27, 88, 9 까지의 삽입은 문제가 없다. 해당 주소가 비어있기 때문이다.

그림 6.14 선형 조사법 삽입 연산
71의 삽입에서 충돌이 발생한다. 선형 조사법에 의해 다음의 비어있는 공간을 찾는다. 따라서, 7의 위치에 71을 저장한다.

그림 6.15 선형 조사법 삽입 연산 (충돌 발생1)
60의 삽입은 해당 주소가 비어 있으므로 문제가 없다.
46의 삽입에서 다시 충돌이 발생한다. 비어있는 공간을 찾아 이동하여 11의 위치에 46저장한다.

그림 6.16 선형 조사법 삽입 연산 (충돌 발생2)
38은 충돌 없이 12의 위치에 저장된다.
마지막 24는 충돌이 발생한다. 그런데 뒤쪽으로 남은 버킷이 없으므로 다시 처음으로 돌아가 검사를 진행한다. 따라서, 24는 0의 위치에 저장한다.

그림 6.17 선형 조사법 삽입 연산 (충돌 발생3)

군집화(Clustering)

바로 위 그림과 같이 한 번 충돌이 발생한 위치에서 연속적인 충돌이 집중되는 현상이다.

선형 조사법은 간단하지만 오버플로가 자주 발생하면 군집화 현상에 따라 탐색의 효율이 크게 저하될 수 있다!!

python

# 선형 조사법의 삽입 알고리즘
M = 13                  # 테이블의 크기
table = [None] * M      # 테이블 생성 (None으로 초기화)

def hash_fn(key):       # 해시 함수
    return key % M

def lp_insertion(key):  # 삽입 연산 함수
    id = hash_fn(key)
    cnt = M

    while cnt > 0 and (table[id] != None):  # 테이블의 빈 공간을 찾는 구문
        id = (id+1+M) % M   # 다음 위치로 이동
        cnt -= 1            # 검사할 남은 위치 수
    
    if cnt > 0:             # 비어있다면
        table[id] = key     # 해당 슬롯에 키를 저장
    
    return

3. 선형 조사법의 탐색 연산

**탐색(search)**은 삽입과 비슷한 과정을 가진다. 탐색키가 입력되면 해시주소를 계산하고, 해당 주소에 같은 키의 레코드가 있으면 탐색은 성공이다. 이 과정은 해당 키의 레코드를 찾거나, 레코드가 없는 버킷을 만나거나, 모든 버킷을 다 검사할 때 까지 진행된다.

46은 같은 키에 레코드가 존재하므로 탐색 성공이다.

그림 6.18 선형 조사법 탐색 연산 (탐색 성공)
39는 27다음에 버킷이 비었으므로 탐색이 실패로 끝난다.

그림 6.19 선형 조사법 탐색 연산 (탐색 실패)

python

# 선형 조사법 탐색 연산
def lp_search(key):
    id = hash_fn(key)
    cnt = M

    while cnt > 0:
        if table[id] == None:   # 현재 위치가 비어있다면
            return None         # 해당 키는 테이블에 존재하지 않으므로 탐색 종료

        if table[id] == key:    # 현재 위치의 키가 찾는 키와 같다면
            return table[id]    # 해당 키 위치의 값을 반환 (탐색 성공)
        
        id = (id+1+M) % M       # 해당 버킷이 비어있지 않은데 찾는 키도 아닌 경우 다음 위치로 이동
        cnt -= 1
    
    return None     # 테이블을 모두 탐색하였는데도 없다면 None 반환

4. 선형 조사법의 삭제 연산

선형 조사법에서 항목이 **삭제(delete)**되면 탐색이 불가능해질 수 있다.

$e.g.$
60을 먼저 삭제 했다고 가정하고, 이 상태에서 46을 탐색하려고 한다. 문제는 60이 있던 위치가 이제는 빈 버킷이 되었으므로 46까지 도달하지 못하고 탐색이 종료된다.

이를 해결하기 위해서는 빈 버킷을 두 가지 유형으로 나누어야 한다. 즉, **한 번도 사용하지 않은 버킷**과 삭제되어 현재 비어있는 버킷 두 가지 유형으로 나누어야 한다. 그리고 탐색 연산 코드는 한 번도 사용되지 않는 버킷을 만나야 종료 되도록 수정해야 한다.

5. 선형 조사법 최종 소스코드

python

# 해시 함수
def hash_fn(key):       
    return key % M


# 삽입 연산 함수 (삭제 연산을 위한 11행 수정)
def lp_insertion(key):  
    id = hash_fn(key)
    cnt = M

    while cnt > 0 and (table[id] != None and table[id] != -1):  # 테이블의 빈 공간을 찾는 구문
        id = (id+1+M) % M   # 다음 위치로 이동
        cnt -= 1            # 검사할 남은 위치 수
    
    if cnt > 0:             # 비어있다면
        table[id] = key     # 해당 슬롯에 키를 저장
    
    return


# 탐색 연산 함수 (삭제 연산을 위한 30행 수정)
def lp_search(key):
    id = hash_fn(key)
    cnt = M

    while cnt > 0:
        if table[id] == None:   # 현재 위치가 비어있다면
            return None         # 해당 키는 테이블에 존재하지 않으므로 탐색 종료

        if table[id] != -1 and table[id] == key:    # 현재 위치의 키가 찾는 키와 같다면
            return table[id]    # 해당 키 위치의 값을 반환 (탐색 성공)
        
        id = (id+1+M) % M       # 해당 버킷이 비어있지 않은데 찾는 키도 아닌 경우 다음 위치로 이동
        cnt -= 1
    
    return None     # 테이블을 모두 탐색하였는데도 없다면 None 반환


# 삭제 연산 함수
def lp_delete(key):
    id = hash_fn(key)
    cnt = M

    while cnt > 0:
        if table[id] == None:   # 현재 위치가 빈 버킷이라면
            return              # 해당 키는 테이블에 존재하지 않으므로 삭제할 항목이 없음
        
        if table[id] != -1 and table[id] == key:    # 현재 위치가 삭제된 슬롯(-1)이 아니고, 찾는 키와 일치하는 경우
            table[id] = -1                          # 슬롯을 비우지 않고 -1을 대입하여 삭제된 슬롯임을 표시
            return
        
        id = (id+1+M) % M
        cnt -= 1
    
    return None


# 선형 조사법 테스트
M = 13                  # 테이블의 크기
table = [None] * M      # 테이블 생성 (None으로 초기화)

print("   최초:", table)
lp_insertion(45); print("45 삽입:", table)
lp_insertion(27); print("27 삽입:", table)
lp_insertion(88); print("88 삽입:", table)
lp_insertion(9); print(" 9 삽입:", table)
lp_insertion(71); print("71 삽입:", table)
lp_insertion(60); print("60 삽입:", table)
lp_insertion(46); print("46 삽입:", table)
lp_insertion(38); print("38 삽입:", table)
lp_insertion(24); print("24 삽입:", table)
lp_delete(60); print("60 삭제:", table)
print("46 탐색:", lp_search(46))

python

# 출력 결과
   최초: [None, None, None, None, None, None, None, None, None, None, None, None, None]
45 삽입: [None, None, None, None, None, None, 45, None, None, None, None, None, None]
27 삽입: [None, 27, None, None, None, None, 45, None, None, None, None, None, None]
88 삽입: [None, 27, None, None, None, None, 45, None, None, None, 88, None, None]
 9 삽입: [None, 27, None, None, None, None, 45, None, None, 9, 88, None, None]
71 삽입: [None, 27, None, None, None, None, 45, 71, None, 9, 88, None, None]
60 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, None, None]
46 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, None]
38 삽입: [None, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, 38]
24 삽입: [24, 27, None, None, None, None, 45, 71, 60, 9, 88, 46, 38]
60 삭제: [24, 27, None, None, None, None, 45, 71, -1, 9, 88, 46, 38]
46 탐색: 46