10강. 해쉬 알고리즘(1)

[ 목차 ]

1. Direct-address table

2. Direct-address table의 주요 함수

3. Direct-address table의 공간복잡도

4. 해슁 Hashing

5. 해쉬테이블 수행시간 분석

6. 해쉬 테이블 충돌 문제

7. 체인을 이용한 충돌문제 해결법

8. 최악의 경우의 수행시간

9. 평균적 수행시간

10. 좋은 해쉬 함수는?

11. 해쉬 함수와 key

12. 나눗셈 방법

13. 효율적인 m의 선택 방법

 

1. Direct-address table

1) 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식

2) 중복되는 key는 없다고 가정

3) 시간복잡도가 굉장히 빠름

4) 검색, 삽입, 삭제가 빠르지만 실제 사용하는 공간이 낭비되는 단점

 

2. Direct-address table의 주요 함수

1) 각각의 수행시간은O(T)

 

3. Direct-address table의 공간복잡도

1) O([U])

2) 실제 공간 사용을 전체 공간으로 나눈 [K]/[U]를 적재율이라 함

3) 적재율이 낮다면 실제로 대부부의 공간은 낭비 

 

4. 해슁 Hashing

1) key k를 저장할 대 slot k에 저장하는 것이 아니라 slot h(k)에 저장

2) 이것을 key k가 slot h(k)로 해쉬되었다고 하며 h(k)를 key k의 해쉬값이라고 부름

3) 이때 h( )를 해쉬 함수라고 부름

  h : U -> {0, 1, ..., m-1}

4) k2, k5는 동일한 해쉬값으로 인해 같은 공간에 배치경우가 발생

 

5. 해쉬테이블 수행시간 분석

 

1) 이 때 slot은 항상 비어져 있으며 이 중 연결리스트로 구현되어있다고 가정하며 리스트의 길이를 I라고 생각

2) 공간낭비를 줄이면서 시간복잡도를 낮추기 위해 사용하지만 충돌문제가 있으며 이를 위한 chained hash table은 시간을 느리게 할 수 있음

 

6. 해쉬 테이블 충돌 문제

1) 두 개의 key가 동일한 hash값을 갖는 경우 충돌이 발생했다고 함

2) 충돌을 피하는 방법은 충돌이 적은 좋은 해쉬 함수를 쓰거나 체이닝 방법을 사용

3) 하지만 테이블의 크기가 해쉬 함수의 치역 영역보다 크다면 [U]>m 충돌을 피하는 것은 매우 어려움

 

7. 체인을 이용한 충돌문제 해결법

1) 중복되는 key 값이 있을 경우 해당 슬롯을 연결리스트로 저장

2) 시간 복잡도의 문제가 발생할 수 있음

 

8. 최악의 경우의 수행시간

1) 모든 key 값 k가 하나의 slot으로 해슁도는 경우는 길이가 n인 이줄 연결 리스크가 생성

2) 해쉬 테이블이 아닌 일반적인 리스트에 저장하는 것과 성능이 동일

 

9. 평균적 수행시간

1) 이때 a는 적재율이라고 부르며 a=n/m으로 계산

2) n은 테이블의 원소 개수이고 m은 slot의 수

 

10. 좋은 해쉬 함수는?

1) simple uniform hashing을 만족

  1] 각각의 key는 중복 없이 n개의 sloy으로 동일한 확률로 해쉬(simple)

  2] 각각의 key는 다른 key값의 해쉬값과 관계엾이 해쉬(uniformly)

2) 모든 값이 골고루 나오는 것

  1] m개의 slot이 있으면 중복 없이 확률적으로 m개의 slot에 골고루 나누어지는 것이 좋음(simple uniform hashing)

 

11. 해쉬 함수와 key

1 해쉬 함수에서는 key값을 자연수로 가정 즉, N={0, 1, 2, ...}

2) 만약 key가 자연수가 아닌 형태라면 자연수 형태로 변형하여 사용

3) pt가 입력되었다면 p=112, t=116이므로 이를 숫자값으로 바꿔 계산

 

12. 나눗셈 방법

1) 해쉬 함수로 나눗셈을 이용하는 방법으로 키값 k를 m으로 나누고 나머지를 이용

2) Modular 연산을 이용

3) h(k) = k mod m

  ex. m=12, k=100  ->  h(k) = 100 mod 12 = 4

 

13. 효율적인 m의 선택 방법

1)  m = 2의 n승일 피하는 것이 좋음

2) 1)의 경우 해쉬함수 h(k)는 키 k의 하위 n비트가 됨

3)해쉬 함수가 key 값 전체에 따라 바뀌지 않고 하위p 비트에만 영향

4) 하위 p비트가 고루 나온다면 나쁜 선택은 아니나 그런 경우가 적기 때문에 피하는 것이 좋음

5) 2의 n승에 가깝지 않은 소수를 선택하는 것이 좋음