검색의 종류
- 선형 검색
무작위로 늘어놓은 데이터 집합에서 검색을 수행 - 이진 검색
일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행 - 해시법
추가/삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행
- 체인법 : 같은 해시값 데이터를 연결 리스트로 연결
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
선형 검색(linear search)
- 배열에서 검색하는 방법 중 가장 기본적인 알고리즘
- 직선 모양(선형)으로 늘어선 배열에서 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
- 원소의 갯수가 n개일 때 조건을 판단하는 횟수는 평균 n/2번임.
배열에서 선형검색을 하는 프로그램
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
i = 0
for i in range(len(a)):
if a[i] == key:
return i
return -1선형검색의 종료 조건
- 검색 실패 : 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우
if i == len(a)- 검색 성공 : 검색할 값과 같은 원소를 찾은 경우
if a[i] == key
보초법
- 선형 검색은 반복할 때마다 2가지 종료 조건을 체크하기 때문에, 종료 조건을 검사하는 비용을 무시할 수 없음.
- 이 비용을 반으로 줄이는 방법이 보초법(sentinel method)임.
배열의 맨 뒤에 찾고자 하는 값을 추가하여(이 때 저장하는 값을 보초(sentinel)이라고 함) 위 코드의
if a[i] == key:를 판단할 필요없게 만듬
- 보초법을 활용해 수정된 코드
from typing import Any, Sequence
import copy
def seq_search(seq: Sequence, key: Any) -> int:
a = copy.deepcopy(seq)
a.append(key)
i = 0
while True:
if a[i] == key:
break
i += 1
return -1 if i == len(seq) else i이진 검색(binary search)
- 선형 검색보다 빠르게 검색할 수 있음
- 배열의 데이터가 정렬되어 있어야만 사용가능
- 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl(0), pr(n-1), pc((n-1)//2)로 초기화하고,
검색이 한 단계씩 진행될 때마다 검색 범위를 반으로 좁힘- 검색 범위가 절반씩 줄어들기 때문에 검색하는데 필요한 횟수는 평균
log n번 임, 검색에 실패할 경우log(n+1)번, 성공할 경우는log n - 1번
- a[pc] < key 일때
중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝을 pl로 지정하여, 검색 범위를 뒤쪽 절반으로 좁힘 - a[pc] > key 일때
중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝을 pr로 지정하여, 검색 범위를 앞쪽 절반으로 좁힘
이진 검색 프로그램
from typing importy 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 # 검색 범위를 앞쪽 절반으로 좁힘
if pl > pr:
break
return -1 # 검색 실패이진 검색의 종료조건
- a[pc]와 key가 일치하는 경우
- 검색 범위가 더 이상 없는 경우
복잡도
- 프로그램의 실행 속도는 하드웨어나 컴파일러의 조건에 따라 달라지나, 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 함.
- 복잡도의 구체적인 내용은 다른 글에 따로 작성 예정
- 시간 복잡도 : 실행하는데 필요한 시간을 평가
- 공간 복잡도 : 메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가
해시법
- 검색과 데이터의 추가/삭제도 수행 가능
- '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것
해시값
- 배열의 각 원소의 값을 원소 개수(인덱스 값이 아닌 갯수)로 나눈 나머지
해시 테이블
- 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열
- 새로운 데이터를 저장할 때도 해시값으로 나눠 해당 인덱스번호에 추가하면 되기 떄문에 원소를 이동할 필요 없음.
해시 함수
- 키(원소의 값)를 해시값으로 변환하는 과정
버킷
- 해시 테이블에서 만들어진 원소
해시충돌
- 새로운 값을 추가하려고 할 때 버킷이 중복되는 현상
- 해결법
- 체인법 : 해시값이 같은 원소를 연결 리스트로 관리
- 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복
체인법
- 해시값이 같은 데이터를 체인모양의 연결 리스트로 연결하는 방법(오픈 해시법)
체인법으로 구현한 해시 프로그램
from __future__ import annotations
from typing import Any, Type
import hashlib
class Node: # 해시를 구성하는 노드
def __init__(self, key: Any, value: Any, next: Node) -> None: # 초기화
self.key = key # 키
self.value = value # 값
slef.next = next # 뒤쪽 노드 참조- Node 클래스는 키와 값이 짝을 이루는 구조로 키에 해시 함수를 적용해 해시값을 구함
class ChaineHash:
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()).hexdigest(), 16) % self.capacity)- __init__() 함수가 호출된 직후 배열의 모든 원소는 None이고 전체 버킷이 빈 상태임
- hash_value() 함수는 인수 key에 대응하는 해시값을 구함
return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)key가 int형이 아닐경우를 대비하여 사용
- hashlib 모듈을 사용하여 SHA256 해시 알고리즘을 사용합니다.
- str(key)는 파라미터로 전달된 key값을 문자열로 변환합니다.
- encode()는 문자열을 바이트 코드로 변환합니다.
- sha256()은 파이썬 내장 모듈인 hashlib을 이용하여 SHA-256 해시를 생성합니다. 이 함수는 바이트 코드를 입력으로 받아서 256비트의 해시 값을 생성합니다.
- hexdigest()는 생성된 해시값을 16진수 문자열로 반환합니다.
- int()는 문자열을 정수형으로 변환합니다. 이 함수는 첫번째 파라미터로 받은 문자열을 두번째 파라미터로 받은 진법으로 변환합니다. 여기서는 16진수 문자열을 16진수 정수형으로 변환합니다.
- % self.capacity는 해시 테이블의 크기를 사용하여 해시 값을 해시 테이블 내 인덱스 값으로 변환합니다. 이 값은 나머지 연산자를 사용하여 해시 값을 해시 테이블 크기로 나눈 나머지 값입니다.
결과적으로, 이 코드는 입력된 key값을 문자열로 변환하고, SHA-256 해시 알고리즘을 사용하여 256비트의 해시값을 생성합니다. 그리고 나서 이 값을 16진수 문자열로 변환하고, 16진수 정수형으로 변환합니다. 마지막으로, 해시 테이블의 크기를 사용하여 이 값을 해시 테이블 내 인덱스 값으로 변환합니다.
- sha256 해시 알고리즘
hashlib 모듈에서 제공하는 것으로, 주어진 바이트 문자열의 해시값을 구하는 해시 알고리즘의 생성자.
search() 함수
- 해시 함수를 사용해 키를 해시값으로 변환
- 해시값을 인덱스로 하는 버킷에 주목
- 버킷이 참조하는 연결 리스트를 맨 앞부터 스캔
- 키와 같은 값이 발견되면 검색 성공, 원소의 맨 끝까지 발견되지 않으면 검색 실패
def search(self, key: Any) -> Any:
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 # 검색 실패add() 함수
- 해시 함수를 사용하여 키를 해시값으로 변환
- 해시값을 인덱스로 하는 버킷에 주목
- 버킷이 참조하는 연결리스트를 선형 검색
- 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패
- 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가
def add(self, key: Any, value: Any) -> bool:
hash = self.hash_value(key) # 추가하는 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 # 추가 성공remove() 함수
- 해시 함수를 이용해 키를 해시값으로 변화
- 해시값을 인덱스로 하는 버킷에 주목
- 버킷이 참조하는 연결 리스트를 선형 검색
- 키와 같은 값이 발견되면 해당 노드를 리스트에서 삭제
def remove(self, key: Any) -> bool:
hash = self.hash_value(key) # 삭제할 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 # key 삭제 성공
pp = p
p = p.next # 뒤쪽 노드를 주목
return False # 삭제 실패(key가 존재 x)dump() 함수
- 해시 테이블의 내용을 한꺼번에 통째로 출력
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()오픈 주소법
- 충돌이 발생했을때 재해시(rehashing)을 수행해 빈 버킷을 찾는 법(닫힌 해시법)
- 재해시를 위한 해시 함수는 자유롭게 정할 수 있음 ex) 키에 1을 더하여 재해시
원소 추가 시는 재해시를 반복
원소 삭제 시 처음부터 비어있는 곳은(-)으로 표현, 삭제된 것은(★)으로 표현
원소 검색 시 기존 해시값으로 부터 다음 -을 만날때까지 검색
from __future__ import annotations
from typing import Any, Type
from enum import Enum
import hashlib
# 버킷의 속성
class Status(Enum):
OCCUPIED = 0 # 데이터를 저장
EMPTY = 1 # 비어 있음
DELETED = 2 # 삭제 완료
class Bucket:
"""해시를 구성하는 버킷"""
def __init__(self, key: Any = None, value: Any = None,
stat: Status = Status.EMPTY) -> None:
"""초기화"""
self.key = key # 키
self.value = value # 값
self.stat = stat # 속성
def set(self, key: Any, value: Any, stat: Status) -> None:
"""모든 필드에 값을 설정"""
self.key = key # 키
self.value = value # 값
self.stat = stat # 속성
def set_status(self, stat: Status) -> None:
"""속성을 설정"""
self.stat = stat
class OpenHash:
"""오픈 주소법을 구현하는 해시 클래스"""
def __init__(self, capacity: int) -> None:
"""초기화"""
self.capacity = capacity # 해시 테이블의 크기를 지정
self.table = [Bucket()] * self.capacity # 해시 테이블
def hash_value(self, key: Any) -> int:
"""해시값을 구함"""
if isinstance(key, int):
return key % self.capacity
return(int(hashlib.md5(str(key).encode()).hexdigest(), 16)
% self.capacity)
def rehash_value(self, key: Any) -> int:
"""재해시값을 구함"""
return(self.hash_value(key) + 1) % self.capacity
def search_node(self, key: Any) -> Any:
"""키가 key인 버킷을 검색"""
hash = self.hash_value(key) # 검색하는 키의 해시값
p = self.table[hash] # 버킷을 주목
for i in range(self.capacity):
if p.stat == Status.EMPTY:
break
elif p.stat == Status.OCCUPIED and p.key == key:
return p
hash = self.rehash_value(hash) # 재해시
p = self.table[hash]
return None
def search(self, key: Any) -> Any:
"""키가 key인 갖는 원소를 검색하여 값을 반환"""
p = self.search_node(key)
if p is not None:
return p.value # 검색 성공
else:
return None # 검색 실패
def add(self, key: Any, value: Any) -> bool:
"""키가 key이고 값이 value인 요소를 추가"""
if self.search(key) is not None:
return False # 이미 등록된 키
hash = self.hash_value(key) # 추가하는 키의 해시값
p = self.table[hash] # 버킷을 주목
for i in range(self.capacity):
if p.stat == Status.EMPTY or p.stat == Status.DELETED:
self.table[hash] = Bucket(key, value, Status.OCCUPIED)
return True
hash = self.rehash_value(hash) # 재해시
p = self.table[hash]
return False # 해시 테이블이 가득 참
def remove(self, key: Any) -> int:
"""키가 key인 갖는 요소를 삭제"""
p = self.search_node(key) # 버킷을 주목
if p is None:
return False # 이 키는 등록되어 있지 않음
p.set_status(Status.DELETED)
return True
def dump(self) -> None:
"""해시 테이블을 덤프"""
for i in range(self.capacity):
print(f'{i:2} ', end='')
if self.table[i].stat == Status.OCCUPIED:
print(f'{self.table[i].key} ({self.table[i].value})')
elif self.table[i].stat == Status.EMPTY:
print('-- 미등록 --')
elif self.table[i] .stat == Status.DELETED:
print('-- 삭제 완료 --')