728x90
이전 글
2022.11.27 - [Code/Algorithm] - [Algorithm] 검색 알고리즘_2 (선형 검색)
[Algorithm] 검색 알고리즘_2 (선형 검색)
03-2 선형 검색 선형 검색(linear search) 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘 선형 검색
heejins.tistory.com
2022.11.28 - [Code/Algorithm] - [Algorithm] 검색 알고리즘_3 (이진 검색)
[Algorithm] 검색 알고리즘_3 (이진 검색)
이전 글(선형 검색) 2022.11.27 - [Code/Algorithm] - [Algorithm] 검색 알고리즘_2 (선형 검색) [Algorithm] 검색 알고리즘_2 (선형 검색) 03-2 선형 검색 선형 검색(linear search) 직선 모양(선형)으로 늘어선 배열에서
heejins.tistory.com
03-4 해시법
해시법
- 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말합니다. 이 방법은 원소의 검색뿐 아니라 추가·삭제도 효율적으로 수행할 수 있습니다.
- 해시값은 원소의 개수를 기준으로 합니다. 해시값은 데이터에 접근할 때 기준이 됩니다.
- 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시 테이블(hash table)입니다.
- 키를 해시값으로 변환하는 과정을 해시 함수(hash function)라고 합니다. 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용합니다.
- 해시 테이블에서 만들어진 원소를 버킷(bucket)이라고 합니다.
해시 충돌
- 키와 해시값의 대응 관계가 꼭 1:1일 필요는 없습니다. 키와 해시값은 일반적으로 다대 1(n:1)입니다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 합니다.
- 이렇게 해시법에서 충돌이 발생하는 경우 다음 2가지 방법으로 대처할 수 있습니다.
- 체인법: 해시값이 같은 원소를 연결 리스트로 관리합니다.
- 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복합니다.
체인법(chaining)
- 체인법: 해시값이 같은 데이터를 체인(chain) 모양의 연결 리스트로 연결하는 방법을 말하며, 오픈 해시법(open hashing)이라고도 합니다.
해시값이 같은 데이터 저장하기
체인법에서는 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결합니다. 배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드(head node)를 참조하는 것입니다.
실습 3-5 체인법으로 해시 함수 구현하기
# 체인법으로 해시 함수 구현하기
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
self.next = nextNode 클래스 만들기
- Node 클래스는 개별 버킷을 나타냅니다.
- key: 키(임의의 자료형)
- value: 값(임의의 자료형)
- next: 뒤쪽 노드를 참조(Node형)
Node형 인스턴스를 초기화하는 __init__() 함수는 3개의 인수 key, value, next를 전달받아 각각 대응하는 필드인 self.key, self.value, self.next에 대입합니다.
class ChainedHash:
"""체인법으로 해시 클래스 구현"""
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)ChainedHash 해시 클래스 만들기
- capacity: 해시 테이블의 크기(배열 table의 원소 수)를 나타냅니다.
- table: 해시 테이블을 저장하는 list형 배열을 나타냅니다.
__init__() 함수로 초기화 하기
- __init__() 함수는 빈 해시 테이블을 생성합니다. 매개변수 capacity에 전달받는 것은 해시 테이블의 크기입니다. 원소 수가 capacity인 list형의 배열 table을 생성하고 모든 원소를 None으로 합니다.
hash_value() 해시 함수 만들기
hash_value() 함수는 인수 key에 대응하는 해시값을 구합니다.
해시와 해시 함수 알아보기
- 해시(hash): '긁어모음, 뒤죽박죽, 가늘게 썬 고기 음식'을 뜻합니다. 만약 충돌이 전혀 발생하지 않는다면 해시 함수로 인덱스를 찾는 것만으로 검색·추가·삭제가 대부분 완료되므로 시간 복잡도는 모두 O(1)입니다.
- 해시 테이블을 충분히 크게 만들면 충돌 살생을 억제할 수 있지만 이 방법은 메모리를 낭비합니다. = 시간과 공간의 트레이드-오프(trade off - 상충 관계) 문제가 발행합니다.
- 충돌을 피하려면 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성해야 합니다. 따라서 해시 테이블의 크기는 소수를 선호합니다.
- ChainedHash 클래스의 hash_value() 함수는 해시값을 다음과 같이 key가 int형인 경우와 아닌 경우로 구합니다.
- key가 int형인 경우: key를 해시의 크기 capacity로 나눈 나머지를 해시값으로 합니다.
- key가 int형이 아닌 경우: key가 정수가 아닌 경우(문자열, 리스트, 클래스형 등) 그 값으로는 바로 나눌 수 없습니다. 그래서 다음과 같은 표준 라이브러리로 형 변환을 해야 해시값을 얻을 수 있습니다.
- sha256 알고리즘:hashlib 모듈에서 제공하는 sha256은 RAS의 FIPS 알고리즘을 바탕으로 하며, 주어진 바이트(byte) 문자열의 해시값을 구하는 해시 알고리즘의 생성자(constructor)입니다. hashlib 모듈은 sha256 외에도 MD5 알고리즘인 md5등 다양한 해시 알고리즘을 제공합니다.
- encode() 함수: hashlib.sha256에는 바이트 문자열의 인수를 전달해야 합니다. 그래서 key를 str형 문자열로 변환한 뒤 그 문자열을 encode() 함수에 전달하여 바이트 문자열을 생성합니다.
- hexdigest() 함수: sha256 알고리즘에서 해시값을 16진수 문자열로 꺼냅니다.
- int() 함수: hexdigest() 함수로 꺼낸 문자열을 16진수 문자열로 하는 int형으로 변환합니다.
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) # 추가하는 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 # 추가 성공키를 원소로 검색하는 search() 함수
search() 함수는 key인 원소를 검색합니다.
1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.
2. 해시값을 인덱스로 하는 버킷에 주목합니다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔합니다. 키와 같은 값이 발견되면 검색에 성공하고, 원소의 맨 끝까지 스캔해서 발견되지 않으면 검색에 실패합니다.
원소를 추가하는 add() 함수
add() 한수는 키가 key이고 값이 value인 원소를 추가합니다.
1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.
2. 해시값을 인덱스로 하는 버킷에 주목합니다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 합니다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패합니다. 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가합니다.
def remove(self, key:Any) -> bool:
"""키가 key인 원소를 삭제"""
hash = self.hash_value(key) # 삭제할 key의 해시값
p = self.table[hash] # 노드를 주목
pp = None # 바로 앞의 노드를 주목
while p is not None:
if p.key == 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가 존재하지 않음)
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()원소를 삭제하는 remove() 함수
키가 key인 원소를 삭제합니다.
1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.
2. 해시값을 인덱스로 하는 버킷에 주목합니다.
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색합니다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제합니다. 그렇지 않으면 삭제에 실패합니다.
원소를 출력하는 dump() 함수
해시 테이블의 내용을 한꺼번에 통째로 출력합니다.
해시 테이블의 모든 원소인 table[0] ~ table[capacity - 1]까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복합니다.
실습 3-6 체인법을 구현하는 해시 클래스 ChainedHash의 사용
# 체인법을 구현하는 해시 클래스 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) # 크기가 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(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 1
추가할 값을 입력하세요.: heedy
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 5오픈 주소법(open addressing)
- 해시 충돌이 발생할 때 해결하는 또 다른 방법으로 오픈 주소법이 있습니다.
- 오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고도 합니다.
- 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법(linear probing)이라고도 합니다.
원소 추가하기
- 위 그림 a는 18을 추가하여 충돌이 발생하는 상태를 보여 줍니다. 이럴 때 재해시를 수행할 수 있습니다.
- 재해시를 위한 해시 함수는 자유롭게 정할 수 있습니다. 여기에서는 키에 1을 더하여 13으로 나눈 나머지를 사용합니다.
- 재해시를 위한 식(18 + 1) % 13으로 나머지 6을 얻었습니다. 그런데 위 그림 b처럼 인덱스 6인 버킷도 값이 채워져 있으므로 재해시를 합니다.
- 이번에는 (19 + 1) % 13을 통해 7을 얻으므로, c와 같이 인덱스 7인 버킷에 19를 추가합니다.
원소 삭제하기
- 위 그림 c에서 5를 삭제하는 과정을 살펴봅시다. 인덱스가 5인 버킷을 비우기만 하면 될 것 같지만 실제로는 그렇지 않습니다.
- 해시값이 같은 18을 검색할 때 해시값이 5인 데이터는 존재하지 않는다고 착각하여 검색에 실패하기 때문입니다.
- 이러한 오류를 방지하기 위해서 각 버킷에 다음과 같은 속성을 부여합니다.
- 데이터가 저장되어 있음(숫자)
- 비어 있음(-)
- 삭제 완료(★)
- 위 그림과 같이 버킷이 비어 있는 상태를 -으로, 삭제 완료된 상태를 ★로 나타냈습니다.
원소 검색하기
- 17을 검색한다고 가정해 봅시다. 해시값이 4인 버킷을 들여다보면 속성은 비어 있음(-)이므로 검색 실패라고 판단할 수 있습니다.
- 18을 검색하는 경우를 위 그림을 보며 생각해 봅시다. 18의 해시값이 5인 버킷의 속성은 삭제 완료(★)입니다.
- 재해시하여 해시값이 6인 버킷의 속성을 살펴보지만 6이 저장되어 있으므로 다시 재해시하여 7인 버킷을 들여다봅니다. 검색하는 값 18이 저장되어 있으므로 검색 성공입니다.
실습 3-7 오픈 주소법으로 해시 함수 구현하기
# 오픈 주소법으로 해시 함수 구현하기
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('--삭제 완료--')실습 3-8 오픈 주소법을 구현하는 해시 클래스 Openhash 사용
# 오픈 주소법을 구현하는 해시 클래스 Openhash 사용
from enum import Enum
from open_hash import OpenHash
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 = OpenHash(13) # 크기가 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(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 1
추가할 값을 입력하세요.: 수연
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 5
추가할 값을 입력하세요.: 동혁
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 10
추가할 값을 입력하세요.: 예지
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 12
추가할 값을 입력하세요.: 원준
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 14
추가할 값을 입력하세요.: 민서
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 3
검색할 키를 입력하세요.:5
검색한 키를 갖는 값은 동혁입니다.
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 4
0--미등록--
11 (수연)
214 (민서)
3--미등록--
4--미등록--
55 (동혁)
6--미등록--
7--미등록--
8--미등록--
9--미등록--
1010 (예지)
11--미등록--
1212 (원준)
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 2
삭제할 키를 입력하세요.: 14
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 4
0--미등록--
11 (수연)
2--삭제 완료--
3--미등록--
4--미등록--
55 (동혁)
6--미등록--
7--미등록--
8--미등록--
9--미등록--
1010 (예지)
11--미등록--
1212 (원준)
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 5체인법과 오픈 주소법의 실행 결과 비교
- 체인법: 해시값이 같은 (1 수연)과 (14, 민서)를 연결하는 연결 리스트가 버킷 1에 연결되어 있습니다.
- 오픈 주소법: 나중에 추가한 (14 민서)는 재해시 결과 버킷 2에는 등록되어 있습니다. 또 데이터를 삭제한 뒤 버킷 2는 삭제 완료 속성이 들어 있습니다.
- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B2%80%EC%83%89%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb
GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습
파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습. Contribute to heejvely/Algorithm development by creating an account on GitHub.
github.com
728x90
'Code > Algorithm' 카테고리의 다른 글
| [Algorithm] 스택과 큐_2 (0) | 2022.12.05 |
|---|---|
| [Algorithm] 스택과 큐_1 (0) | 2022.12.02 |
| [Algorithm] 검색 알고리즘_3 (이진 검색) (2) | 2022.11.28 |
| [Algorithm] 검색 알고리즘_2 (선형 검색) (0) | 2022.11.27 |
| [Algorithm] 검색 알고리즘_1 (0) | 2022.11.27 |