기말준비-해싱(Hashing)

 기존 검색 시간은 O(lg N) 인데, 이것을 O(1)로 낮추기 위한 시도

   -> 배열의 크기, 데이터 량에 관계 없이 검색의 시간이 동일하게 함.

  방법  : 매우 큰 공간을 가진 Hash table를 만든다. 이때 hash table의 사이즈 M은 소수이다. (Prime number)

  공간낭비가 커 효율이 떨어지지만 긴급한 검색의 경우 필요해 만들어짐.

 

 1. 배경

   data K가 저장될 위치를 data K를 통해 구하는 방식

  h(K) : Hash function, Table[h(k)] = k로 저장

 

 2. 문제점

  2-1) 충돌 (Collision)

   서로 다른 데이터 X, Y에서, h(X) == h(Y)가 돼버리는 경우  ( 서로 다른 데이터가 같은 해시를 지님 )

  2-2) 군집화 (Clustering)

   데이터가 해시 테이블에 골고루 분산되지 않고 부분적으로 뭉치게 되는 현상

 

 3. 해시 펑션 (Hash Function)

  문제점 2개를 최대한 해결할 수 있는 해시 펑션을 만들어야함.

  일반형 : h(x) = f(x)mod M

   - f(x)는 데이터 X를 임의 가공하여 정수로 변환시키는 함수 (Universal Hashing, etc.)

   - mod M은 f(x)를 M으로 나눈 나머지값을 구함.

 

4. 충돌 해결법

 데이터 K를 저장하려는 위치 h(K)에 이미 다른 데이터가 저장되어 있는 경우

 4-1) 선형 조사법 (Linear probing)

  h(K)에 1씩 더하면서 비어있는 공간을 찾으면 입력한다.

  (h(K)+1) > M이 될 수 있으므로, (h(K)+1)mod M의 형태로 사용함.

   장점 : 매우 간단함

   단점 : 잦은 충돌 시 군집화 될 가능성이 높음, 

           연속적으로 저장된 data가 일부 삭제될 시 그 밑의 데이터는 검색되지 않음.

            -> 각 항목이 (사용), (미사용), (삭제됨) 으로 구분되면 검색 가능

 

4-2) 2차 조사법 (Quadratic Probing)

 (h(K)+(i^2))mod M의 형태로 i를 늘려가며 빈 공간을 찾아서 입력한다.

 장점 : 1차 군집화는 감소한다.

 단점 : 2차 군집화의 가능성이 있다. -> i를 늘리는 방식의 변화는 군집화 해결에 큰 의미 없음.

 

4-3) Double Hashing

 2차 군집화의 감소를 위해, size M보다 약간 작은 소수 C를 이용한 g(x)를 추가로 사용한다.

  -> ( h(k) + i*g )mod M  { g = (g(x)mod C) }

 장단점 : 군집화는 거의 없지만, 완벽하지는 않다.

 

4-4)  Chaining

 Hash table의 다른 장소로 보내는 것이 아닌, 충돌이 발생한 장소를 Linked List로 구성해서 같은 자리에 여러개 저장한다.

 

 

 5. 성능 분석

복잡해서 이 수업에서는 다루지 않는다고함.

삽입/삭제는 검색이 선행 됨 > 충돌 미발생 : O(1) / 충돌 발생 : O(N)

적재 밀도 (Loading Density) : N(데이터의 수) / M(배열의 크기)

 ex) Linear probing : 성공확률 = 1/2[ 1 + 1/(1-a) ], a < 0.1 / 실패 : 1/2[ 1 + 1/(1-a)^2 ]

 몰?루