그리미
배열 크기를 크게 잡는 게 좋을 까? (with Load factor) 본문
동적으로 배열 크기를 조절할 수 있는 자료 구조의 경우 Load factor 에 도달하면 배열이 확장됩니다
Hashtable을 보면 load factor 에 도달하면 rehash 합니다. 즉, 더 큰 배열을 만들어 기존 데이터들을 적제하는 방식을 취합니다.
본 글에서는 rehash 에서 발생하는 오버헤드는 얼마인지와 유의미 한지를 알아보겠습니다.
public class HashTableTest {
static int SETTING = 66_667_000;
static int CNT = 50_000_000;
public static void main(String[] args) {
Hashtable<Integer, Integer> table = new Hashtable<>();
long startTime = System.currentTimeMillis();
for (int i=0; i<CNT; i++) {
table.put(i, i);
}
long endTime = System.currentTimeMillis();
System.out.println(calTime(startTime, endTime) + " 초");
Hashtable<Integer, Integer> compareTable = new Hashtable<>(SETTING);
startTime = System.currentTimeMillis();
for (int i=0; i<CNT; i++) {
compareTable.put(i, i);
}
endTime = System.currentTimeMillis();
System.out.println(calTime(startTime, endTime) + " 초");
}
}
다음 표는 위의 코드를 50번 진행 했을 때 나온 값의 평균으로 작성됐습니다.
SETTING을 66_667_000 한 이유는 compareTable 에서 rehashing 이 발생 방지를 위해서 입니다.
(시도 횟수(50_000_000) % 로드팩터 (0.75)+ 여유값)
또한 공정한 타임 체크를 위해 각각 실행하여 측정하였습니다.
| 설정 | 소요 시간 |
| 기본 (10일 때) | 4.3 ~ 4.99 초 |
| 초기값 66_667_000 | 3.1 ~ 3.38 초 |
GC 횟수 역시 동일 하기 때문에 시간이차이 나는 원인은 rehasing 이다.
(GC 횟수는 아래 사진에서 확인 할 수 있습니다.)
다만, 50_000_000 번이라는 다소 큰 연산이 진행 됐음에도 대략 1초 정도의 시간 차이만 보이는 것을 감안 할 때
유의미한 시간 차이가 난다고 보기는 어렵습니다.
(HashMap 으로도 테스트 진행 하였으나 위의 표와 유사한 수치가 나왔습니다)
