해슁1

해슁1 - 정리

 

SUHA(Simple uniform Hashing Assumption)

-각각의 키가 모든 슬록들에 균등한 확률로 독립적으로 해싱된다는 가정
  -성능 분석을 위해서 주로 하는 가정임
  -hash 함수는 deterministric 하므로 현실에서는 불가능
-Load Factor a = n/m;()
  -n:테이블에 저장된 키의 개수
  -m:해쉬테이블의 크기, 즉 연결리스트의 개수
  -각 슬롯에 저장된 키의 평균 개수
어떤 키가 각각의 슬록에 따라 균등하게 분포된다는것은 말이안됨

해싱을 포함하는 어떤 알고리즘의 성능을 분석하기위해서 사용하는 가정
(현실에서 실행X)

 

참고 영상

 

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4097?tab=note