[Hash table]

1.Limit of divide and conquer :

the efficiency is limited to the logarithm of the problem size!

still remain time complex..

 

2. Searching and sorting without comparison!!

but... how..?

 

3.  Hash Table : Dictionary 형식 key , value 사용!

hash funtion은 key를 이용하여 array index를 찾아 거기에 value를 store 한다! -> time complex 없이 그냥 찾을 수 있음!

f( Key ) -> array index -> store value

* one key -> one index * multi key -> one index

 

 

Hash function

value의  key를 array의 index로 convert하는 함수!

 

(1) perfect hash function

-무제한의 공간에 -제한적인 input size가 있고 -key와 index는 모두 1:1 대응( Bijective Function) 

그러나.. 사실 구현하기 불가능하며.. 이렇게 그냥 막 늘여놓는다면 hash function을 쓰는 이유가 없다!

 

(2) Good hash function

-uniform distribution 인덱스당 store된 key가 적당히 분포되어 있어야 하고 

- low cost 계산 비용이 적어야 하며 

- determinism 딱딱 나와야하고

-variable range 인덱스 range가 size를 넘어가면 안된다.

여전히 uniform distribution하기 어렵지만.. 그래도 해볼만하다!!

 

 Hash function의 예

1) Modulo based hash function   f( key ) : key % num → index

- divide a numeric key with number

-(1)  low cost : 나누기만 하면 됨!

-(2) range : [0, num-1] 적절~

-(3) uniform distribution 하기 쪼끔 어려움 : key 의 정보값을 너무 많이 버리게 됨 ㅠㅠ

 

2) Square based hash function f( key ) : MidSquare(key^2) % num → index

-(1)  low cost : 쪼끔 비용은 들지만 이정도면 soso~

-(2) range : [0, num-1] 적절~

-(3) 더 많은 key 정보를 사용하므로 uniform 하게 됨 -> collision 적어짐!

 

3) Digit analysis based hash function f( key ) : DigitSum(key) % num → index

-수를 나타내는 숫자를 이용함!!!!

-(1)  low cost : 완전 적게 든다.

-(2) range : [0, num-1] 적절~

-(3) 안 쓰는 key 정보가 없다! uniform 하게 됨 -> collision 적어짐!

 

collision resolution of hashing

하나의 index에 여러개의 key 값이 entry 되면 발생... 운명임...

collision을 가늠할 수 있는 수치가 바로 Load factor

-N: size of the stored entries

-S: size of hash table

Load factor : N/ S  → [0,1]

 

Collision resolution by closed addressing

-index에 여러개의 key를 store하는 것! (chaining)

 

-how? table에 linked list의 Head만 저장해 놓고, 새로운 값이 들어오면 linked list에 이어나감. 

                                (linked list 아니더라도 tree root도 가능함~ 근데 무거워질 수 있음)

-worst case : 하나의 index에 그냥 다 store하는 것 : linked list와 다름 없음;;

-Deletion : 그냥 bucket 으로 가서 linked list 따라가서 지우면 됨! easy~

 

Collision resolution by opened addressing

-index 에는 오직 한 개의 key만 store!! 다른 index 찾아가라!

 

-Probing(다른 index 찾아가는 법) :

(1) Linear probing : 방이 없으면 바로 다음 bucket을 찾아감

f(key) + i

 

(2) Quadratic probing  방이 없으면 다음 i^2 번째 bucket을 찾아감 

f(key ) + i + i^2

Q . i^2 를 찾아가는 이유?  result가 뭉친 지점이 존재한다. 그 때는 index 몇 개 옆으로 가봐야 어차피 다 차있음... 차라리 cluster 지점을 벗어나는 것이 좋다.

 

-Deletion : Lazy deletion을 해야 함.

지우지 않고 remove 표시만 해 둠. 이후 Load factor 가 커지면 새로운 hash table에 전체 정보를 copy를 하게 되는데 이때 표시된 원소는 copy 하지 않음.