이진 검색:원소가 오름차순이나 내림차순으로 정렬된 배열에서 사용
ex) 5 7 15 28 29 31 39 58 68 70 95에서 39찾기
39는 중간 값 31 보다 큼
-> 31 뒤 부터 검색
39 58 68 70 95
39는 중간 값 68보다 작음
-> 68 앞 부터 검색
39 58
39는 중앙 값 39와 일치 -> 검색 성공
검색 범위의 맨 앞,맨 뒤,중앙 -> pl,pr,pc
pl = 0,pr = n - 1,pc = (n-1)//2로 초기화
list[pc]와 key값을 비교
1.a[pc] < key일 때
검색 범위는 a[pc + 1]~a[pr]로 좁혀짐,pl = pc + 1로 업데이트
2.a[pc] > key일 때
검색 범위는 a[pl]~a[pc - 1]로 좁혀짐,pr = pc = 1로 업데이트
pr > pl이 되면 검색 실패
반복할 때마다 검색 범위가 거의 절반 씩 줄어들음
필요한 비교 횟수 평균 log(n)
검색에 실패할 경우는 log(n+1)
검색에 성공할 경우는 log(n-1)
*시간 복잡도(time complexcity):실행하는 데 필요한 시간을 평가
*공간 복잡도(space complexity):메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가
해시법은 검색 뿐만 아니라 데이터의 추가,삭제도 효율적으로 수행 가능
'데이터를 저장할 위치 = 인덱스' 를 간단한 연산으로 구함.
해시값(hash value) : 키(배열 값) % 원소 개수
해시 테이블(hash table) : 해시값 새로 저장한 배열
ex) 원소 값이 14면 x[1]에 저장
해시 함수(hash function) : 키를 해시값으로 변환
버킷(bucket) : 해시 테이블에서 만들어진 원소
키와 해시값의 대응 관계과 n:1이 될 때 , 즉 버킷이 중복되는 현상을 충돌(collision)이라고 한다.
ex) 18 % 13 했는데 x[5]에 버킷이 이미 있음
이때 두 가지 방법으로 대처 가능
체인법: 해시값이 같은 원소를 연결 리스트로 관리,오픈 해시법이라고도 한다.
노드
해시 테이블
* int(,16)은 16진수로 만들어줌. 사실 default가 10임.hex()랑 똑같음
검색,추가 기능 구현
삭제,덤프 기능 구현
*덤프: 전부 보여주는거
연결 리스트에서 보통 위치를 저장해서 연결하는데 이건 next에 객체 자체를 넣어서 낯설었다...ㅜ
*Enum은 열거형(Enumerated Type)이라고 부름. 해당 언어의 상수 역할을 하는 식별자로, 일부 열거자 자료형은 언어에 기본으로 포함되어 있음. 그 대표적인 예가 Boolean 자료형으로 False, True 값이 미리 정의된 열거형으로 볼 수 있다.대부분의
ex) False == 0, True == 1
응용해보았다.
해시 충돌이 발생했을 때 재해시(rehashing)을 수행하여 빈 버킷을 찾음.
닫힌 해시법(closed hashing)이라고도 한다.
다음은 오픈 주소법을 이용한 것
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):
# ex) key의 자료형은 Any라고 어노테이션 해주고 값은 None이다.init함수니까 값을 넣어준거
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)
# 여기선 튀어나온 해시값에 1을 더해주는거지 원래 key값에 더하는게 아님
def search_node(self, key: Any) -> Any:
# 검색
hash = self.hash_value(key)
p = self.table[hash]
for i in range (self.capacity):
if p.stat == Status.OCCUPIED and p.key == key:
return p
elif p.stat == Status.EMPTY:
return None
hash = self.rehash_value(hash) # 재해시
p = self.table[hash]
return False # 해시 테이블이 가득 참
def search(self, key: Any) -> Any:
#같은 키의 원소를 검색하여 값을 반환,그냥 search_node에서 p 받아와서 p.value 뱉음
p = self.search_node(key)
if p is not None:
return p.value
else:
return None
def add(self, key: Any, value: Any) -> bool:
if self.search(key) is not None:
return False
hash = self.hash_value(key) # 추가하는 키의 해시값
p = self.table[hash]
for i in range (len(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) -> bool:
p = self.search_node(key)
if p is None:
return False
p.set_status(Status.DELETED)
# 파이썬 변수 선언은 값 복사가 아니라 바인딩이라...? 잘 모르겠음 ㅠ
return True
....
이것도 만들어 보았다.