HashMap의 capacity와 load factor
HashMap의 API 문서에 보면 생성자에 파라미터로 capacity와 load factor가 나옵니다.
HashMap의 기본 생성자에서 capacity는 16, load factor는 0.75로 생성됩니다.
각각의 의미는
- capacity == bucket의 크기
- HashMap에 저장된 데이터ㅗ의 수 == capacity * loadFactor
라고 생각하면 됩니다.
capacity가 16이라면 아래 그림과 같은 사이즈가 16인 ArrayList가 생성됩니다.
그리고 put 작업을 통해 map에 데이터를 저장하는데 저장할 위치를 다음과 같이 계산합니다.
int index = key.hashCode() % capacity
만약 index가 중복된다면 어떻게 될까?
그림과 같이 해당 index에 링크드 리스트 형태로 저장됩니다. 이를 Separate Chaining이라 합니다.
이 상황에서 get() 메소드를 사용한다면 key의 해시 계산 결과가 0일 때 0번째 index에는 데이터가 2개 들어있는 상황이라 해당하는 데이터들이 key값과 일치하는지 검사를 2번 진행해야 합니다.
만약 데이터가 많다면?
데이터가 적다면 이런 해시충돌은 그렇게 크게 치명적이지 않을지도 모릅니다. 하지만 HashMap에 저장해야할 데이터가 많지만 capacity가 작다면 put 과정에서 해시충돌이 빈번하게 발생하고 get() 호출에도 부정적인 영향이 있습니다.(equals() 연산을 n번 반복해야하기 때문에)
그래서 HashMap은 capacity에 일정 갯수 이상의 데이터가 들어오면 자동으로 capacity를 늘립니다.
늘리는 시점은
loadFactor == 저장된 데이터 수 / capacity
입니다.
그렇기 때문에 loadFactor는 한 공간에 저장된 데이터 수라고 볼 수 있습니다.
만약 모든 공간에 데이터들이 균등하게 퍼져서 저장되어 loadFactor가 <= 1을 유지한다면 get()메소드 호출은 빠를 것입니다.
하지만 그렇지 못한 경우 loadFactor의 값은 증가하고 get() 메소드의 성능은 떨어지게 됩니다.
그렇기 때문에 이런 문제를 개선하기 위해 자동으로 capacity를 늘려 하나의 index에 2개 이상의 값이 들어가는 것을 방지하려고 합니다.
그렇다면 capacity를 크게 하면?
그렇다고 처음부터 HashMap의 capacity를 크게 잡아버리면 처음에는 빈 공간이 많을테니 메모리가 낭비되고 Iteration 상황에서 빈공간을 포함한 모든 데이터를 조회해야 하기 때문에 성능이 저하됩니다.
loadFactor의 tradeoff
loadFactor가 작으면, capacity가 커지므로 메모리는 많이 차지하지만, get() 메소드의 호출은 빨라집니다.
반대로 loadFactor가 커지면 capacity가 작아지므로 메모리는 적게 차지하지만, get() 메소드의 호출은 느려집니다.
API에서 권장하는 값은 0.75입니다. 개발자들이 가장 최적의 값이라고 합니다.
데이터 수를 예측 가능하다면?
HashMap에 저장될 데이터의 수가 짐작 가능하다면 capacity를 생성할 때 설정해주는 것이 좋습니다. 만약 데이터의 양이 많아 capacity 값이 자동으로 증가한다면 늘어난 capacity에 맞게 모든 데이터들을 rehashing하는 작업이 발생하기 때문입니다.
참고
https://onsil-thegreenhouse.github.io/programming/java/2018/02/22/java_tutorial_HashMap_bucket/
