13-1강. 해슁(Hashing) 1

 

 

• SUHA(Simple Uniform Hashing Assumption)

- 각각의 키가 모든 슬롯들에 균등한 확률로() 독립적으로(independently) 해슁된다는 가정 => 사실 현실적이지 않다.

   - 성능분석을 위해서 주로 하는 가정일 뿐

   - hash 함수는 deterministic하므로 현실에서는 불가능하다

- Load factor alpha = n/m:

   - n : 테이블에 저장될 키의 갯수

   - m : 해쉬테이블의 크기, 즉 연결리스트의 깃수

   - 각 슬롯에 저장된 키의 평균 갯수

- 연결리스트 T[j]의 길이를 Nj라고 하면, E[Nj] = alpha

- 만약 n = O(m)이면 평균검색시간은 O(1)