해시 테이블의 충돌과 성능

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

해시 테이블은 해싱을 통해 빠르게 값을 검색할 수 있지만 해시 값이 겹치는 경우에 주의해야 한다.

 

 

부하율(Load factor)

전체 원소 개수 / 해시 테이블의 크기

• 부하율이 1이면 원소 개수가 테이블의 크기와 같다는 뜻이고 가장 이상적인 상태이다.
  모든 연산이 O(1)에 가깝게 작동하고 공간 이용도 효율적이다.
• 부하율이 1보다 낮아질수록 원소가 하나도 저장되지 않은 리스트가 많다는 뜻이고 공간이 낭비된다.
• 부하율이 1보다 커질수록 리스트의 크기가 1보다 크다는 것이고 검색 성능이 저하된다.

 

해시 테이블의 성능을 결정짓는 요소

• 부하율이 유일한 지표는 아니다.
  몇몇 해시 테이블은 부하율이 1에서 너무 멀어지면  해시 함수를 변경하여 1에 가깝게 만드는 재해싱(Rehashing)을 수행한다.
• 테이블의 크기와 해시 함수를 잘 고려해야 한다.