해시 테이블 - collision resolution method

해시 함수에 의해 특정 인덱스 값이 정해지게 되면 c - universal function이기 때문에 충돌이 발생할 수 밖에 없다.

충돌이 발생했다는 것은 내가 삽입하려고 하는 슬롯에 이미 다른 key value 데이터가 저장되어 있는 것.

그럼 다른 어느 곳에 저장해야 될까? 에 대한 것을 collision resolution method이다.

대표적인 방법 중 하나 Open addressing인데 그 방식은 3가지로 나눌 수 있다.

1. linear probing - 한칸씩

2. quadratic probing - 제곱칸씩

3. double hashing - 해시함수 두개

set 함수 : key 값이 해시테이블에 있으면 update하고 아니면 insert (upsert)

set(key, value=None):

1. key 값이 HashTable(h.t)에 있으면 value를 update

2. key 값이 h.t에 없으면 (key, value)를 insert

remove 함수 : 해당 키 값이 h.t에 있으면 해당 슬롯을 비울 수 있도록

search 함수 : 해당 키 값이 h.t에 있으면 key와 value return 없으면 None return

이때 set, remove, search는 cluster size에 성능 영향을 받게 된다.

클러스터 사이즈란 해시 테이블에 덩어리로 뭉쳐있는 데이터를 말함

hash function, collision resolution method, load factor이 cluster size에 영향을 미침

load factor는 n/m 이고(m : slot의 개수, n : H에 저장된 item 개수) 0<= n/m < 1 임

예를들어 load facotr가 0.5 라면 50% 만큼 차 있다는 뜻

Cluster size는 왜 위의 세가지에 영향을 받을까?

클러스터 사이즈가 크다는 것은 데이터들이 연속해서 충돌을 일으키고 있다는 뜻!

hash function이 좋지 않다면 충돌이 일어날 확률(비슷한 인덱스를 반환)이 크므로 클러스터 사이즈가 커진다.

collision resolution method가 좋지 않다면, 충돌을 제대로 회피하지 못하므로 클러스터 사이즈가 커진다.

load factor가 크면 이는 클러스터 사이즈에 당연히 영향을 미칠 수 밖에 없음(차지하고 있는 비율이 크니깐)

또한 cluster size는 set, remove, search 함수의 수행시간과 비례하게 된다.

클러스터 사이즈가 커질 수록 각 함수들의 수행시간은 늘어날 것이 당연하다.

이때 평균적으로 m >= 2n 일 경우, 즉 해시 테이블에서 최소 50% 이상 빈 슬롯을 유지할 경우

평균 cluster size를 O(1)로 유지할 수 있다. 즉 이는 set, remove, search 수행시간도 O(1)로 유지된다는 것

(python에서는 3/1 이상 빈 슬롯을 유지하는 것으로 알고 있다. - 최근 버전에서 dict 관련 업데이트 된 것 같아서 나중에 다시 찾아보고 수정해야겠다)

또 하나의 collision resolution method인 Chaining은 동일한 key 값일 때 하나의 슬롯에 연결리스트로 연결해서 저장한다는 것

Chaining의 경우 hash function을 c - universal을 사용 할 경우 상수 시간 내에 set, search, remove 연산이 가능하다.

With Data