MIT - Introduction to Algorithms
- Lecture 8. Hashing with Chaining 해싱 1 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/
모든 프로그래밍 언어에서 사용
Dictionary라고도 부르는 추상적 데이터 타입(ADT)
insert(item), delete(item), search(key)가 있는데 이 중 탐색은 가장 흥미로운 부분
search(key) : return item with given key or report doesn't exist
이진 트리의 경우 키를 찾지 못한다면 다음으로 크거나 작은 조건의 다음 값을 찾지만
딕셔너리에서는 이런 일은 할 수 없다
단지 키의 존재값만을 알 수 있음
insert(item) : overwirte any existing key
AVL tree와 같은 이진 트리로 만들어 낼 수 있다
모든 연산을 Olog n)으로 수행
이전 시간 비교 모델에서 정렬이 nlog n 탐색은 log n이 최적임을 보았음
오늘은 탐색을 log n보다 빠르게 하는 법을 알아볼 것 : O(1) Constant time
cf) clobber 1. (사람을) 두들겨 패다 2. (특히 경제적으로) 호된 처벌을 가하다 3. 완패시키다
Python : dict
D[key] ~ search
D[key] = val ~ insert
del D[key] ~ delete
어떻게 구현하는지가 오늘의 주제
item = (key, value)
쉽고 빠름, 모든 프로그래밍 언어에 딕셔너리가 존재
데이터 베이스를 2 종류로 나뉘는데 하나는 해싱을 사용 또 다른 하나는 탐색 트리를 사용
대부분 데이터 베이스는 해싱이 필요
딕셔너리가 빠르다보니 철자 하나하나 살펴보는 것이 가능해서 비슷한 단어, 맞춤법에 사용
컴퓨터는 메모리 주소로 생각하기 때문에 변수 이름을 물리적 주소로 변환하는 작업이 필요하다 -> 이제는 느려서 이 방법은 사용하지 않음
컴파일할 때 역시도 딕셔너리
라우터 : 연결된 모든 장치 IP 주소를 알아야하는 것 이 때 dict
패킷을 특정 포트에 전달할 때 어떤 앱이나 소켓이 포트에 연결되어 있는지 살펴볼 때 사용
엄밀하게 딕셔너리가 아닌 미묘한 것이 있지만 해싱 개념에서 사용하는 것
예) 문자열 탐색 substring search
ctrl+f or ctrl+s or /로 찾을 때 해싱
grep in Unix, google search
string commonalities 공통된 단어
파일, 디렉토리 동기화
Unix : rsync or unison
암호학에서도 파일을 변환할 때 알맞은 파일을 변환하는지 확인할 때 누군가 가로채고 바꿨는지 확인할 때 암호 해시 사용
배열의 인덱스 : 키
파이썬에서 딕셔너리에 접근하는 것은 배열에 접근하는 것과 같다
배열은 키가 음이 아닌 정수로 제한 0 ~ n-1
충돌이 없다고 가정
(충돌 : 두 항목이 테이블의 같은 곳에 저장될 때 일어남)
1. 키가 음이 아닌 정수일 때
실행 시간은 괜찮다.
2. 엄청난 메모리 낭비 gigantic memory hog
cf) memory hog : 1. 메모리 용량이 큰 프로그램 2. 메모리 용량이 큰 프로그램
해결책 : Solution
1. prehash 프리해시, 파이썬 해시
- maps keys to nonnegative integers
이론 답, 현실적 답
- in theory keys are finite & discrete
cf) heuristic (교수법·교육이) 체험적인
제한된 정보와 시간제약을 고려해 실무상 실현 가능한 해답이 필요한데 이것이 바로 휴리스틱 접근법이다. 휴리스틱 접근법은 가장 이상적인 방법을 구하는 것이 아니라 현실적으로 만족할 만한 수준의 해답을 찾는 것이다.
Heuristic 기법에서는 경험이나 직관을 사용하거나 노력을 기울여 시행착오를 거쳐 충분히 효율적인 해답이나 지식을 얻게 된다.
ex) hash('\OB') = hash('\O\OC') = 64
ideally: hash(x) = hash(y) <=> x=y
특정 객체를 정의시 __hash__ 메소드 구현, 만약 이 메소드를 구현하지 않으면 id 객체를 사용 id:해당 객체의 물리적인 주소
두 항목이 메모리의 같은 공간에 있지 않으니 id는 좋은 해시 함수
prehash는 시간이 지나도 바뀌면 안됨 -> __hash__ method 구현시 주의할 것
2. Reducing Space : hashing
핵심 개념 : 모든 가능한 키를 작은 정수의 집합으로 줄이는 것
hash table T index 0 ~ m-1
T(h(k_i)) = item
idea : m = O(n)
n : # of keys in dict
linear optimal
m개를 저장하고 싶을 때 2m or 3m만큼의 공간을 사용
그렇다면 h를 어떻게 찾을까 : 나머지 강의 시간 내용
비둘기를 위한 구멍의 수가 비둘기 수보다 작을 때 문제가 됨
: Collision 충돌
Chaining은 linked list로 table을 증가시켜나가는 방법
왜 좋은가?
Worst Case : O(n)
K의 모든 요소들이 하나의 item으로 들어가며 linked list로 들어가서 생기는 방식
그러나 실제로는 무작위성에 의해 잘 작동
후에 6.046을 듣는 것을 추천
Simple Uniform Hashing
cf) hash function는 전체 집합을 m개의 슬롯으로 줄여주는 것 m의 값을 알아야하지만 하나만 있는 것은 아님
확률적 가정 2개
1. Uniformity 균일성
공간에서 키를 골라 해시 테이블에 저장할 때 무작위적으로 선택, 대응
2. Independence 독립성
Analysis
- expected length of chain for n keys, m slots = n/m = alpha = load factor
O(1) Constant if m=O(n)
=> running time : O(1 + chain) = O(1 + alpha)
아직 풀리지 않은 점은 어떻게 h를 만들 것인가
테이블의 작은 슬롯 집합에 어떻게 대응할 것인가
3가지 해시 함수 제시(2개 흔히 보는 것, 1개 이론적으로 좋은 것)
앞의 2개는 이론적으로 좋지 않지만 이해를 도움
Hash Functions
1. Division method
h(k) = k mod m
m과 k가 공약수 일 때 좋지 않음
소수라면 2~10의 제곱근에 멀어지기 때문에 소수로 사용
2. Multiplication Method
$h(k) = [(a\times k) mod 2^w] \gg (w-r)$
w bit machine, w bits
ex) w bits (k) * 00101001(a)
일반적으로 결과값은 w bits의 2배
$2^w$는 오른쪽 비트를 이야기함
w-r만큼 오른쪽으로 shift
a : w 비트 중 하나 랜덤한 수
$m=2^r$
작동원리는 직관적으로 생각
곱셈을 통한 이동시키고 더하고 충돌시키며 랜덤화
이 때 중앙의 r bits만큼 더 잘섞임 -> 대부분의 경우 잘 작동
w 비트 중 가장 오른쪽 앞의 r 비트
a는 홀수
2의 제곱에 가까워서는 안된다. $2^{r-1} ~ 2^r$ 사이에 있어야함
이론적으로 좋지 않음
3. Universal hashing
h(k) = [(ak+b) mod p] mod m
a, b : random 0~ p-1
p : prime number > |U| : 전체 크기보다 큰 소수
for worst-case keys k1 != k2
$P_r{h(k_1) = h(k_2)} = {1\over m}$
최악의 경우 충돌 확률은 ${1\over m}$
기댓값의 선형성을 이용
기대되는 체인의 길이는 기대되는 키의 충돌 횟수의 적재율과 같다.
체인의 길이가 곧 예상 실행 시간
실행시간 적재율이 상수이면 해싱이 이론상 잘 작동하는 것
어디에 랜덤이 있을까
더 알고싶다면 6.046을 통해...
