MIT - Introduction to Algorithms
- Lecture 10. Open Addressing, Cryptographic Hashing
해싱 3. 개방 주소법, 암호 해싱 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
Open Addressing 개방 주소법 : 해시 테이블을 구현하기 가장 쉬운 방법
배열을 사용 해시 테이블 구현
오늘은 연결 리스트와 포인트를 없애고 하나의 배열 자료구조를 사용 해시 테이블 구현
그러나 효율적으로 쓰기 위해서는 정교함이 필요
균일 해싱이라는 가정 또한 필요
컴퓨터 보안과 암호학에서 사용하는 Crytographic Hashing 응용
암호적인 해시의 개념과 비밀번호 저장, 파일 손상 검사와 같은 암호 해시 함수 응용을 알아볼 것 (보통의 해시 테이블과는 다를 것)
Open Addressing 개방 주소법
충돌이 있을 경우 Chaining을 사용하지만 오늘은 사용하지 않음
no chaining
Figure 1. one item per slot : m >= n
m : # of slots
n : # of elements
Probing(조사)이라는 개념을 사용
cf) probing 1. 진실을 캐기 위한 2. 면밀히 살피는
probe 1. 캐묻다, 캐다, 조사하다 2. (특히 길고 가느다란 기구로) 살피다 3. (철저한) 조사
데이터 삽입을 통해 해시 테이블 사용 여부를 살피고 안되면 key에 대한 다른 해시값을 구함을 반복하는 과정
-> 비어있는 슬롯을 찾을 때까지 계속 조사
h(k,1), h(k,2), h(k,3) ... , h(k,m-1)
k : arbitrary key
우리는 0~ m-1 까지의 순서가 되기를 희망
to be a permutation of 0,1,...m-1
이유 : 해시 테이블 전체를 사용함으로써 슬롯의 낭비를 피하고 싶어서
각 slot들에 균일 해시 테이블에 동등하게 분배되기 위한 기회가 주어져야함
ㅇ
Insert 삽입
Init
Insert 586 / h(586,1)=1
h(133,1)=2, h(204,1)=4, h(481,1)=6
Insert (496) / h(496,1)=4 가정
slot이 이미 204의 값으로 차있다. -> 첫 조사 실패 Fail
h(496,2)=1
slot이 이미 586의 값으로 차있다. -> Fail
h(496,3)=3
slot = None -> 값을 넣음
탐색Search나 삭제Deleting를 보기 전 데이터 삽입 과정이 얼마나 걸릴까에 대해 생각
삽입 한 번 하고 탐색한다면?
None(flag) : empty slot
Search(k)
empty slot -> return None
삽입할 때의 순서와 조사할 때의 순서가 같기 때문에 조사할 때 slot이 None이라면 본래 Key 값이 들어 있어야하지만 없기 때문에 None을 return함
그렇다면 Deleting에 의해 없어진 None의 경우는?
-> 다음 페이지에서
Deleting에 비하면 Insert, Search는 쉬운 편
Search 496 : return None -> Fail
틀린 결과 Fail Incorrectly
데이터 삭제시 삭제된 항목을 None으로 바꾸는 것이 아닌 Delete Me라는 flag 형태로 표시한다면 됨
Search에서 Delete Me라는 flag일 때의 행동을 추가해줘야함
다음으로 넘어가게끔 코드(아마 Continue 쓰지 않을까 생각)
cf) flag 1. (중요한 정보 옆에) 표시를 하다
얼마나 잘 작동할 것인가
Probing Strategies : 해시 함수를 개방 주소법에 쓸 수 있게 바꾸는 일
Linear Probing
순열 조건을 만족하는가
h(k,1), h(k,2), h(k,3) 순열을 만족
틀린 것은? 군집화 clustering
자세히는 보이지 않지만 왜 그런지 간단히 설명하면
군집화는 값이 들어있는 연속된 슬롯들이 생기는 것을 말하는데 이 연속되는 슬롯 군집이 계속 커질 가능성이 크다.
이것은 항목 균형화에 있어 좋지 않다.
군집화 <=> 부하 분산
예) 100개의 슬롯이 있고 군집이 4라면 4/100이 1/100보다 크므로 100개 중 무작위 위치로 가는 것보다 군집되어 있는 4개로 갈 확률이 높다.
이것은 결국 더 큰 군집화를 부르기 때문에 선형 조사의 문제가 된다.
=> 평균 상수 시간의 성질을 잃음
타당한 확률적 가정에 있어 0.01 < alpha = n/m < 0.99
cluster size = theta(log n)
-> 데이터의 삽입과 탐색이 더이상 상수 시간이 아니게 됨 -> bad
참고로 이상적인 해시 함수 h`에 대해서 체이닝을 쓰면 잘 됨
먼저 생각해야하는 것은 어떻게 순열을 보장할 것인가
정수론에 기반해 순열을 보장하기 위한 순열 조건으로 h2와 m이 가져야할 특성은?
=> 서로소 relatively prime between h2 and m
m = 2의 지수 = 배열의 크기
h2 = 홀수
Uniform Hashing Assumption(not Simple Uniform Hashing Assumption)
실제로는 어렵지만 이중 해싱에서는 비슷하게 가능
이 조건을 충족하는 해시 함수는 없음
의미하는 바는?
alpha = n/m = 적재율
Cost of operation insert <= 1/(1-alpha), alpha -> 1
안 좋은 상수인 적재율이 낮기를 원함
적재율이 0.99라면 100번의 탐색이 필요
개방 주소법은 포인터를 쓰지 않기에 구현이 쉽고 적은 메모리를 차지하지만
적재율이 0.5 이하로 조절해야하는 단점이 있다.
(메모리 리소스를 적게 차지할 뿐 메모리는 m이 커야하므로 많이 차지하지 않나라는 개인적 생각)
즉 테이블이 가득 찬 상태에서 모든 데이터를 삭제하고 탐색하면 루프를 돈다.
체이닝 해시 테이블의 연결 리스트에서는 데이터 삭제시 체인이 줄어들기에 적재율이 줄어든다
그러나 개방 주소법의 Delete Me flag의 경우 적재율 감소에 지연이 생긴다.
-> 적재율을 잘 정의해야한다. 적재율이 0.5, 0.6이면 문제가 생김
테이블 크기를 조절할 때 새로운 테이블을 만든다면 해시를 다시 해줘야하므로 Delete Me를 지워도 됨
데이터 삽입 연산 비용이 특정 값 이하인 것을 보이는 증명
p = (m-n)/m = 첫 번째 시도로 성공할 확률 = 1-alpha
비밀번호를 칠 때 unix 시스템이 뭘 하는지 생각해보면
자신이 친 암호와 맞는지 확인하는 절차가 필요
가장 멍청한 방법은? 해싱
문서에 저장, 필요할 때마다 읽음
시스템 관리자도 내 비밀번호를 모르게 하고싶다면?
-> 단방향적 암호학적 해시를 사용하면 됨 One-way
given h(x)=Q it is very hard to find x s.t h(x) =Q
/etc/passwd : devades : x12467 해싱
x` = typed in password
h(x`)=h(x) compare compute
