해싱 (2)

msung99·2022년 5월 19일
0

linear probing 의 find(탐색) 연산

  • 해싱을 linear probing 으로 구현했을때 insert 연산은 지난시간에 살펴봤다. 이번엔 find 연산을 살펴보자.

Algorithm find(k)
  i <- h(k)    // i의 초기값으로 k에 해시함수를 적용시켜 얻은 hash value 인 h(k) 를 할당
  p <- 0       // probing 총 횟수
  repeat
    c <- A[i]            // 배열에서 현재 탐색하는 인덱스에 들어있는 값을 c 에 할당
    if c = Ø              // 원하는 key 값 k를 못찾은 채로 빈 인덱스를 발견한 경우
      return null
    else if c.key() = k   // 원하는 key 값 k 를 찾게된 경우
      return c.value()    
    else   //  해당 인덱스에 누군가 담겨있는 경우
      i <- (i+1) mod N   // probing 을 계속 진행하기 위해 옆칸으로 이동 
      p <- p + 1     // probing 총 횟수 증가 
  until p = N        //  probing 을 최대 N번 진행  (반복문 중간에 원하는 key 값을 찾아냈거나, 또는 빈 인덱스를 만나게 되면 도중에 probing 탐색을 중단한다. 즉 반복문을 도중에 종료)
  return null  // 최악의 경우 => 배열의 모든 인덱스에 대해 싹다 뒤져봤지만 (= N개의 원소에 대해 모두 탐색을 진행했지만 ), 원하는 key 값을 못찾은 경우는 배열에 원하는 key 값이 없다고 판단하게 되어서 null 을 리턴
  1. k 에 해시함수를 적용해 hash value 값인 h(k)로 바꿔준다.

  2. k에 해당하는 key 를 찾거나,

  3. 못 찾은채로 비어있는 인덱스를 발견하거나,
    (있어야 할 곳에 아무것도 없는 상황)

  4. 못 찾은채로 이동을 N번 반복했을 때 중단된다.
    (모두 다 차있는 상황)

=> 마지막 경우를 위해 변수 p = 0 을 설정하고
이동할때마다 1씩 추가해준다.


  • "if c = Ø" 의 의미
    • 왜 빈 인덱스를 만나면 찾고자 했던 key 가 배열에 없는 것일까?

  • 위와 같은 배열에 대해 find(101) 을 하는 경우를 생각해보자.
    이떄 해시함수는 "mod 10" 이 들어갔다고 가정한다.

그러면 key 101 은 1 로 변환되고, 인덱스 1부터 시작해서 순차적으로 probing 을 수행할 것이다.

인덱스 4까지 진행을 하다 인덱스 5가 빈 인덱스라는 것은 곧 탐색에 실패했다는 것인데 왜 그럴까?

=> 배열 안에서 인덱스 1에 있는 애들과 다닥다닥 연속으로 붙어있는 인덱스에 있는 key 값들은 곧 hash value 가 1인 key 들의 후보(?) 명단에 올라와 있는 애들이라 할 수 있다.

즉, 그룹 A에 있는 key 들에 대해 탐색을 진행하다가 결국 빈 인덱스를 만나게되면, 우리가 찾고자 하는 key 101은 hash value 가 1인 key 들의 후보 명단 그룹 A에 존재하지 않는 것으로 판명되는 것이다.


데이터의 key 가 k가 아닌 경우

  • 해당 배열의 인덱스에 이미 누군가가 공간을 차지하고 있다.

  • 공간을 차지중인 그 데이터가 가진 key 의 hash value 값이 나랑 같을수도 있고,
    더 앞쪽이였는데 probe 에 의해서 probing 하면서 더 뒤쪽으로 왔을수도 있다.

=> 그래서 mod N 을 진행하는 것임.
배열 인덱스 끝까지 도달했다가 다시 맨앞(=인덱스 0) 부터 탐색을 진행

  • 따라서 k 가 나타날 떄까지 계속 선형적으로 한칸씩 이동하며 probing 을 진행해야 한다.

  • linear probing 의 배열은 환형배열이라 생각하면 좋다.


Linear Probing 의 삭제

그냥 삭제하지 않고, AVAILABLE 표식을 남기고 삭제한다.

  • 삭제를 위해 탐색 알고리즘 find 를 사용하는데, 이는 빈 인덱스를 만나면 멈추도록 설계되어있다.

아래와 같은 배열에서 우선 31을 삭제한 후

아래처럼 배열에서 31이 삭제된 후에 key 73 을 탐색하면

73을 찾지 못한채 비어있는 10번 인덱스를 만나게 되므로 배열에 73이 있는데도 73을 발견하지 못한채 종료되고 만다.

이처럼 단순 삭제로는 삭제 인전에 삽입된 데이터에 도달하지 못한다는 문제가 발새한다.

때문에 비어있는 인덱스가 처음부터 비어있었는지,
삭제되어 비어있는 상태인지 구분하기 위한 장치가 필요하다.

AVAILABLE

  • 빈 인덱스가 원래 처음부터 비어 있었던건지, 아니면 누군가 있던 인덱스였는데 삭제되어 비어있게 된 상태여서 insert 가 가능한 인덱스인지 구분해주는 객체

  • 데이터 삭제 후, 비어있는 자리에 AVAILABLE 객체를 저장한다.

  • 삽입시 데이터를 AVAILABLE 객체 위에 덮어씌우고, 탐색과 삭제를 할때는 그 자리를 건너뛴다.

따라서 AVAILABLE 은 삽입 연산시에는 비어있다고 인식되서 그냥 데이터를 삽입하면 되고, 탐색과 삭제 연산 시에는 빈 상태가 무시되고 (= 빈 상태가 아니라고 인식되고 ) 다음 인덱스로 넘어간다.


Double Hashing (이중 해싱)

linear probing 은 "1칸" 만큼 이동해서 탐색하는 반면,
Double Hashing 은 " 2차 해시 함수의 결과값" 만큼 이동해서 탐색하는 것이다.

  • linear probing 에 비해 분산이 잘 된다!

    • linear probing 의 뭉침 현상을 해결!!
      => linear probing에 비해 총 probe 횟수가 줄어듬. 즉 수행능력 좋다.
  • 결국 선형 탐사 말고도 더블 해싱을 이용해서도 충돌의 문제를 해결 가능

  • key 마다 다음 key 가 있을 수 있는 실제 자리가 멀어졌다 가까워졌다함.

  • 2차 해시값 만큼의 인덱스를 더해서 본다.


j번째로 탐색하게 되는 인덱스 : ( i + j x d(k) ) mod N = h( h(k) + j x d(k) )

i : 1차해시함수 결과값이자, 탐색을 시작하는 첫번째 인덱스
d(k) : 2차해시함수의 결과값이자, 다음 탐사 과정(probing) 을 진행할 때 기존 인덱스에서 몇 칸을 이동하는지의 수치.
=> j번째로 탐색하게 되는 인덱스 = ( h(k) + j x d(k) ) mod N


결국 probing 과정은
인덱스 h( h(k)+d(k) ),
인덱스 h( h(k) + 2d(k) ),
인덱스 h( h(k) + 3d(k) ),
인덱스 h( h(k) + 4d(k) ), ...
이 순으로 인덱스를 살펴보며 탐사를 진행하는 것이다.
(이때 인덱스 h(k) + 2d(k) 가 아니라, 인덱스 h ( h(k) + 2d(k) ) 인 이유는,
probing 을 진행하다가 배열 끝 인덱스까지 갔다면 다시 환형배열처럼 배열 앞부분으로 돌아와서 탐사 과정을 이어나가기 위함이다. 1차해시함수 h는 mod N 연산을 진행하는 함수이기 때문! )


결론 : probing 과정은 인덱스 ( h(k) + j x d(k) ) mod N= h( h(k) + j x d(k) ) 에 대해서 순차적으로 진행된다.

  • => 인덱스 i부터 시작해서 1차 해시함수 h(k) 값을 계속 더해나간 인덱스 값을 탐색한다.

  • 즉 인덱스 i, 인덱스 i + d(k), 인덱스 i + 2d(k), 인덱스 i + 3d(k),
    인덱스 i + 4d(k), ... 에 대해 탐색을 진행함

즉, 인덱스 i (= 1차해시함수의 결과값 i을 탐색의 시작 인덱스로 설정 ) 가 비었다면 2차 해시함수의 결과값(=d(k)) 만큼 계속 이동하면서 탐색을 진행하는 것이다.

2차해시함수 결과값 만큼 이동하면서 탐색을 진행하다 배열 끝부분에 도달하면 다시 맨 앞에서부터 환형 배열로써 탐색을 진행하기 위해 mod N 을 한다.

  • N 은 소수로 설정할것!

    • 소수로 설정 안하면 탐색을 이전에 진행한 곳을 또 탐색할 수가 있음.

    • ex) N = 10, d(k) = 5, i = 3인 경우, 계속 인덱스 3에 대해서만 탐색을 한다. 결국 탐색을 진행한 곳을 계속해서 또 본곳만 또 보게되는 꼴이됨.

    • N 을 소수로 설정하면 배열의 모든 인덱스에 대해서 탐색을 진행하게 됨

  • 더블 해싱도 삭제연산에서 AVAILABLE 객체를 이용해야함.

  • hash value 인 d(k) 는 0이 되서는 안된다.

    • 만일 0이라면 j 가 아무리 증가해도 인덱스 i 에 대해서만 계속 탐색을 진행하기 떄문
    • 이에 따라 d(k) 가 0이 아닌, 1~N 사이의 값이 되게 하는 기법이 아래 식처럼 필요함

2차해시함수 => d(k) = q - k mod q
(q : 소수)

더블 해싱의 insert 연산
더블 해싱은 1차 해시함수 결과값(= h(k) ) 를 삽입될 적절한 빈자리를 찾는 탐색(probing)의 시작 인덱스로 삼아서,
빈자리를 찾아낼 때 까지 2차 해시함수의 결과값 ( = d(k) ) 만큼
계속 이동을 해서 (= probing 과정) 빈자리를 찾아내고, 찾아낸 빈자리에 insert 하는 것이다.
( 선형탐사의 경우, 2차 해시함수의 결과값이 아닌 1 만큼 계속 이동해서 빈자리를 찾아내는 probing 과정을 진행했을 것이다! )

probing 진행시에, 1차해시함수로 구한 인덱스 i 에서 2차해시함수 결과값만큼 이동한다.
ex) 1차해시함수 결과값 = 2 이고, 2차해시함수 결과값 = 10 일때

=> 인덱스 2에 누군가 값이 들어있어서 경쟁해서 패배한경우, 인덱스 2에서 10만큼 이동한 곳인 인덱스 12로 탐사(probe) 를 해나간다.
인덱스 12 에도 누군가 있다면, 인덱스 12+10, 12+10+10, 12+10+10+10, ... 로 계속 탐사를 진행해 나가면서 insert 될 위치를 탐사해 나간다.

  • k mod q : 이 결과의 범위는 0 ~ (q-1) 이 된다.
    • 이떄 보듯이 0이 나올 수 있으므로, 0이 안나오게 하기 위해 이 값을 q 에서 빼버린다.
    • 즉, q - k mod q 를 하면 (k mod q) 값이 0 인 경우 q - 0 = q 가 되고,
      (k mod q) 값이 q-1 인 경우 q - (q-1) = 1 이 된다.
      => 범위 : 1 ~ q 로 변함
    • q는 N 보다는 작은 소수중 가장 큰 소수로 설정

ex) Double Hashing 으로 구현한 해시에서 insert 연산 진행하기

1차해시함수 h(k) = k mod 79,
2차해시함수 d(k) = 13 - k mod 13 일때

2가 들어오면 2 mod 79 를 하게되서 인덱스 2에 들어가게 되고,
다음으로 81이 들어오면 81 mod 79 를 하게되면 마찬가지로 인덱스 2에 들어가야함.
이럴때 2차 해시함수를 이용하는 것이다.

  • 80 을 insert 하기

    • 80 mod 13 = 2 이고( = 1차해시함수 결과값) ,
    • 이렇게 1차해시함수로 구해낸 인덱스 2에서 시작해서 빈자리를 찾아나가면 되는 것이다.
    • 이떄 빈자리를 찾는 것은 선형탐사는 바로 옆칸, 즉 1칸만 이동해서 빈자리인지 확인하면 되지만,
    • 이중해싱은 2차해시함수 결과값만큼 이동해서 빈자리인지를 확인하고 빈자리이자면 insert 를 한다.
    • 빈자리가 아닌 경우는 또 다시 2차해시함수 결과값 만큼 이동해서 빈자리인지를 확인하는 과정을 반복하면 된다.
    • 즉, 인덱스 2(=1차해시함수 결과값) 에서 부터 시작해서 2차해시함수 결과값인 13 - 81 mod 13 = 10 만큼 이동해서 빈자리인지를 판별한다.
    • 이때 인덱스 2은 빈자리이므로, probing 을 딱 1번만 진행하고 인덱스 3에다 81을 insert 하면된다.
  • 2를 insert 하기

    • 1차해시함수 결과값 = 2 mod 13 = 2
    • 2차해시함수 결과값 = 13 - 2 mod 13 = 11
      => 인덱스 2에서 부터 시작해서, 11 만큼 계속 이동을 해서 빈자리를 찾아내서 insert 하면 된다. 즉, 인덱스 2, 2+11, 2+22, 2+33, 2+44, ... 순으로 계속 probing 을 진행하며 빈자리를 찾아내면 된다.
    • 인덱스 2에는 데이터 81이 저장되어 있으므로, 10만큼 이동해서 탐사를 또 진행한다.
    • 2 + 11 = 인덱스 13 이 빈자리이므로, 인덱스 13에 2를 insert 한다!

예시

N = 13
1차 해시함수 h(k) = k mod 13
2차 해시함수 d(k) = 7 - mod 7

과정1) k = 18 을 insert 하기
=> h(k) = 5 이기 때문에 인덱스 5를 확인했더니 AVAILABLE 객체가 없고, 그냥 insert 하면 됨.

과정2) k = 41 을 insert
=> h(k) = 2 이므로 인덱스 2에 18을 insert

과정3) k = 22 을 insert
=> h(k) = 9 이므로 인덱스 9에 insert

과정4) k = 44 를 insert
=> h(k) = 5 이므로 인덱스 5에 insert 하려했더니 누가 있어서 probe 진행.
이떄 2차 해시함수 d(k) 를 활용해서 다른 인덱스에 insert 해야함.

2차 해시함수 d(k) 의 hash value 를 구해보면
즉 7 - 44 mod 7 = 7 - 2 = 5 이므로 인덱스 5에서 5칸을 이동한 곳인 인덱스 10에다 44를 insert

과정5) k = 59 를 insert
=> 인덱스 7에 insert

과정6) k = 32 를 insert
=> 인덱스 6에 isnert

과정7) k = 31 를 insert
=> h(k) = 5 이므로 2차 해시함수로 probing 을 진행한다.
2차 해시함수로 hash value 를 구해보면 7 - 31 mod 7 = 4 이다.
따라서 인덱스 5에서 4칸 이동한 곳이 인덱스 9에다 insert 하면 됨.

그런데 또 인덱스 9 안에 누가 담겨있으므로,
인덱스 ( 9 + 4 ) mod 13 = 인덱스 0에다 insert 하면 된다.

과정8) k = 73 을 insert
=> 인덱스 8에다 insert

결과 분석

총 probe 횟수 : 11번
(<=> linear probing 을 진행한경우 18번 진행한다.)


성능분석

expected time : 탐색,삽입,삭제 연산 모두 O(1)
worst case : 탐색, 삽입, 삭제 연산 모두 O(n) ( => 발생할 확률 굉장히 낮음 )

  • 최악의 경우 모든 해싱 기법들이 탐색, 삽입, 삭제 모두 O(n) 이 걸림
    • 해싱을 chaining 으로 구현했을 떄 : 특정 인덱스에 대해서만 collision이 발생해서 그 인덱스에만 모든 key값들이 싹다 저장되고(= 링크드리스트로 저장되고), 링크드리스트의 끝까지 찾아가서 뒤져보는 경우
    • 이중 해싱으로 구현했을 떄 : 1차 해시함수 뿐만 아니라, 2차 해시함수 값이 모두 동일한 데이터들만 들어온 경우.
      => 몰론 이런 경우가 발생할 확률은 굉장히 낮음!!!
  • load factor α (=n/N) 을 조절함으로써 평균 성능을 예측할 수 있다.

    • n : 실제 저장된 배열의 데이터 개수, N : 처음에 설정한 배열의 크기

      ex) 크기가 80인 배열에 40개의 데이터를 넣을떄 : α = 0.5

    • α 에 따라서 해싱의 성능이 달라짐

    • 즉, α 가 작을수록 성능이 더 좋아진다.

      • 다시말해 α 가 1에 가까워질수록 성능이 안좋아진다.
    • 배열의 크기가 클수록, 원소를 insert 할때 분산도 잘되고 충돌도 잘 안일어나고 probing 도 잘 안일어남.

=> α가 1에 가깝지 않은 이상, (n과 N이 비슷하지 않은 이상) 해싱의 속도는 굉장히 빨라진다.

  • hash 값이 랜덤으로 나온다고 가정하면 (즉, 잘 분포되어 나온다고 가정하면)
    1번의 삽입당 평균적으로 1/(1-α) 번 탐색(probing)을 수행한다.

    • ex. N이 n보다 2배 크면, α = 1/2 이고, 평균 탐색 횟수는 2 가 된다.

    • ex. N이 n보다 3배 크면, α = 1/3 이고, 평균 탐색 횟수는 1.5 가 된다.

일례로 100개의 n을 크기가 200개인 자료구조에 넣는다면,
BST의 경우 O(log n)번 즉, 10번을 연산하지만,

해싱은 2번의 연산만 하면 되므로 연산 속도가 굉장히 빨라진다.

따라서 해싱의 모든 연산 수행시간은 O(1)로 예측되어진다.

profile
블로그 이전 : https://haon.blog

0개의 댓글