[JAVA] ArrayList의 로드팩터는 1인데 HashMap의 로드팩터는 0.75일까?

 

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

HashMap의 capacity(용량)은 16이다. 즉 처음 내부적으로 생성되는 배열(버킷)의 크기가 16이라는 의미이다. 그리고 load factor(로드팩터)는 0.75이다. 즉 용량의 0.75가 찼을때 내부적으로 배열의 크기를 2배 늘린다.

 

그렇다면 왜 ArrayList의 로드팩터는 1인데 HashMap의 기본 로드팩터는 0.75일까?

 

이유는 해싱 충돌때문이다. 해시함수를 통해 해시값을 구하고 인덱스를 구하면 동일한 인덱스를 가질 가능성이 있고, 해싱 충돌이 일어나면 추가적인 탐색 기간이 소요되기 때문에 이러한 해시충돌을 줄이기위해 0.75만큼 용량이 찼을 때, 미리 배열을 늘려 해시 충돌의 가능성을 줄이는 것이다.

하지만 배열은 해시충돌이라는 개념도 없고 단순히 기존의 배열을 새로운 배열로 옮기기 때문에 미리 배열의 크기를 늘릴 필요가 없다. 

 

그리고 로드팩터가 0.75가 됐을 때 2배 크기의 새로운 배열이 생성되고 기존 배열의 값을 새로운 배열의 버킷으로 재분배되는 rehash 작업이 일어난다. 이 작업은 인덱스가 변경이 될만큼 비싼 작업이므로 초기 용량을 충분히 주어서 rehash 작업이 일어나지 않도록 해야한다.