Data Structure - Hashing ( Introduce )

Dictionary

• 딕셔너리의 search, insert, delete는 다음과 같은 시간 복잡도를 가지게 됩니다.
  • array에서 O(n)의 시간복잡도
  • balance binary search tree 에서 O(log n)
• 하지만 우리는 hasing이라는 개념을 정의해야 합니다.
  • 이 hashing은 위에서 O(n), O(logn)의 시간복잡도를 가졌던 연산이 O(1)로 획기적으로 죽어들게 하는 자료구조 입니다.
• Hashing technique에는 static hashing과 dynamic hashing이 존재합니다.

Hash Tables

• static hashing에서는 dictinary의 쌍들이 table에 저장됩니다. 여기서 이것을 ht ( hash table )이라고 부릅니다.
  • 이러한 hash table은 b( bucket )으로 나뉘게 됩니다. ht[0], ... ,ht[b-1]
  • 각각의 bucket들은 s(dictionary pairs)을 가질 수 있게 됩니다.
  • 그러므로 bucket은 s( slot )이라는 것으로 이루어지게 됩니다. 각각의 슬롯은 최소한 1개의 dictionary pair를 가질 수 있습니다.
  • 그리고 이러한 dictionary pair의 address는 hash function이라는 것에 의해 결정됩니다. h( hash function )은 key를 bucket으로 mapping시켜 줍니다.
  • 즉 any key에 대해서 h(k)는 0 ~ b-1의 범위내에서 생성되게 됩니다. 그 이유는 b보다 종류가 다양해 질 수 없기 때문입니다.

• key density
  • n을 현재 hash table에 있는 pairs의 수라고 하고, T를 h(k)로 만들 수 있는 모든 경우의 키의 수라고 했을 때, n/T라고 정의됩니다.
    • 대부분의 key density는 매우 작습니다. 그 이유는 6개의 문자, 10진수, 대문자를 합치면 T : 1.6 * 10 ^ 9가 나오게 되어 분모가 매우 커져서 key density는 매우 작은 값이 나오게 됩니다.
• loading density or loading factor
  • a = n/(sb)로 정의되는데 s를 버킷의수, s를 슬롯의 수라고 하면 sb는 hash Table의 저장 용량이 됩니다. 그리고 n은 저장된 데이터의 수라고 위에서 설명했습니다.
• bucket b와 대게 같은 크기를 가지는 key의 개수는 T에 비해 작은 개수를 가집니다.
  • 따라서 hash function은 다른 key들이 같은 버킷으로 들어가게 해야만 합니다. ( 어쩔 수 없이 하게 됩니다. )
  • h(k1) = h(k2)에서 k1과 k2를 synonyms라고 합니다.
• overflow
  • 이는 home bucket이 꽉 찼는데 key pair가 더들어오려는 상황에서 발생합니다.
• collision
  • 이는 공간은 있는데 그냥 원래 home bucket에 dictionary pair가 있을 때 발생합니다.
• 대개 s( slot ) = 1일 떄 overflow와 collision은 동시에 일어납니다.

 

overflow, collision Example 

이러한 상황을 봅시다.

• b =  26, s = 2입니다.
• n = 10입니다 (acos, define, float, exp, char, atan, ceil, floor, clock, ctime)
• Loading factor a = 10/(26 * 2) = 0.19가 됩니다.
• hash function h는 첫번째 charactor의 순서라고 합시다. ex a = 0, b = 1

여기서는 h("clock")을 하려고 했는데 slot이 꽉차서 overflow가 나타납니다. 그리고 h("do")을 하려고 했는데 이미 define이 있지만 slot이 꽉차지는 않았기 때문에 collision이 일어나게 됩니다.

 

• 이러한 overflow가 일어나면 item은 (insert, delete, search)을 해야하는데, 이는 hash function, sarch a buck에 의존하게 됩니다.
  
  • 이는 n ( 저장되어 있는 item의 수 )에 의존하지 않습니다.
• 이러한 overflow은 흔한 상황입니다. 그 이유는 b/T가 매우 적은 값이기 때문입니다. 그래서 collision을 피하기는 힘듭니다.
• 우리가 collision을 아예 없게 만들지는 못하지만, 줄일 수는 있습니다. 그리고 hash function을 계산하기 쉽게 만들어야 합니다 ( GPU가 계산하기 쉽게 해야 하기 때문입니다. hash의 이점은 검색이 빠르다는 점에 있기 때문입니다. ). 또한 우리는 overflow을 처리하기 위한 메커니즘을 만들어야 하긴 합니다.