Hash Table

Search, Insert, Delete를 모두 상수시간에 하는 것이 목표다!
가능할까?
➡️ key 값 비교를 하지 말고 key 값으로 자리를 정하자!
 

Hashing Method

divsion hashing - h(k; p) : k mod p (p는 소수이고 table size와 비슷하면서 작은 숫자 주로 2의 거듭제곱)
근데 2의 거듭제곱을 divisor로 사용했을 때 문제점: $2^3$로 하면 하위 3개 digit들만 영향을 받음
 
그럼!
multiplicative hashing - $h(k; a) =  \left \lfloor (a\times k \times mod W)/(W/M)\right \rfloor$
a는 보통 W에 대한 소수로 정함
근데 만약에 $W=2^w$이고 $M=2^M$이면...? - right shift 연산이랑 똑같아져 간편해짐
예를 들어 h(47, 3) W=32, M=4라고 해보자.
$ \left \lfloor (47\times 3 \times mod 32)/(32/4)\right \rfloor$
$ \left \lfloor (141 \times mod 32)/(32/4)\right \rfloor$
$ \left \lfloor (13)/(8)\right \rfloor$
$ 1 $이다. 13을 bit로 나타내면 1101이고 3만큼 right shift를 하면 1이다. 
 

load factor

$\lambda =n_{load}/M$
적재율 또한 hash table를 다룸에 있어 중요하다. 단순히 전체 table size에서 몇 칸이 차 있는지 나타내는 비율이다.
너무 적재율이 크면 중복될 가능성이 늘어나 collision 발생 확률이 올라간다. 
 

Collision Resolution

• (separtate) chaining = open hashing
  • 여기서 질문, 만약 open hashing 을 하면 search와 insert operation 은 적재률 lambda에 영향을 받을까?
    • search는 받는다! 당연히 높은 적재률을 보이면 chain된 list도 있을 확률이 높으므로 받으나
    • insert은 받지 않는다. linked list로 chain 되기 때문에 상수시간이 걸린다.
  • 적재률이 1을 초과할 수도 있다. 
• open addressing = closed hashing
  • collide 하면 빈 자리를 찾아서 넣어준다. 
  • 적재률이 1을 초과하지 않는다.
    • linear probing : $h_{i}(k)=h(k)+i\cdot mod M$
    • quadratic probing : $h_{i}(k)=h(k)+i^2\cdot mod M$
    • double hashing : $h_{i}(k)=h(k) + i \cdot f(k) \cdot mod M$
      • 만약 f(k)와 M이 서로 1보다 큰 최대공약수를 가진다면? - 계속 반복되게 할당 될 것임
  • deletion이 발생할 경우 key가 있던 자리에 있었다고 표시를 해줘야 한다. 
    • 만약 x, y, z순으로 insert 되었을 때 x가 삭제 되었다고 그냥 null로 해놓으면 y, z를 찾을 때 table에 없다고 표시 될 것이기 때문에