안녕하세요🙌! 개발자 갈레입니다!
이 글을 읽으면, 여러분들은 아래 질문들에 대해 스스로의 답변을 만드실 수 있을겁니다.
Q. ArrayList는 사이즈가 꽉 차면 어떻게 확장하지?
Q. ArrayList는 왜 50%씩 확장하지?
Q. HashMap는 사이즈가 꽉 차면 어떻게 확장하지?
Q. HashMap은 왜 2배씩 확장하지?
오늘은 알고리즘 문제를 풀며 겪었던 메모리 초과 문제 상황과 이를 해결하기 위해 LinkedList 구조를 살펴봤던 이야기를 해볼겁니다. LinkedList를 뜯어보니 HashMap 또한 궁금해지더군요! HashMap의 구조에 대해서도 알아보겠습니다.
글을 읽으시면서 핵심 부분(노란)과 꼬리질문(초록) 부분에 집중하며 읽어주세요! 개인적으로 키워드에서 꼬리질문을 하는게 개념을 깊이있게 이해하는 과정이라고 생각합니다:)
목차
1. 문제 상황 분석
- 알고리즘 문제
2. 기술 분석
- ArrayList
- HashMap
3. 결론
문제 상황 분석
거두절미하고 바로 들어가보죠!
저는 백준 2904 문제를 풀고 있었습니다! 여차여차 해서 문제를 풀었는데 메모리 초과가 나오더군요.. 메모리 초과는 잘 안나는 에러인데 등장해서 당황스러웠습니다.
제 코드 중에서 메모리를 많이 잡아 먹는 곳이 어딘가 살펴봤고, 아래 함수인걸로 파악했습니다. 다른 곳에선 정적인 배열만 사용하고 있었기 때문이죠. getPrimeNumbersUnder에서는 ArrayList를 만들고 이를 반환하는 함수입니다. 여기서 문제가 있을거라고 가정했습니다. 자! 그럼 ArrayList 안으로 들어가보죠!
static List<Integer> getPrimeNumbersUnder(int numberBorder) {
List<Integer> result = new ArrayList<>();
boolean[] isPrimeNumber = new boolean[numberBorder + 1];
for (int num = 2; num <= numberBorder; num++) {
if (!isPrimeNumber[num]) {
result.add(num);
for (int multipled = num * 2; multipled <= numberBorder; multipled += num) {
isPrimeNumber[multipled] = true;
}
}
}
return result;
}ArrayList
ArrayList에 들어가면 보이는게 DEFAULT_CAPACITY(<그림2>의 1번)입니다. 그렇다면 ArrayList는 최초 Capacity가 10이고 이를 넘어서면 사이즈 확장이 일어난다고 볼 수 있습니다. 그렇다면 어떤 방식으로 확장될까요? 이에 대한 답은 <그림2>의 2번에서 유추할 수 있습니다. ArrayList는 데이터를 Object 배열에 넣군요! ArrayList는 새로운 배열을 생성하여 기존 배열의 내용을 복사하는군요! 저희가 생각한게 맞는지 확인하기 위해 데이터 추가 함수를 살펴보죠!
<그림3>는 데이터 추가 함수입니다. (s == elementData.length)를 보면, 데이터가 꽉찬 경우 elementData를 grow 시켜주군요! 어떤 방식으로 grow 하는지 알아봅시다!
<그림4>은 arrayList의 grow 함수입니다. 아래 grow는 현재 minCapacity를 보장하는 배열 객체를 만들어서 돌려주는듯 하군요! grow(size + 1)로 들어가보죠!
<그림5>는 ArrayList의 grow(int minCapacity) 함수입니다! elementData내에 있는 데이터를 복사해서 newCapacity(minCapacity)에 붙여넣군요! 저희가 초기에 가정했던, elementData의 데이터를 복사하지 않을까 생각한게 거의 들어 맞고 있습니다! 확신하기 위해 newCapacity 함수로 들어가보죠!
<그림6>는 newCapacity 함수입니다. 해당 함수를 보면 답을 알 수 있습니다. 함수 주석에선 가능하면, 배열 사이즈를 50% 늘려준다고 돼있습니다(<그림6> 1번 참조). 해당 기능의 코드 구현은 <그림6> 2번에서 확실히 알 수 있습니다. 비트 연산을 이용하여 절반만큼 늘려주고 있군요!
저희가 처음 알고 싶었던 얘기의 답을 얻었습니다! 제 문제 풀이는 ArrayList의 배열 확장 방법을 고려하지 않은 비효율적인 구현이였습니다. 자 이쯤 되면 궁금해질 때가 됐습니다. HashMap은 그렇다면 어떤 방식으로 확장하지? 많은 사람들은 HashMap에서 해시 충돌이 일어나면 java에서는 LinkedList와 Binary tree를 이용하여 해결하는 것은 알고 있는데, Bucket size의 확장 방법은 잘 모릅니다. HashMap의 Bucket size 확장 방법에 대해 알아보도록 하죠!
HashMap
HashMap의 버킷 사이즈 확장 방법을 알아보기 위해 HashMap의 클래스 파일로 들어가보죠! <그림7>은 HashMap 클래스입니다! 들어가자마자 DEFAULT_INITIAL_CAPACITY가 보입니다. 1<<4 = 16이군요! 여기서 재밌는 사실을 발견할 수 있습니다. 함수 주석과 1<<4입니다. 함수 주석에 의하면 default inital capacity는 2의 제곱수여야 합니다. 심지어 숫자를 넣을 때 16이 아닌 1<<4를 넣었습니다! 마치 '우린 2의 제곱수를 설정해줬어!'라고 얘기 하고 있는듯하군요:) 자 그럼 왜 2의 제곱수를 설정해줘야하는지 알아봅시다! HashMap이 감당할 수 있는 데이터 저장 개수보다 많은 데이터가 들어올 때 bucket size가 커지겠죠. putVal로 가봅시다!
HashMap의 putVal입니다. 여기서 가장 중요한 부분은 <그림8>의 체크한 부분입니다. (n - 1) & hash 함수죠! 이게 뭐냐구요? 이건 hash % (bucket size)와 같은 기능을 합니다! 그럼 누군가가 질문할겁니다!
Q. hash % (bucket size)와 (n - 1) & hash가 어떻게 같죠? 10(hash) % 4(bucketsize) = 2와 (4-1) & 10(hash) = 3이기 떄문에 다르지 않나요?
A. 아주 좋은 질문입니다! 제가 전제 조건을 일부로 숨겼습니다. n이 2의 제곱수일 때만 같습니다. 지금부터 설명 드리죠!
Q. 2의 제곱 수는 어떤 방식으로 표현될까요?
A. 2의 제곱수는 항상 100000...(2)으로 표현됩니다. 단 하나의 1이 맨 왼쪽에 있고 나머지는 0이죠.
Q. 그렇다면 2^n -1은 어떤 방식으로 표현될까요?
A. 2^n -1은 항상 111111...(2) 으로 표현되죠.
Q. 101 0110 1101(2)은 1 0000(2)으로 나누면 어떻게 될까요?
A. 101 0110 0000(2)이 몫이 되고 1101(2)이 나머지가 됩니다. 자 그럼 우리가 나머지를 쉽게 만들려면 1111(2)이 있으면 되겠군요! 1111(2)과 101 0110 1101(2)을 & 연산하면 1101(2)이되니까요!
Q. 1111(2)은 어떻게 만들죠?
A. 1 0000(2)에서 1을 빼면 1111(2)이 됩니다. 그렇죠! (n - 1) & hash가 1111(2)을 만들 수 있는 연산입니다! 정확히는 (n-1)이 1111(2)을 만들죠!
주관적인 의견
비트 연산을 이용하면 나눗셈을 빠르게 할 수 있습니다. 컴퓨터는 0와 1로 이뤄져있기 때문에 비트 연산이 굉장히 빠르기 때문이죠. 그럼 누군가가 궁금해할겁니다!
Q. 근데 2^n으로 버킷 사이즈 늘리는건 너무 많이 늘리는거 아닌가요? 안쓸 버킷도 많을 수도 있잖아요!
A. 맞습니다! 해시 충돌이 많이 일어난다고 버킷 사이즈를 2배 늘리는건 비효율적일 수 있죠. 특히 DB sharding을 할 경우는 배보다 배꼽이 더 클 수 있습니다. 서버 개수를 2배 늘리는건 어려운 결정이죠. 하지만 지금은 해시 버킷을 늘리는거니까 큰 문제가 없습니다. 또한 버킷 사이즈는 2^n으로 가끔씩 늘어나지만, HashMap에 putVal를 하는건 버킷 사이즈에 비해 훨씬 많이 일어납니다. 더 많이 일어나는 연산(나눗셈)의 효율성을 고려하는게 맞다고 생각합니다.
Q. ArrayList도 HashMap 처럼 2배씩 확장하면 안되나요? 왜 ArrayList는 50%만 확장하나요?
A. 제 생각엔 ArrayList는 HashMap 처럼 비트 연산으로 이득 볼 경우가 크게 없기 때문에 2배씩 늘릴 필요가 없다고 생각합니다. 50%만 늘려도 그 목적에 충족했기 때문에 Java에서 해당 값으로 설정했다고 생각해요. 그에 비해 HashMap은 나눗셈에서 볼 수 있듯이 버킷 사이즈를 2^n으로 설정하여 얻을 수 있는 연산 성능 효율성이 크죠!
자 그럼 마지막 확인을 위해 resize() 함수로 들어가봅시다(<그림9> 참조). 해당 함수는 bucket size * load factor가 다 찼을 때, bucket size를 resizing 하는 역할을 합니다. 함수를 보아하니 실제로 old << 1;에서 threashold 크기를 두배로 늘려주군요! 이로서 저희는 bucket sizing이 2배씩 되는 것을 알았습니다.
결론
ArrayList와 HashMap의 튜닝 방법
자 그렇다면 우리 글의 제목이자 1차 목표인 ArrayList와 HashMap의 튜닝 방법에 대해 알아보죠! ArrayList와 HashMap은 내부 bucket 사이즈 보다 넘치면 새로 배열을 할당합니다. 따라서 해당 작업을 줄여야 겠죠. 두 객체의 initialCapacity를 사용하면 bucket 사이즈를 처음부터 크게 설정 할 수 있습니다. 만약 ArrayList와 HashMap에 넣을 데이터 개수가 고정돼있다면 initialCapacity를 설정해주는 것이 아주 좋은 성능 개선 방안이겠죠.
실제로 initalCapacity를 설정하지 않고 N개의 데이터를 HashMap에 넣었을 때, 키 & 값 쌍 접근 횟수는 아래와 같이 분석할 수 있습니다. 결국 N개의 키를 넣었을 때 2.5N - N = 1.5N배 더 많이 키 & 값 쌍 연산이 일어나게 되죠. Http request 한번에 여러 HashMap이 만들어지고 없어지는 상황에서 접근 연산을 150% 줄여주는 것은 좋은 성능 개선 방안이라고 볼 수 있습니다.
HashMap은 이에 더해 load factor를 크게 해주는 방법 또한 존재합니다. load factor를 크게 해주면 버킷 사이즈가 늘어나는 것을 늦출 수 있죠. 하지만 load factor가 높아진다면 해시 충돌이 일어날 가능성이 높아집니다. load 되는 비율이 높아지므로 한정된 공간 내에 많은 데이터가 쌓이게 되겠죠. 만약에 bucket 내부에 해시 충돌이 너무 많이 일어나서 해시 충돌 해결 구현체인 LinkedList가 Red black tree로 변하게 된다면 기존 LinkedList는 쓸모가 없어지기 때문에 또 다른 메모리 낭비가 일어나게 됩니다. 따라서 load factor를 조정하는건 메모리 효율성과 큰 의미가 없을 수도 있습니다.
글 서두 질문에 대한 대답
자 그렇다면 우리 글의 목표 2차 목표인 아래 질문에 대한 대답을 알아보도록 하죠!.
Q. ArrayList는 사이즈가 꽉 차면 어떻게 확장하지?
A. ArrayList는 사이즈가 꽉 차면 기존 배열 크기보다 50% 큰 새로운 배열을 할당해서 기존 배열의 값을 복사합니다.
Q. ArrayList는 왜 50%씩 확장하지?
A. ArrayList는 HashMap 처럼 비트 연산으로 이득 볼 경우가 크게 없기 때문에 2배씩 늘릴 필요가 없습니다. 50%의 크기가 ArrayList의 sizing 효과를 만족시킬 수 있는 적정 값이라고 java 측에서 판단했다고 생각합니다.
Q. HashMap는 사이즈가 꽉 차면 어떻게 확장하지?
A. HashMap은 Bucket size * load factor 이상으로 <key, value> 값이 들어오면 bucket size를 두배 늘립니다.
Q. HashMap은 왜 2배씩 확장하지?
A. Bucket size를 2의 제곱수로 유지하게 되면 hash의 인덱스 값을 비트 연산을 이용하여 빠르게 얻을 수 있다는 장점이 있습니다. 가끔씩 일어나는 2배의 bucket sizing 보다, 훨씬 자주 일어나는 putVal의 효율성이 더 중요하다고 할 수 있습니다.
출처
'Computer launguage > Java' 카테고리의 다른 글
| 자바 NIO (1) 채널, 버퍼의 동작 과정을 간단한 채팅 서버/클라 애플리케이션 구현을 통해 리서치 (0) | 2024.09.01 |
|---|---|
| [Deep dive] 부동 소수점, 고정 소수점 표현 방법? 연산 속도? 오차? 돈 계산? (0) | 2022.03.26 |
| [Deep Dive] Garbage Collector(GC) 구조? 동작 과정? SE7, 8 차이? (0) | 2022.03.11 |
| [Deep dive] JVM 구조? 자바 애플리케이션 실행 과정? 컴파일 과정? (2) | 2022.03.05 |
| 객체지향 프로그래밍? 장단점? 4대 원칙(추상화, 캡슐화, 상속, 다형성)이란? (0) | 2022.02.25 |
