-
해시 테이블 개요
해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조이다.
해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다.
단, 테이블의 모든 영역에 값을 적절하게 분배하도록 만들지 못하는 경우 인덱싱이 필요하게 되어 성능이 떨어질 수 있게 된다. 따라서 해시 함수의 성능이 중요하게 된다.
이때 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m 이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다.