이번에는 시간 복잡도에 대해 생각해보겠습니다. 일단 삽입 함수의 시간 복잡도는 O(1)입니다. 리스트에 노드를 추가하는 연산이 단순히 값을 설정하는 것보다는 조금 느릴 수 있지만 심하게 느리지는 않습니다. 체이닝을 통해 얻을 수 있는 이점에 비하면 무시할 수 있는 수준입니다. 다만 룩업과 삭제는 데이터 크기와 해시 테이블 크기에 따라 상당히 느릴 수 있습니다. 예를 들어 모든 키가 같은 해시 값을 가질 경우, 룩업 연산은 연결 리스트에서 선형 검색을 수행하는 것과 같으므로 O(N)의 시간 복잡도를 갖게 됩니다.

만약 해시 테이블이 저장할 키 개수에 비해 매우 작다면 충돌이 많이 발생하게 되고, 리스트는 평균적으로 더 길어집니다. 반면에 너무 큰 해시 테이블을 가지고 있다면 실제 데이터는 듬성듬성 존재하게 되므로 메모리 낭비가 발생합니다. 그러므로 응용 프로그램의 동작 시나리오를 고려하여 해시 테이블 크기를 적절히 조절해야 합니다. 이를 위해 수식을 하나 정의할 수 있습니다.

부하율(load factor)은 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 나타내며, 다음 수식을 이용하여 구할 수 있습니다.

▲ 그림 3-6 부하율

만약 키 개수가 해시 테이블 크기와 같다면 부하율은 1입니다. 이는 매우 이상적인 상태로, 모든 연산이 O(1)에 가깝게 작동하고 모든 메모리 공간을 적절하게 활용합니다.

부하율이 1보다 작으면 리스트당 키가 하나도 저장되지 않은 경우가 있다는 것이고, 이는 메모리 낭비가 될 수 있습니다.

만약 부하율이 1보다 크면 이는 리스트의 평균 길이가 1보다 크다는 의미이고, 이 경우 검색, 삭제 등의 함수가 약간 느리게 동작할 수 있습니다.