[Data Structure] Hashing - 이론

Hahsing

---

• Search 알고리즘과 관련해서, 정렬이 되어있을 때, binary Search로 O(logn)의 성능을 낼 수 있다.

• 이에 반해서, Hashing은 최대 O(1)의 성능을 낼 수 있다.

• Hash table은 Slot으로 이루어져있는데, 각각Slot의 이름은 숫자로 되어있고, 0부터 시작한다.

• 이를 통해서 쉽게 item을 찾을 수 있다.

• item과slot을 맵핑하는 방법으로 Hash Function을 이용한다. Hash Function은 Slot name의 범위내의 int 값을 리턴한다.

• 위와같이 Hash Table이 만들어 지면, search는 O(1)에 할 수 있다.

• 그러나, Hash Function의 결과 값이 같으면 한 Slot에 여러 Item이 들어 가게 되는데 이것을 Collision 이라고 한다.

Hash Function

---

• 만약 Collision이 없도록 하는 Hash Function이 있다면, 그것은 perfect hash function 이라고 부르는데, 이것은 시스템적으로 만들 수 없고, 또 그럴 필요도 없다.

• 굳이 원한다면, Slot의 크기를 늘리는 방법이 있지만, Item이 너무 많을 경우에, 그만큼 이상의 더 많은 Slot이 필요하고, 반대로 적은 경우에는 Slot을 지나치게 낭비하게 된다.

• 가장 Hash Function은

  1. 충돌은 최소화

  2. 계산은 쉽게

  3. 고르게 배분

  한 것이라고 할 수 있다.

• Hash Function의 예로 Folding Method 가 있는데, item을 같은 size로 각각 조각으로 나누고 그 값들을 전부 합한 후에, Remainder Method에 적용 시키는 것이다.

• 또다른 방법은 Mid Square Method 이다. 해당 item을 제곱한 다음에 그중 특별 부분을 발췌하는 것이다.

  • ex) 44 ^ 2 = 1936 -> 여기서 '93' 부분을 발췌 하여서 Remainder Method에 적용한다.

  • Char-based item 일때도 비슷하게 적용가능 하다.

    Ord('c') = 99
    Ord('a') = 97
    Ord('t') = 116
    # 99 + 97 + 116 = 312
    # 312 % 11 => 4

• 이것의 문제는 'act' , 'tac' 등도 같은데 이때는 position 당 가중치를 매긴다.

  • ex) 99 x 1 + 97 x 2 + 116 x 3 = 641 % 11 => 3

• 조심해야할 것은 Hash Function이 너무 복잡하면 기존의 Sequential, Binary Search 보다 더 효율이 떨어 질 수도 있다는 사실이다.

Collision Resolution

---

• Collision이 발생했을 때 해결방법으로는'Open Addressing'이 있다.

• Hash function을 통해 정해진 최초 position에서 부터, 한 Slot씩 순회하면서, 빈 Slot이 있는지 찾고 찾으면 값을 넣는 방식이다. - 한번씩 각Slot을 탐색하기 때문에 Linear probing이라고 한다.

• 이것의 문제점은 Clustering인데, 같은 Hash Function에서 많은 Collision이 발생하면, 많은 인근 Slot 들이 Linear Probing resolution에 의해 채워질 수 있다. 즉, 다른 item들이 정상적으로 Slot에 삽입될 때 문제가 될 수 있다.

• 이를 해결하기 위해서는 한칸씩 탐색하는 것이 아닌 일정거리 만큼 Skip하고 넣는 방식이 있는데,

• 이와 같은 것을rehashing이라고 한다.

  • rehash(pos) = (pos + skip) % size of Table 로 계산한다.

• 여기서 중요한 것은 Skip의 사이즈는 모든 슬롯을 방문할 수 있게 정해야되는데, 그래서 대개 테이블 사이즈는'Prime Number'로 정한다. - 예제에서는 11 로 하였다.

• Quadratic Probing방법은 Skip 값을 쓰는 대신에, 1, 4, 9, 16 ... 으로 대체한다. 예를들어서, hash value가 1 이라면, collision이 발생했을 때, 1 + 1 즉, skip 값 대신에 1을 넣고, 또 collision이 발생했 다면, 4 + 1, 9 + 1 ... 이런 식으로 하는 방법이다.

• 'Open Addressing'의 대안으로는 'Chaning Method'가 있다.

• Collision이 발생했을 때에 각 item의 reference를 가지고, 링크드 리스트 형태로 가지는 방법이다.

• 위의 Open Addressing의 문제를 해결해주는 장점도 있지만, 한 location에 collision이 많이 발생하여 몰릴 경우 탐색할 때 성능이 떨어지는 단점이 있다.