Python - 검색 알고리즘(부제: 검색 알고리즘이 무엇인지 살펴보고, 선형 검색, 이진 검색, 해시법을 알아보자)

검색 알고리즘이란?

데이터 집합에서 원하는 값을 가진 원소를 찾아내는 검색 알고리즘

 

데이터 집합에서 원하는 값을 가진 원소를 찾아내는 검색 알고리즘을 살펴보도록하자. 

검색과 키

주소록을 검색한다고 가정하고 검색 조건을 다음과 같이 다양하게 설정할 수 있다.

• 국적이 한국인 사람을 찾는다
• 나이가 21세 이상 27살 미만인 사람을 찾는다
• 이름에 '민'자가 들어간 사람을 찾는다.
  
  

이 검색 조건은 모두 어떠한 항목에 주목하고 있다. 이렇게 주목하는 항목을 키key라고 하고 국적으로 검색하는 경우 국적이 키고 나이로 검색하는 경우 나이가 키인 것이다. 대부분 키는 데이터의 일부이다. 데이터가 간단한 정숫값이나 문자열이면 데이터값이 그대로 키값이 될 수도 있다. 다시 말해서 위의 주소록 검색 조건을 수행하려면 다음과 같은 키를 지정해야 한다.

• 국적 : 키값과 일치하도록 지정한다.
• 나이 : 키값의 구간을 지정한다.
• 문자 : 키값에 가깝도록 지정한다. 
  
  

검색에서는 이러한 조건을 하나만 지정할 수도 있고 논리곱, 논리합을 사용해 복합해서 지정할 수도 있다. 

 

검색의 종류

알고리즘에서는 다양한 검색 방법이 있지만 먼저 3가지 종류를 알아보도록 하자.

• 배열 검색
• 연결 리스트 검색
• 이진 검색 트리 검색

<검색은 어떤 조건을 만족하는 데이터를 찾아내는 것이다.> 

 

배열 검색의 알고리즘을 알아보도록 하자.

• 선형 검색: 무작위로 늘어놓은 데이터 집합에서 검색을 수행합니다.
• 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행합니다.
• 해시법: 추가. 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행합니다.  

선형 검색

배열에서 검색하는 방법 중 가장 기본적인 알고리즘은 선형 검색이다. 

선형 검색(linear search)이란 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다.

 

 

<2를 검색(검색 성공)>

a 

6

4

3

2

1

2

8

b

6

4

3

2

1

2

8

c

6

4

3

2

1

2

8

d

6

4

3

2

1

2

8

 

검색 성공!

- 검색할 값과 같은 원소 발견!

---

<5를 검색(검색 실패)>

 

a

6

4

3

2

1

2

8

b

6

4

3

2

1

2

8

c

6

4

3

2

1

2

8

d

6

4

3

2

1

2

8

e

6

4

3

2

1

2

8

f

6

4

3

2

1

2

8

g

6

4

3

2

1

2

8

h

6

4

3

2

1

2

8

배열의 맨 끝 원소를 지났음에도 찾는 값이 없을 경우엔 검색 실패!

선형 검색의 종료 조건
1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 ---- 검색 실패
2. 검색할 값과 같은 원소를 찾는 경우 ---- 검색 성공

배열 원소의 개수가 n이라면 이 조건을 판단하는 횟수는 평균 n/2번 입니다. 

(배열에 원하는 값이 존재하지 않는 경우 1과 2는 각각 n+1번, n번 수행이 된다.) 

#while문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key:Any) -> int:
    i = 0

    while True:
        if i == len(a):
            return -1   
            #검색 실패하면 -1을 반환
        
        if a[i] == key:
            return i
        #검색 성공하면 현재 검사한 배열의 인덱스를 반환
        i += 1

        
if __name__ =='__main__':
    num  = int(input('원소 수를 입력하세요.: '))
    x = [None] *num #입력받은 값만큼 빈리스트 생성

    for i in range(num): #입력받은 num값만큼 반복해서 x[i]값을 입력받아 넣어주기 리스트 채워넣는 개념
        x[i] = int(input(f"x{[i]}: "))

    ky = int(input("검색할 값을 입력하세요.: ")) #검색할 키값을 입력받음

    idx = seq_search(x,ky)

    if idx == -1:
        print("검색값을 갖는 원소가 존재하지 않습니다.")
    else:
        print(f"검색값은 x[{idx}]에 있습니다.")

👽 해설 👽

def seq_search(a: Sequence, key:Any) -> int:

- 배열  a에서 값이 key인 원소를 선형검색하는 함수 찾은 원소의 인덱스를 반환해준다.

- 여러 개 key 값이 발견 할 땐 맨 처음 발견한 우너소를 반환한다. 

- 위에서 구현한 seq_search 함수는 임의의 자료형 시퀀스에서 검색할 수도 있다. 시퀀스형에는 리스트형, 바이트 배열형, 문자열형, 튜플형, 바이트열형이 있다.

while True: , if~else: 

- 인덱스 값이 -1인 경우엔 입력받은 num값을 다 돌고도 원하는 키값을 찾지 못함을 의미한다. 그렇기에 idx == -1 값일 경우엔 검색값을 갖는 원소가 존재하지 않는다고 출력하고 인덱스 값이 x에 담긴 값과 찾는 값이 일치할 땐 else문을 실행시킨다.  

 

---

배열의 스캔을 for문으로 구성할 땐 코드가 더 짧고 간결해진다. (while -> for문 수정 ver.)

# for문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key:Any) -> int:
    for i in range(len(a)):
        if a[i] ==key:
            return i
        return -1

        
if __name__ =='__main__':
    num  = int(input('원소 수를 입력하세요.: '))
    x = [None] *num #입력받은 값만큼 빈리스트 생성

    for i in range(num): #입력받은 num값만큼 반복해서 x[i]값을 입력받아 넣어주기 리스트 채워넣는 개념
        x[i] = int(input(f"x{[i]}: "))

    ky = int(input("검색할 값을 입력하세요.: ")) #검색할 키값을 입력받음

    idx = seq_search(x,ky)

    if idx == -1:
        print("검색값을 갖는 원소가 존재하지 않습니다.")
    else:
        print(f"검색값은 x[{idx}]에 있습니다.")

---

다양한 자료형인 시퀀스에서 검색

# 3-1 seq_search()함수를 사용하여 실수 검색하기

from ssearch_while import 3-1

print("실수를 검색합니다.")
print("주의: "End"를 입력하면 종료합니다.")

        
num = 0
x = []

while True:
    s = input(f'x{[num]}: ') #리스트에 넣을 리스트 값
    if s == 'End':
        break
    elif s == 'end':
        break
    elif s == 'END':
        break
    x.append(float(s))
    num +=1


ky = float(input('검색할 값을 입력하세요.: '))


idx = seq_search(x,ky)
if idx == -1:
    print("검색값을 갖는 원소가 존재하지 않습니다.")

else:
    print(f"검색값은 x[{idx}]에 있습니다.")

# 3-1 seq_search()함수를 사용하여 특정 인덱스 검색하기

from ssearch_while import 3-1

t = (4,7,5.6,2,3.14,1)
s = 'string'
a = ['DTS','AAC','FLAC']


print(f"{t}에서 5.6의 인덱스는 {seq_search(t,"5.6")}입니다.")
print(f"{s}에서 "n"의 인덱스는 {seq_search(s,"n")}입니다.")
print(f"{a}에서 "DTS"의 인덱스는 {seq_search(a,"DTS")}입니다.")

 

보초법

선형 검색은 2가지 종료 조건을 체크한다. 단순한 판단이지만 이 과정을 계속 반복하면 종료 조건을 검사하는 비용(cost)를 무시할 수 없다. 이 비용을 반으로 줄이는 방법은 보초법(sentinel method)이다.

 

6

4

3

2

1

2

8

2

<-----------------------------------------------원래 데이터--------------------------------------------------->    👆보초

검색할 값을 배열의 맨 끝에 추가

 

표1. 2를 검색(검색 성공)

6

4

3

2

1

2

8

2

 

표2. 5를 검색(검색 실패)

6

4

3

2

1

2

8

5

-------------------------------------------------------------------------------->검색할 값과 같은 원소(보초)를 발견했습니다.

a[0]~a[6]은 원래 데이터이다. 검색하고자 하는 키값을 a[7]에 저장하고 이를 보초(sentinel)라고 한다.

• 표1. 2를 검색하려고 준비,  a[7]에 보초 2를 추가한다.
• 표2. 5를 검색하려고 준비,  a[7]에 보초 5를 추가한다.
  
  

표2처럼 찾는 값이 원래 데이터에 존재하지 않아도 a[7]의 보초까지 스캔하는 단계에서 선형 검색의 종료 조건(검색할 값과 같은 원소를 찾았습니까?)가 성립한다. 따라서 선형 검색의 종료 조건(검색할 값을 찾지 못하고 배열의 맨 끝을 지나갔습니까?)은 판단할 필요가 없다. 이처럼 보초는 반복을 종료하는 판단 횟수를 줄여주는 역할을 한다. 

 

보초 = 반복을 종료하는 판단 횟수를 줄여주는 역할을 한다.

#선형 검색 알고리즘(3-1)을 보초법으로 수정

from typing import Any, Sequence
import copy

def seq_search(seq: Sequence,key:Any) -> int:
    a = copy.deepcopy(seq) #seq 복사 -> 깊은 복사
    a.append(key) #보초 key추가

    i = 0
    while True:
        if a[i] == key:
            break #검색에 성공하면 while문 종료
        i += 1 

    return -1 if i == len(seq) else i

if __name__=='__main__':
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))


    ky = int(input("검색할 값을 입력하세요.: "))

    idx = seq_search(x,ky)

    if idx == -1:
        print("검색값을 갖는 원소가 존재하지 않습니다.")

    else:
        print(f"검색 값은 x[{idx}]에 있습니다.")

원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 2
x[4]: 1
x[5]: 2
x[6]: 8
검색할 값을 입력하세요.: 2
검색 값은 x[3]에 있습니다.
>>> 
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 2
x[4]: 1
x[5]: 2
x[6]: 8
검색할 값을 입력하세요.: 5
검색값을 갖는 원소가 존재하지 않습니다.

16행 : while 문에 의한 반복이 종료되면 찾은 원소가 배열의 원래 데이터인지 보초인지를 판단해야 한다.  i값이 len(seq)과 같다면 찾은 것이 보초이므로 검색에 실패한 것을 나타내는 -1을 반환해야하고 그렇지 않으면 i를 반환해야 한다. 

---

이진 검색

이진 검색(binary search)을 알아보도록 하자. 이진 검색 알고리즘을 사용하려면 배열의 데이터가 정렬(sort)되어 있어야 한다. 이진 검색은 선형 검색보다 빠르게 검색할 수 있다는 장점이 있다.

 

이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.

 

오름차순으로 정렬된 배열에서 39를 검색하는 과정을 생각해보자. 이진 검색에서는 먼저 배열의 중앙에 위치한 원소인 a[5]인 31에 주목한다.

 

5

7

15

28

29

31

39

58

68

70

95

찾아야 할 값인 39는 중앙 원소인 31보다 뒤쪽에 존재한다. 그렇다면 검색 대상을 a[6] ~ a[10]으로 좁힐 수 있다. 

 

 

이어서 업데이트 된 대상의 범위의 중앙 원소인 a[8], 즉 68에 주목해보자 

5

7

15

28

29

31

39

58

68

70

95

찾아야 할 값인 39는 중앙 원소인 68보다 앞쪽에 존재하기 때문에 검색 대상을 a[6]~a[7]로 좁힐 수 있다. 이제 검색해야 하는 대상은 2개로 다시 중앙 원소로 앞쪽의 39에 주목하도록 하자.

5

7

15

28

29

31

39

58

68

70

95

39는 찾아야 할 키의 값과 일치하므로 검색하는 데 성공했다. 

---

<이진 검색의 알고리즘 과정>

 

                                                                           pl                    pc - 주목할 원소(중앙원소)            pr  

<----------------검색 범위에서 제외-------------------><---------------------------검색 범위----------------------------->

 

n개의 원소가 오름차순으로 정열된 배열 a에서 이진 검색을 하는 과정의 알고리즘을 살펴보자

pl = 0

pc 주목할 원소(중앙원소)  = (n - 1) //2

pr = n-1

 

---

   pl                                                                                                                                           pr 

5

7

15

28

29

31

39

58

68

70

95

 

---

                                                                                 pl                           pc                          pr 

5

7

15

28

29

31

39

58

68

70

95

검색 범위를 중앙에서 오른쪽으로 좁힌다. 

---

                                                                                      pl            pr 

5

7

15

28

29

31

39

58

68

70

95

검색 범위를 중앙에서 왼쪽으로 좁힌다.                                 

---

이진 검색에서 검색 범위를 좁히는 과정을 정리하면 다음과 같다. 

• a[pc] < key : 중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝 pl로 지정하고, 검색 범위를 뒤쪽 절반으로 좁힙니다.
• a[pc] > key : 중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝 pr로 지정하고, 검색범위를 앞쪽 절반으로 좁힙니다. 

 

 

따라서 <이진 검색 알고리즘의 종료 조건>은 다음 조건 중 하나만 성립하면 된다.

1.  a[pc]와 key가 일치하는 경우
2.  검색 범위가 더이상 없는 경우
   
   

 

 

#이진 검색 알고리즘

from typing import Any, Sequence

def bin_search(a:Sequence, key: Any) -> int:
    pl = 0 #검색 범위 맨 앞의 원소 인덱스
    pr = len(a) -1 #검색 범위 맨 뒤의 원소 인덱스

    while True:
        
        pc = (pl+pr) //2 #중앙의 원소 인덱스를 구하는 것 그리고 나누기를 하면 소숫점 나와서 안 된다고 함
        if a[pc] == key:
            return pc #검색 성공

        #키값이 중앙값보다 큰 경우 중앙값을 다시 세팅
        elif a[pc] < key:
            pl = pc + 1
            #현재의 중앙값 바로 뒤를 검색 범위 맨 앞의 원소 인덱스로 설정해준다.

        else: #키값이 중앙값보다 작은 경우 중앙값 다시 세팅
            pr = pc -1
             #키값이 중앙값보다 작은 경우 pl 검색 범위 맨 앞의 원소 인덱스는 그대로니 pr 검색 범위 맨 뒤의 원소 인덱스를 현재 중앙값의 바로 앞으로 설정

        if pl > pr:
            break
    return -1 #검색 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num

    print("배열의 데이터를 오름차순으로 입력하세요.")

    x[0] = int(input('x[0]:'))
    for i in range(1,num): #x[0]을 입력받아 놓은 상태이기 때문에 x[1]부터 num개 입력받기 시작
        while True:
            x[i] = int(input(f"x[{i}]: "))
            if x[i]>= x[i-1]:#입력 값이 직전 입력값보다 클 경우 프로그램 종류
                break

    ky = int(input('검색할 값을 입력하세요.: '))

    idx = bin_search(x,ky)

    if idx == -1:
        print("검색값을 갖는 원소가 존재하지 않습니다.")

    else:
        print(f"검색 값은 x[{idx}]에 있습니다.")
            

 - if __name__ == '__main__': 가 사용되는 경우는 ①스크립트 파일로 실행 프로그램의 시작점이 맞는지 판단하는 작업. 또한 ②스크립트 파일이 메인 프로그램으로 사용될 때와 모듈로 사용될 때를 구분하기 위한 용도

>>>원소 수를 입력하세요.: 7
배열의 데이터를 오름차순으로 입력하세요.
x[0]:1
x[1]: 2
x[2]: 3
x[3]: 5
x[4]: 7
x[5]: 8
x[6]: 9
검색할 값을 입력하세요.: 5
검색 값은 x[3]에 있습니다.

 

 

이진 검색은 무조건 오름차순, 내림차순으로 정렬이 되어 있어야 한다. 

>>>원소 수를 입력하세요.: 7
배열의 데이터를 오름차순으로 입력하세요.
x[0]:1
x[1]: 2
x[2]: 3
x[3]: 3
x[4]: 4
x[5]: 2
x[5]: 2
x[5]: 2

앞서서 입력한 값보다 작은 값을 입력하면 다시 입력해야 한다. 

이진 검색 알고리즘은 반복할 때마다 검색 범위가 거의 절반으로 줄어드므로 검색하는 데 필요한 비교 횟수는 평균 log n이다. 검색에 실패할 경우는 log(n+1)번이며, 검색에 성공할 경우는 log(n-1)번이다.

 

복잡도

 

선형 검색하는 seq_search( )함수를 바탕으로 시간 복잡도를 알아보자

def seq_search(a: Sequence, key: Any) -> int:
	
    
    i = 0 #1
    while i<n: #2
    	if a[i] == key: #3
        	return i #4 검색 성공 인덱스 반환
        i += 1 #5
        
    return -1 #6 검색 실패 -1 반환
        

단계	실행 횟수	복잡도
1	1	O( 1 )
2	n / 2	O( n )
3	n / 2	O( n )
4	1	O( 1 )
5	n / 2	O( n )
6	1	O( 1 )

---

해시법

검색과 더불어 데이터의 추가, 삭제도 효율적으로 수행할 수 있는 해시법을 알아보도록 하자.

 

정렬된 배열에서 원소 추가하기

 

a

5

6

14

20

29

34

37

51

69

75

-

-

-

 

b

5

6

14

20

29

34

35

37

51

69

75

-

-

                                                                       ↑새로운 값(35)을 추가함에 따라 삽입한 위치 이후의 모든                                                                                  원소를 뒤로 이동해야 한다. 

1. x[5]와 x[6] 사이에 값이 추가되도록 이진 검색법으로 검사합니다.
2. 그림처럼 x[6] 이후의 모든 원소를 한 칸씩 뒤로 이동합니다.
3. x[6]에 35를 대입합니다. 

원소가 이동하는데 필요한 복잡도는 O(n)이고 그 비용은 결코 작지 않다. 물론 데이터를 삭제하는 경우도 이와 똑같은 비용이 발생한다.

 

해시법

해시법(hasihing)은 '데이터를 저장할 위치 = 인덱스'를 간단학 연산으로 구하는 것을 말한다. 이 방법은 원소의 검색뿐 아니라 추가,삭제도 효율적으로 수행할 수 있다. 그림 a에 나타낸 배열의 키(원소의 값)를 원소 개수인 13개로 나눈 나머지를 아래 표로 정리했다. 이 값을 해시값(hash value)이라고 한다. 해시값은 데이터에 접근할 때 기준이 된다.

키	5	6	14	20	29	34	37	51	69	75
해시값(13으로 나눈 나머지)	5	6	1	7	3	8	11	12	4	10

해시값 = 키 % 원소의 개수 (키를 원소 개수로 나눈 나머지가 해시값이 된다.)

 

   0          1          2          3           4          5        6          7            8          9         10         11           12

-

14

-

29

69

5

6

20

34

-

75

37

51

 

-

14

-

29

69

5

6

20

34

35

75

37

51

                                                                                                          ↑ 새로운 값(35)을 추가해도 원소를                                                                                               이동할 필요다 없다.

 

이렇게 키를 해시값으로 변환하는 과정을 해시 함수(hash function)이라고 한다. 또한 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다. 해시 테이블에서 만들어진 원소를 버킷(bucket)이라고 한다.

 

해시 충돌

앞에서 만든 해시 테이블에 18을 추가해보도록 하겠다. 18을 13(해시값)으로 나누면 5지만 지금 x[5] 자리엔 이미 5가 들어차있다. 이미 이와 같이 값이 들어있는 경우엔 해시값과 키가 1:1 대응관계일 필요는 없기 때문에 일반적으로 키와 해시값은 n:1 즉 다대 1 관계이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(Collision)이라고 한다. 

🐸해시 함수는 가능한 한 해시값이 한쪽으로 치우치지 않고 고르게 분산된 값을 출력하도록 만드는 것이 가장 좋다.

 

 

-

14

-

29

69

5

6

20

34

35

75

37

51

                                                           ↑18 추가할 x[5]는 이미 값이 들어 있어서 버킷이 중복되는 현상을 충돌                                                                 이라 한다.

이렇게 해시법 충돌이 발생하는 경우 다음 2가지 방법으로 대처가 가능하다.

• 체인법: 해시값이 같은 원소를 연결 리스트로 관리한다.
• 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복한다.
  
  

체인법

체인법(chaining)이란 해시값이 같은 데이터인 체인(chain)모양의 연결리스트로 연결하는 방법을 말하며 오픈 해시법(open hashing)이라고도 합니다.

 

해시값이 같은 데이터 저장하기

 

체인법으로 구현한 해시의 예시                                                                                                      : None  

체인법에서는 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결합니다. 배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것입니다.

예를 들어 69와 17의 해시값은 둘 다 4이며 이들을 연결하는 연결 리스트의 앞쪽 노드를 참조하여 table[4]에 저장합니다. 참고로 해시값이 0이나 2처럼 데이터가 하나도 없는 버킷의 값을 None이라고 합니다. 

🐸table[4]는 버킷 69를 참조하는 것이며, 버킷 69의 뒤쪽 포인터는 17을 참조하는 것입니다. 또한 버킷 17의 뒤쪽 포인터는 뒤쪽 노드가 존재하지 않음을 알려주는 None입니다. 

 

Node 클래스의 chainedHash 클래스가 정의되어 있으며 체인법으로 구현한 해시 프로그램이다.

#체인법으로 해시 함수 구현하기


from __future__ import annotations

from typing import Any, Type

import hashlip

class Node:
    #해시를 구성하는 노드

    def __init__(self, key:Any, value: Any, next:Node) -> None:
        self.key = key #키
        self.value = value #값
        self.next = next #뒤쪽 노드 참조 
        
    

Node 클래스는 키와 값이 짝을 이루는 구조이다. 키에 해시 함수를 적용하여 해시값을 구한다. 자기 참조형 클래스인 Node의 이미지를 나타내면 자신과 같은 자료형인 인스턴트를 참조하는 것으로 볼 수 있다. '객체에 대한 참조'

Node형 인스턴스를 초기화하는 __init__( ) 함수는 3개의 인수 key, value, next를 전달받아 각각 대응하는 필드인 self.key, self.value, self.next에 대입합니다.

class ChainHash:
    #체인법으로 해시 클래스 구현

    def __init__(self,capacity: int) -> None:
        #초기화

        self.capacity = capacity
        self.table = [None]*self.capacity

    def hash_value(self,key:Any) -> int:
        #해시값을 구함
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib,sha256(str(key).encode()).hedigest(),16)%self.capacity)                

ChainedHash 해시 클래스 만들기

ChainedHash 해시 클래스는 필드 2개로 구성됩니다.

• capacity: 해시 테이블의 크기(배열 table의 원소 수)를 나타냅니다.
• table: 해시 테이블을 저장하는 list형 배열을 나타냅니다.
  
  

_ _ init _ _( ) 함수로 초기화 하기

_ _ init _ _( ) 함수는 빈 해시 테이블을 생성합니다. 매개변수 capacity에 전달받는 것은 해시테이블의 크기입니다. 원소 수가 capacity인 list형의 배열 table을 생성하고 모든 원소를 None으로 합니다.

해시 테이블의 각 버킷은 맨 앞부터 table[0],table[1],table[2].... table[capacity-1]순으로 접근할 수 있습니다. 

_ _ init _ _( )함수가 호출된 직후 배열 table의 모든 원소는 None이고 아래의 표와 같이 전체 버킷이 빈 상태이다. 

 

모든 버킷이 비어 있음(None)

hash_value( )해시 함수 만들기

hash_valoue( ) 함수는 인수 key에 대응하는 해시값을 구합니다. 

---

해시와 해시 함수 알아보기

해시(hash)는 '긁어모음, 뒤죽박죽, 가늘게 썬 고기 음식'을 뜻한다. 만약 충돌이 전혀 발생하지 않는다면 해시 함수로 인덱스를 찾는 것만으로 검색,추가,삭제가 대부분 완려되기 때문에 시간 복잡도는 O(1)입니다. 해시 테이블을 충분히 크게 만들면 충돌 발생을 억제할 수 있지만 이 방법은 메모리의 낭비이다. 즉, 시간과 공간의 트레이드-오프(trade off) 상충관계 문제가 발생한다. 따라서 해시 테이블의 크기는 소수를 선호하며 ChainedHash 클래스의 hash_value( ) 함수는 해시값을 다음과 같이 key가 int형인 경우와 아닌 경우로 구한다.

🐸해시 값은 다이제스트(digest)값이라고도 한다. 

 

key가 int형인 경우

key를 해시의 크기 capacity로 나눈 나머지를 해시값으로 한다. 예를 들어 ChainedHash 클래스를 사용한 프로그램인 것을 보면 key가 int형이고 크기가 13이므로 키를 13으로 나눈 나머지가 해시값이 된다. 

 

key가 int형이 아닌 경우

key가 정수가 아닌 경우(문자열, 리스트, 클래스형 등) 그 값을 바로 나눌 수 없다. 그래서 다음과 같이 표준 라이브러리로 형 변환을 해야 해시값을 얻을 수 있다. 

 

• sha256 알고리즘: hashlib 모듈에서 제공하는 것으로 RSA의 FIPS 알고리즘을 바탕으로 하며, 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘 생성자입니다. hashlib 모듈은 sha256이외에도 MD5 등 다양한 해시 알고리즘을 제공합니다.
• endcode( ) 함수: hashlib.sha256에는 바이트 문자열의 인수를 전달해야 합니다. 그래서 key를 str형 문자열로 변환한 뒤 그 문자열을 encode( ) 함수에 전달하여 바이트 문자열을 생성합니다.
• hexdigest( ) 함수: sha256 알고리즘에서 해시값을 16진수 문자열로 꺼낸다.
• int( ) 함수: hexdigest( ) 함수로 꺼낸 문자열을 16진수 문자열로 하는 int형으로 변환합니다. 

---

키로 원소를 검색하는 search( ) 함수

seach( ) 함수는 key인 원소를 검색한다. search( )함수로 원소를 검색하는 과정을 아래 그림을 참고하여 구체적으로 알아보도록 하겠다. 

33 검색하기

33의 해시값은 7이므로 table[7]이 가리키는 연결 리스트를 찾아간다. 20->33으로 찾아가면 성공입니다.

 

26 검색하기

26의 해시값은 0입니다. table[0]이 None이므로 검색에 실패합니다.

 

search( ) 함수가 원소를 검색하는 과정은 다음과 같이 정리할 수 있다.

1. 해시 함수를 사용하여 키를 해시값으로 변환한다.
2. 해시값을 인덱스로 하는 버킷에 주목한다.
3. 버킷이 참조하는 연결 리스트 맨 앞부터 차례대로 스캔한다. 키와 같은 값이 발견되면 검색에 성공하고, 원소의 맨 끝까지 스캔해서 발견되지 않으면 검색에 실패한다.

def search(self, key:Any) -> Any:
    #키가 key인 원소를 검색해 값을 반환

    hash = self.hash_value(key) #검색하는 키의 해시값
    p = self.table[hash] #노드를 주목

    while p is not None: #검색 성공
        if p.key == key: 
            return p.value #뒤쪽 노드 주목
        p = p.next

    return None #검색 실패

def add (self,key:Any, value:Any)-> bool:
    #키가 key이고 값이 value인 원소를 추가
    hash = self.hash_value(key)
    p = self.table[hash]

    while p is not None:
        if p.key == key:
            return False
        p = p.next

    temp = Node(key,value, self.table[hash])
    self.table[hash] = temp
    return True
    

원소를 추가하는 add( ) 함수 

add( ) 함수는 키가 key이고 값이 value인 원소를 추가합니다.

아래의 그림을 통해서 add( ) 함수에서 원소를 추가하는 과정을 구체적으로 살펴보도록 하자 

 

13 추가하기

먼저 13의 해시값은 0이고 table[0]은 None이다. 저장할 노드를 새로 생성하고, 그 노드에 대한 참조를 table[0]에 대입해야 한다.

46 추가하기

46의 해시값은 7이고 table[7] 버킷에는 20과 33을 연결한 연결 리스트에 대한 참조가 저장되어 있다. 이 리스트 안에 46은 존재하지 않으므로 연결 리스트의 맨 앞에 46을 추가해준다. 구체적으로는 46을 저장하는 노드를 새로 생성하고, 그 노드에 대한 참조를 table[7]에 대입한다. 또 추가한 노드의 뒤쪽 포인터인 next가 20을 저장한 노드를 주목하도록 업데이트 한다.

 

add( )함수에 원소를 추가하는 과정

1. 해시 함수를 사용하여 키를 해시값으로 변환
2. 해시값을 인덱스로 하는 버킷에 주목
3. 버킷이 참조하는 연결 리스트 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이기 때문에 추가에 실패한다. 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가한다. 

원소를 삭제하는 remove( ) 함수

remove( ) 함수는 키가 key인 원소를 삭제한다. 69를 삭제하는 예를 통해 구체적으로 살펴보자.

69의 해시값은 4이며 table[4]의 버킷에 저장되어 있는 참조하는 곳의 리스트를 선형 검색하면 69를 발견할 수 있다. 이 노드의 뒤쪽 노드는 17을 저장한다. 그러므로 그림처럼 17을 저장한 노드에 대한 참조를 table[4] 버킷에 대입하면 노드가 삭제 된다. 즉, 69의 노드에 연결하는 것이 아닌 table[4]의 버킷에 대입하면 된다는 말.

def remove(self, key:Any) -> bool:
    #키가 key인 원소를 삭제

    hash = self.hash_value(key)
    p = self.table[hash]
    pp = None

    while p is not None:
        if p.key == key:
            if pp is None:
                self.table[hash] = p.next
            else:
                pp.next = p.next
            return True
        pp = p
        p = p.next
    return False

def dump(self) -> None:
    #해시테이블을 덤프
    for i in range(self.capacity):
        p = self.table[i]
        print(i, end='')
        while p is not None:
            print(f" -> {p.key} ({p.value})",end ='')
            p = p.next
        print()

원소를 출력하는 dump( ) 함수

 dump( ) 함수는 모든 원소를 덤프하는 것, 즉 해시 테이블의 내용을 한꺼번에 통째로 출력합니다. 해시 테이블의 몯느 원소인 table[0]~table[capacity-1]까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복합니다. 예를 들어 dump( )를 실행하면 아래와 같이 출력이 된다. 

00
01 -> 14 
02
03 -> 29
04 -> 69 -> 17
05 -> 5
06 -> 6
07 ->46 -> 20 -> 33
08
09
10
11
12

해시값이 같은 버킷은 화살표(->)로 연결했다.

이 함수를 실행하면 해시값이 같은 버킷이 연결 리스트에 의해 체인모양으로 묶인 모습을 확인할 수 있다.(원래는 키와 값 모두가 출력이 된다.)

 

지금까지 다룬 ChainHash 클래스를 실제로 사용하는 프로그램을 구현했고, 여기서는 키를 int형 값을 str형 문자열로 한다. 

#체인법을 구현하는 해시 클라스 ChainedHash 사용

from enum import Enum
from chained_hash import ChainedHash

Menu = Enum ('Menu',['추가','삭제','검색','덤프','종료']) #메뉴 선언

def select_menu() -> Menu:
    #메뉴 선택
    s = [f"({m.value}){m.name}"for m in Menu]
    While True:
        print(*s,sep='',end ='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)

hash = chainedHash(13)

while True:
    menu = select_menu() #메뉴 선택

    if menu==Menu.추가 #메뉴 추가 선택
        key = int(input('추가할 키를 입력하세요.:'))
        val = input('추가할 값을 입력하세요')
        if not hash.add(key,val):
            print('추가를 실패했습니다.')
    elif menu == Menu.삭제:
        key = int(input("삭제할 키를 입력하세요:"))
        if not hash.remove(key):
            print("삭제를 실패했습니다")
    elif menu == Menu.검색:
        key = int(input("검색할 키를 입력하세요:"))
        t = hash.search(key)
        if t is not None:
            print(f"검색한 키를 갖는 값은 {t}입니다.")
        else:
            print('검색할 데이터가 없습니다.')
    elif menu == Menu.덤프:
        hash.dump()

    else:
        break