제 8 장 해싱.

Presentation on theme: "제 8 장 해싱."— Presentation transcript:

1 제 8 장 해싱

2 개요 ADT 사전(dictionary) 해싱(Hashing) 정적 해싱(Static hashing)
동적 해싱(Dynamic hashing)

3 정적 해싱 (1) 해시 테이블 (1) 사전 쌍들이 해시 테이블 ht 에 저장
ht[0], … , ht[b-1], 즉, b개의 버킷(bucket)으로 분할됨 한 버킷은 s개의 슬롯(slot)으로 구성됨 한 슬롯에는 하나의 사전 쌍이 저장됨 키 값이 k인 한 쌍의 주소 또는 위치는 해시 함수 h에 의해 결정됨 해시 함수는 키 값을 버킷으로 사상시킴 h(k) : k의 해시 또는 홈 주소(home address) 사전 쌍들은 이상적인 조건 하에서는 모두 해당 홈 버킷(home bucket)에 저장됨

4 정적 해싱 (2) 해시 테이블 (2) 정의 키 밀도 n/T는 매우 작고 버킷 수 b도 T보다 작게 됨
해시 테이블의 키 밀도(key density)는 n/T 임 해시 테이블의 적재 밀도(loading density)는 α = n/(sb) 임 n : 테이블에 있는 쌍의 수 T : 가능한 키의 총 개수 키 밀도 n/T는 매우 작고 버킷 수 b도 T보다 작게 됨 k1와 k2에 대해 h(k1) = h(k2) 인 경우 k1과 k2를 h에 대한 동거자(synonym)라 함

5 정적 해싱 (3) 해시 테이블 (3) 이상적인 조건 하에서, 사전 쌍들은 모두 해당 홈 버킷에 저장됨
이상적인 조건 하에서, 사전 쌍들은 모두 해당 홈 버킷에 저장됨 오버플로(overflow) 새로운 사전 쌍을 삽입하려고 할 때, 홈 버킷이 차 있는 상태일 경우 충돌(collision) 새로운 쌍의 삽입 시 홈 버킷에 비어 있는 자리가 없을 경우

6 정적 해싱 (4) 해시 테이블 (4) b=26개의 버킷과 s=2인 해시 테이블 n=10개, α =10/52 = 0.19
0부터 25까지의 숫자로 사상시킴 GA와 G가 같은 버킷에 있음 A와 A2가 같은 버킷에 있음 A1을 테이블 어디에 위치시켜야 되는가?

7 정적 해싱 (5) 해시 테이블 (5) 오버플로가 발생하지 않을 경우 해싱 기법 삽입, 삭제, 탐색 시간
사전의 엔트리 수인 n에 무관 해시 함수의 계산 시간과 한 버킷을 탐색하는데 소요되는 시간에만 좌우됨 버킷 크기 s는 작기 때문에, 버킷 내에서 탐색을 위해 순차 탐색 기법을 사용할 수 있음 해싱 기법 해시 함수 h를 사용하여 키를 해시 테이블 버킷에 사상시킴 해시 함수는 충돌 수 최소화하도록 선택해야 함 오버플로 처리하는 기법이 필요함

8 정적 해싱 (6) 해시 함수 (1) 키를 해시 테이블 내의 버킷으로 사상시킴 계산이 쉽고 충돌이 적어야 함
균일 해시 함수(uniform hash function) h(k) = i 가 될 확률은 모든 버킷 i에 대해 i/b이 됨 k = 키 공간에서 임의로 선택된 키 b개의 버킷 각각에 임의의 k가 대응될 확률은 모두 같게 됨 다양한 종류의 균일 해시 함수가 사용됨 일부는 산술적인 연산을 통해 홈 버킷을 계산하지만, 많은 응용에서 산술적인 연산을 할 수 없는 경우도 있음 먼저 키를 정수와 같이 산술적인 연산이 가능한 데이터 타입으로 변환한 뒤에 연산을 수행함

9 정적 해싱 (7) 해시 함수 (2) 제산(division) 함수 실제로 가장 많이 쓰이는 해시 함수
키 값이 음이 아닌 정수라고 가정 홈 버킷은 모드(%) 연산자에 의해 결정 키 k를 정해진 수 D로 나눈 나머지를 k의 홈 버킷으로 사용 h(k) = k%D 버킷 주소의 범위 : 0 ~(D-1) 최소 b = D개의 버킷이 있어야 함 D의 선택이 오보플로 발생 수에 영향 미침 D의 최소 소인수의 크기가 증가하면 편중 정도는 감수함 D가 홀수가 되도록 제한하고 b=D 배열의 크기를 두 배로 만들면 버킷의 수가 b에서 2b+1로 증가됨

10 정적 해싱 (8) 해시 함수 (3) 중간 제곱(mid-square) 함수
키를 제곱한 후에 버킷 주소를 얻기 위해 그 결과의 중간에 있는 적절한 수의 비트를 취해서 홈 버킷을 정함 키는 정수라고 가정함 제곱 수의 중간 비트는 그 키의 모든 비트에 의존하므로 서로 다른 키들은 서로 다른 해시 주소를 갖게 될 확률이 높게 됨 버킷 주소를 얻기 위해 사용되는 비트의 수는 테이블 크기에 달려 있음 r개의 비트가 사용되면 각 값들의 범위는 0에서 2r-1까지가 됨 해시 테이블의 크기는 2의 제곱이 되게 선정

11 정적 해싱 (9) 해시 함수 (4) 접지(folding) 함수
숫자로 된 키 k를 몇 부분으로 나누는데, 마지막 부분을 제외하고는 모두 길이가 같음 각 부분들을 서로 더하여 k에 대한 해시 주소 만듦 두 가지 덧셈 방식 이동 접지 (shift folding) 마지막을 제외한 모든 부분들을 이동시킴 최하위 비트가 마지막 부분의 자리와 일치하도록 맞춤 서로 다른 부분들을 더하여 h(k)를 얻음 경계 접지 (folding at the boundaries) 키의 각 부분들을 경계에서 겹치게 함 같은 자리에 위치한 수들을 더하여 h(k)를 얻음

12 정적 해싱 (10) 해시 함수 (5) 접지 함수 예제 k = 12320324111220, 길이가 세 자리인 부분들로 나눈다.
P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20 이동 접지 방법 사용: h(k) = = = 699 경계 접지 방법 사용: 먼저 P2와 P4를 역순으로 하여 302와 211을 각각 구한 후 다섯 개의 부분을 더하여 h(k) = = 897을 구함

13 정적 해싱 (11) 해시 함수 (6) 숫자 분석 함수(digital analysis)
정적 파일(static file)과 같은 경우에 유용함 각 키를 어떤 기수(radix) r을 이용해 하나의 숫자로 바꿈 이 기수를 이용해 각 키의 숫자들을 검사함 가장 편향된(skewed) 분산을 가진 숫자 생략 남은 숫자만으로 해시 테이블 주소를 결정함

14 정적 해싱 (12) 해시 함수 (7) 키를 정수로 변환 키를 음이 아닌 정수로 변환함 유일한 정수로 변환시킬 필요 없음
스트링을 정수로 변환하기 16-비트 정수로 사상시킴

15 정적 해싱 (13) 해시 함수 (8) 키를 정수로 변환 (계속)
C++ STL은 T타입의 어떤 개체를 음이 아닌 정수 size_t로 변환시키는 STL 템플릿 클래스 hash<T>를 특별히 제공

16 정적 해싱 (14) - 안전 해시 함수 (1) 컴퓨터 보안 분야의 여러 응용에 사용되는 해시 함수
(ex) 메시지 인증(message authentication) 메시지 M이 보안되어 있지 않은 채널을 통해 A에서 B로 전송될 때, B에서 받은 메시지가 위조된 것이 아니라 A에서 전송된 원본 메시지라고 신뢰할 수 있는 방법 해시 함수 h를 이용해 메시지 M의 해싱 값 h(M)을 더 안전한 경로로 보냄 약한 충돌 저항(weak collision resistance) M과 h에 대해 잘 숙지하고 있는 악의 있는 사용자가 M의 동거자를 쉽게 찾지 못하게 하는 해시 함수를 사용해야 하는 특성

17 정적 해싱 (15) - 안전 해시 함수 (2) 단방향 특성(one-way property)
h(k) =c 를 만족하는 c가 주어졌을 때, k를 찾는 것을 계산적으로 어렵게 만드는 것 강한 충돌 저항(strong collision resistance) h(x) = h(y)를 만족시키는 (x,y) 쌍을 계산적으로 찾기 어렵게 만드는 것 암호화 해시 함수의 추가적인 특징 보안 외에도 실용적으로 사용될 수 있도록 가지는 특성들 (1) h는 데이타 블록 크기 상관없이 적용 가능해야 함 (2) h는 고정 길이의 해시 코드를 만들어야 함 (3) h(k)는 어떤 k가 주어져도 계산이 비교적 쉬워서 하드웨어와 소프트웨어의 구현이 실용적이어야 함

18 정적 해싱 (16) - 안전 해시 함수 (3) 보안 해시 알고리즘(SHA : Secure Hash Algorithm)
미국 국립표준기술연구소(NIST)에서 처음 개발함 입력 : 264 비트보다 적은 길이의 메시지 가능 출력 : 160 비트 길이의 코드 1단계 : 어떤 정수 q에 대해 메시지의 길이가 q*512 비트가 되도록 전처리(preprocess)한다. 이 때 메시지의 뒤에 0으로 채워 넣을 수 있다. 2단계 : 160-비트의 출력 버퍼, OB를 초기화한다. 이 버퍼는 5개의 32-비트 레지스터 A, B, C, D, E로 구성되는데, 여기서 A= , B=efcdab89, C= 98bdcfe, D= , E=c3d2e1f0 이다(이 값들은 16진수이다). 3단계 : for(int i=1; i<=q; i++){ Bi = 메시지의 512 비트로 이루어진 i번째 블록 OB = F(OB, Bi); } 4단계 : OB를 출력한다. SHA 알고리즘

19 정적 해싱 (17) - 안전 해시 함수 (4)

20 정적 해싱 (18) – 오버플로 처리 (1) 오버플로를 처리하는 방법 개방 주소법(open addressing)
선형 조사법(linear probing) 이차 조사법(quadratic probing) 재해싱(rehashing) 임의 조사법(random probing) 체인법 (chaining)

21 정적 해싱 (19) – 오버플로 처리 (2) 선형 조사법 (1) 키 값이 k인 새로운 쌍 하나를 삽입할 때 A 1 A2 2
ht[h(k)+i]%b의 순서에 따라 해시 테이블 버킷 검색 h : 해시 함수, b : 버킷의 수, 0<= i <= b – 1 다 채워지지 않은 버킷을 만나면 검색이 끝나고 새로운 쌍이 그 버킷으로 삽입됨 빈자리가 있는 버킷이 없다면 해시 테이블이 만원인 것 테이블 크기를 늘려야 함 적재 밀도 = 0.75와 같은 경계 값을 넘을 때 테이블 크기 늘림 해시 테이블의 크기를 다시 정할 때 해시 함수 바꿔야 함 모든 사전 엔트리들은 새로 커진 테이블에 다시 사상되어야 함 1 2 3 4 5 6 7 8 9 10 11 12 25 A A2 A1 D A3 A4 GA G ZA E L . Z ≈ ≈ 선형 조사법에 의한 해시 테이블 (26개의 버킷, 버킷당 하나의 슬롯)

22 정적 해싱 (20) – 오버플로 처리 (3) 선형 조사법 (2)
S=1, 선형 조사법으로 오버플로 처리하는 경우, 키 k를 해시 테이블에서 탐색하는 과정 (1) h(x) 계산 (2) 다음과 같은 경우 중 하나가 발생할 때까지 ht[h(k)], ht[(h(k)+1)%b], … , ht[(h(k)j)%b] 순서로 해시 테이블 버킷을 조사 버킷 ht[(h(k)+j)%b]에 값이 k인 키 쌍이 있는 경우  원하는 쌍이 발견되었음 ht[h(k)+j]가 비어 있는 경우  K는 테이블에 없음 시작 위치 ht[h(k)]로 돌아온 경우  테이블은 만원이고 k는 테이블에 없음

23 정적 해싱 (21) – 오버플로 처리 (4) 선형 조사법 (3) 선형 조사법
template <class K, class E> pair<K,E>* LinearProbing <K,E>::Get(const K&k) {// 선형 조사법 해싱테이블 ht(각 버킷은 한 슬롯만 가짐)에서 k를 탐색. // 이 키를 가진 쌍을 발견하면, 그 쌍을 가리키는 포인터를 반환. // 그렇지 않으면 0을 반환. int i = h(k); // 홈 버킷 int j; for(j = i; ht[k] && ht[j] → first != k;) { j = (j+1) % b; // 테이블을 원형으로 간주 if(j == i) return 0; // 시작점으로 복귀 } if (ht[j] → first == k) return ht[j]; return 0; 선형 조사법

24 정적 해싱 (22) – 오버플로 처리 (5) 선형 조사법 (4) 선형 조사법으로 오버플로를 해결하는 경우
키들이 클러스터(cluster)되는 경향이 있어 탐색 시간 증가 균등 해시 함수와 함께 선형 조사법을 사용할 경우 α가 적재 밀도일 때 키를 찾기 위한 평균 키 비교 횟수의 기대 값 (2-α)/(2-2α) 이차 조사법(quadratic probing) 클러스터의 크기를 줄이기 위해서 이용 선형 조사법에서는 b가 테이블에 있는 버킷의 수라고 할 때 (h(k)+i)%b, 1≤i≤b-1인 버킷을 찾는 반면 이차 조사법에서는 i의 이차 함수가 증분으로 사용됨 0≤i≤(b-1)/2에 대해 h(k), (h(k)+i2) % b, (h(k)-i2) % b를 검사하는 방법으로 탐색을 수행 b가 4j+3(j는 정수)인 형태의 소수라면 이차 조사법에서는 테이블의 모든 버킷을 조사하면 됨

25 정적 해싱 (23) – 오버플로 처리 (6) 선형 조사법 (5) 클러스터 확대를 줄이기 위한 다른 방법
재해싱(rehashing) 여러 개의 해시 함수 h1, h2, ..., hm을 사용하는 방법 버킷 hi(k) (0≤i≤m)를 순서대로 검사 임의 조사법(random probing) 형태가 4j+3인 몇 가지 소수들

26 정적 해싱 (24) – 오버플로 처리 (7) 선형 조사법과 같은 방법들이 효율이 좋지 않은 이유 체인법
키를 탐색할 때 서로 다른 해시 값을 가진 키와 비교를 해야하기 때문 체인법 체인을 사용할 때 ChainNode <pair <K, E>>* 타입의 배열 ht[0:b-1]을 이용 ht[i]는 버킷 i에 연결된 체인 중 첫 번째 노드를 가리킴 template <class K, class E> pair<K,E>* Chaining <K,E>::Get(const K&k) {// 체인으로 연결된 해시 테이블 ht에서 k를 탐색 // 이 키를 가진 쌍을 발견하면, 그 쌍을 가리키는 포인터를 반환 // 그렇지 않으면 0을 반환 int i = h(k); // 홈 버킷 // ht[j]에서 시작하는 체인을 탐색 for(ChainNode <pair <K, E>>* current = ht[i]; current; current = current -> link) if(current->data.first == k) return &current->data; return 0; } 체인 검색

27 정적 해싱 (25) – 오버플로 처리 (8)

28 정적 해싱 (26) – 오버플로 처리 (9) 체인법 (계속) 체인법을 균일 해시 함수와 함께 사용할 경우
검색이 성공했을 경우 키의 비교 횟수 기대치는 α가 적재 밀도이고 n/b(b는 버킷의 수)일 때 평균적으로 약 1 + α/2임 해시 테이블의 성능은 오버플로를 처리하는 방식에만 좌우됨 키가 편중적으로 선택되어지는 경향이 있음 해시 함수에 따라 해시 테이블의 성능도 달라짐 체인법과 함께 제산 함수를 사용하면 가장 좋은 성능 가짐 성공적인 탐색을 위해 필요한 최악의 경우에 비교 횟수 O(n) 체인이 아니라 균형 탐색 트리에 저장하면 O(log n)

29 정적 해싱 (27) – 오버플로 처리 (10) 오버플로 기법의 이론적 평가 (1) 균형 트리와 같은 상용 기법보다 성능이 우수
최악의 경우에는 해싱의 성능 좋지 않음 n개의 키를 가진 해시 테이블에서의 삽입, 탐색에 O(n) 시간이 걸릴 수도 있음 체인 방법의 예상 성능에 대한 확률적 분석 ht[0:b-1] : 한 개의 슬롯으로 된 버킷 b개를 가진 해시테이블 h : 치역이 [0,b-1]인 균일 해시 함수 n개의 키 k1, k2, ...., kn 이 해시 테이블에 저장 h(k1), h(k2), ... , h(kn)과 같은 bn가지의 서로 다른 해시 순서가 있을 것 이들이 균등한 발생 확률을 가진다고 가정 Sn : 임의로 선택된 ki(1≤i≤n)의 주소 확인에 필요한 예상 키 비교 횟수 j번째 키인 kj를 찾는 데 필요한 평균 비교 횟수 균등한 확률로 선택되는 j(1≤i≤n)와 bn가지 해시 순서에 따른 비교 횟수를 평균한 값 Un : 해시 테이블에 없는 키를 찾는데 필요한 예상 비교 횟수

30 정적 해싱 (28) – 오버플로 처리 (11) 오버플로 기법의 이론적 평가 (2)
체인 방법의 예상 성능에 대한 확률적 분석 (계속) (정리 8.1) a = n/b가 균일 해시 함수를 사용한 해시 테이블의 적재 밀도라 하자. (1) 선형 개발 주소법에 대해 Un = ½[1 + 1/(1-a)2] Sn = ½[1 + 1/(1-a)] (2) 재해싱 및 임의 조사법과 이차 조사법에 대해 Un ≈ 1/(1-a) Sn ≈ –[1/a]loge(1-a) (3) 체인법에 대해 Un ≈ a Sn ≈ 1 + a/2        

31 정적 해싱 (29) – 오버플로 처리 (12) 오버플로 기법의 이론적 평가 (3)
체인 방법의 예상 성능에 대한 확률적 분석 (계속) (증명) 검색하고자 하는 키 k가 h(k)=i이고 체인 i가 q개의 노드를 가졌을 경우 k가 체인에 없으면 q번의 비교가 필요 k가 그 체인에서 j번째 노드에 있다면(1≤j≤q), j번의 비교가 필요   n개의 키가 b개의 체인에 일정하게 분산되어 있을 경우 각 체인에 있는 키 개수의 기대값은 n/b=α Un은 체인에서의 예상 키 수 이므로 Un=α i번째의 키 ki가 테이블에 들어갈 때 체인에서의 예상 키 수 : (i-1)/b ∴ n개의 모든 키가 저장된 후에 ki를 탐색하는 데 필요한 예상 비교 횟수 : 1 + (i –1)/b 결과

32 동적 해싱 동적 해싱(dynamic hashing)의 배경 확장성 해싱(extendible hashing)이라고도 불림
재조정을 한번 할 때마다 오직 하나의 버킷 안에 있는 엔트리들에 대해서만 홈 버킷을 변경하게 하여 재조정 시간을 줄임 하나의 연산에 대해 좋은 성능을 유지할 수 있게 함 해시 함수의 예

33 디렉터리를 이용한 동적 해싱 (1) 디렉터리(directory)를 이용한 동적 해싱
디렉터리의 크기 : h(k)의 비트 수에 좌우됨 디렉터리 깊이(directory depth) 디렉터리를 인덱싱하는 h(k)의 비트 수 t : 디렉터리 깊이, 2t : 디렉터리 크기 (ex) h(k,2)를 사용하여 인덱싱  디렉터리의 크기 = 22=4 h(k,5) 를 사용하여 인덱싱  디렉터리의 크기 = 25=32 버킷 수 < 디렉터리 크기

34 디렉터리를 이용한 동적 해싱 (2) 키 A0, B0, A1, B1, C2, C3을 포함하고 있는 동적 해시 테이블 (1)
깊이가 2인 디렉터리를 사용 각 버킷에는 두 개의 슬롯 (색칠된 것 – 디렉터리 나머지 – 버킷들)

35 디렉터리를 이용한 동적 해싱 (3) 키 A0, B0, A1, B1, C2, C3을 포함하고 있는 동적 해시 테이블 (계속)
키 k를 탐색하려면, t가 디렉터리 깊이일 때 d[h(k,t)]가 가리키는 버킷을 탐색해보기만 하면 됨 오버플로 발생 시 해결 방법 오버플로가 된 버킷의 모든 키에 대해 h(k,u)가 같지 않게 하는 최하위 비트 u를 정함  디렉터리 크기는 증가, 버킷 개수는 그대로 임 디렉터리 크기 재조정 후 h(k,u)를 사용하여 오버플로가 된 버킷을 분할 현재 디렉터리 깊이가 u와 같거나 클 때 분할된 버킷을 가리키는 다른 포인터들 역시 새로운 버킷을 가리키도록 갱신되어야 함 동적 해싱은 배열을 두 배로 만드는 방법을 사용하지만 정적 해싱에서 배열을 두 배로 만드는 것보다 시간이 적게 걸림 오버플로가 된 버킷에 있는 엔트리들만 재해싱하면 되므로

36 디렉터리 없는 동적 해싱 (1) 버킷 포인터의 디렉터리 d 대신 버킷의 배열인 ht를 사용
배열의 크기는 매우 커서 동적으로 늘릴 필요가 없다고 가정 q와 r이라는 변수 (0≤q<2r)를 두어 활성화된 버킷 (active bucket) 에 대한 정보를 얻어냄 항상 0부터 2r+q-1까지의 버킷만 활성화 됨 각 활성 버킷은 버킷 체인의 시작이 됨 오버플로 버킷(overflow bucket) : 체인의 나머지 버킷들 2r부터 2r+q-1까지의 활성버킷 뿐만 아니라 0부터 q-1까지의 활성 버킷은 h(k, r+1)을 이용하여 인덱싱 나머지 활성 버킷들은 h(k,r)을 이용하여 인덱싱 각 사전쌍들은 활성 버킷이거나 오버플로 버킷

37 디렉터리 없는 동적 해싱 (2) r=2이고 q=0일 때 디렉터리가 없는 해시 테이블 ht
그림 8.6의 해시 함수 사용, 활성 버킷 개수 = 4 각 활성 버킷에는 두 개의 슬롯

38 블룸 필터 (1) 응용 – 차등 파일 (1) 인덱싱된 화일(indexed file)을 관리하는 응용
하나의 인덱스와 하나의 키가 있을 때 밀집 인덱스(dense index)이고, 화일의 갱신이 허용된다고 가정 인덱스 화일의 백업 사본을 유지하는 것이 필요 마스터 인덱스(master index), 마스터 화일(master file) – 인덱스 파일의 작업 사본 트랜잭션 로그 (transaction log) 장애 회복을 위해 필요 백업 사본과 백업 사본 생성 이후에 만들어지는 모든 갱신 로그 장애 회복을 위해 백업 사본과 트랜잭션 로그를 처리하여 장애 당시 작업 사본의 인덱스 화일을 재생해야 함 ∴회복 시간 – 백업 인덱스와 화일 크기, 트랜잭션 로그 크기의 함수가 됨 차등 화일(differential file) 인덱스가 아니라 화일만 클 경우 별도의 화일에 갱신된 레코드를 저장함으로써 복구 시간 줄일 수 있음

39 블룸 필터 (2) 응용 – 차등 파일 (2)

40 블룸 필터 (3) 응용 – 차등 파일 (3) 차등 화일을 사용할 때, 백업 파일은 마스터 화일의 복사본
인덱스, 화일, 트랜잭션 로그 상대적으로 작음 빈번한 백업 가능함 한 화일 연산을 수행할 때 필요한 디스크 접근 횟수에는 영향을 주지 않음 인덱스, 화일 클 경우 차등 화일, 차등 인덱스(differential index)로 문제 해결함

41 블룸 필터 (4) 블룸 필터 설계 블룸 필터(Bloom filter) 차등 인덱스 안에 모든 키의 리스트를 유지함
내부 메모리에 상주하여 ‘차등 인덱스에 키가 있는가?’와 같은 유형의 질의를 허용하는 장치 차등 인덱스 안에 모든 키의 리스트를 유지함 위와 같은 유형의 질의에 정확하게 응답하지 않음 ‘maybe’와 ‘no’중에 하나로 응답 ‘no’ 탐색키가 차등 인덱스에 있지 않다는 것을 보장 ‘maybe’ 차등 인덱스를 탐색

42 블룸 필터 (5) 필터 오류가 될 확률 근사 값을 사용하면 큰 값 x에 대해
P(u) = (1-1/n)u(1-(1-1/m)uh)h 근사 값을 사용하면  (1-1/x)q ~ e-q/x 큰 값 x에 대해 P(u) ~ e-u/n(1-e-uh/m)h h에 대해서 P(u)를 미분하고 결과를 0으로 지정하면 h = (loge2)m/u ~ 0.693m/u