HashMap 의 capacity와 load factor

  HashMap은 Collections의 Map 인터페이스를 구현한 구현체로 해시 테이블을 바탕으로 만들어진다. 

HashMap의 특징은 순서가 아니라 수행시간에 전적으로 몰빵했다는 점이다. add,remove, find에 O(1)의 시간만 필요하다. (TreeMap O(logN)

HashMap은 전적으로 Hash 함수 (hashCode)에 의존하여 그 hash 함수가 원소들을 diverse하게 할수록 성능이 좋아진다.

 

  HashMap 외부에서 볼떄는 항상 같은 형태를 띌거라고 생각하지만 사실은 그렇지 않다.  capacity와 load factor라는 변인을 가지고 동적으로 변화한다. 

capacity 는 해시테이블의 버킷수다.

load factor는 해시테이블의 버킷이 얼마나 가득 찼는지 보여주는 수치다.

참고로 이 값을 설정하지 않을 경우 initial capcity 는 16, load factor는 0.75로 설정되게 된다.

 

 

  어플리케이션이 실행되면 시간이 지날수록 해시 테이블에 원소들이 추가 되어 버킷이 하나하나 채워질거고, 자연스럽게 같은 버킷을 쓰는 원소들도 많아질것이다. 별 다른 설정을 하지 않았다면, 이로 인해 해시테이블은 링크드 리스트와 가까운 형태를 띌거고 우리가 바라는 수행시간의 이득 또한 없어질 것이다.

  이를 방지하기 위해 HashMap은 load factor가 임계치에 다다르면 hash Table은 rehash하게 되고 bucket 수를 2배 증가시킨다. 즉 16이였던 bucket 수가 32로 증가한다. 이 특징으로 인해 쓸모없이 bucket 를 처음부터 많이 만들어 메모리를 낭비할 필요도 없이 bucket 수를 적게 가지고 시작하더라도 서서히 늘릴수 있다는 장점을 가지고 있다. (dynamic)

 

Java HashMap API의 resize가 바로 위의 역할을 해준다. 아래 코드를 보면 이 동작을 자세히 볼 수 있다.

docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap (Java Platform SE 8 )