부하율은 항상 O(1) 시간 복잡도로 계산할 수 있습니다. 몇몇 해시 테이블은 부하율이 1 근방의 특정 값보다 너무 크거나 작아지면 해시 함수를 변경하도록 구현되어 있으며, 이를 재해싱(rehashing)이라고 합니다. 즉, 해시 함수를 수정하여 부하율이 1에 가까운 값이 되도록 만드는 것입니다. 변경된 해시 함수에 의한 값의 분포와 부하율을 고려하여 해시 테이블의 크기도 변경할 수 있습니다.

그러나 부하율이 해시 테이블의 성능을 결정하는 유일한 지표는 아닙니다. 크기가 7인 해시 테이블에 일곱 개의 원소가 저장되어 있다고 가정해보겠습니다. 그런데 모든 원소가 같은 해시 값을 가져서 하나의 버킷(bucket)에 있습니다.¹ 그래서 검색 연산이 항상 O(1)이 아닌 O(N)의 시간 복잡도를 갖습니다. 그렇지만 부하율은 1로 계산되고, 이는 매우 이상적인 상태로 인식될 수 있습니다. 결국 이러한 경우에는 해시 함수가 문제입니다. 해시 함수는 서로 다른 키가 가급적이면 서로 겹치지 않고 골고루 분포되도록 해시 값을 만들어야 합니다. 기본적으로 버킷의 최대 크기와 최소 크기의 차이가 너무 크면 좋지 않습니다. 지금 설명한 예에서는 버킷의 크기 차이가 7입니다. 만약 해시 함수가 전체 일곱 개의 원소에 대해 서로 다른 해시 값을 반환한다면 검색 함수의 시간 복잡도는 O(1)이 되어 즉각적으로 결과를 반환할 수 있게 됩니다. 그리고 이때의 최대, 최소 버킷 크기 차이는 0입니다. 그러나 이렇게 만드는 작업은 해시 테이블 구현에서 수행되지 않습니다. 해시 테이블은 해시 함수 구현에 종속적이지 않기 때문에 해시 함수 자체에서 잘 고려해야 합니다.