[JAVA/알고리즘] HashSet clear()와 removeAll() 메모리 (백준 1697)

 

 위의 문제를 HashSet을 이용하여 해결하였다. 

 

이 과정에서 메모리 초과로 인한 실패가 나왔었는데 그 이유는 HashSet의 clear() 함수 때문이었다.

 

<메모리 초과 코드>

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int cnt = 0;
        HashSet<Integer> set = new HashSet<>();
        set.add(n);
        while (!set.contains(m)) {
            ArrayList<Integer> list = new ArrayList<>();
            for(int x : set) {
                list.add(x-1);
                list.add(x+1);
                list.add(2*x);
            }
            // 메모리 초과 발생 이유
            set.clear();
            set.addAll(list);
            cnt++;
        }

        System.out.println(cnt);
    }
}

물론 위의 코드에서 0 <= n <= 100,000을 만족하지 않는 값들도 set에 저장된다는 문제도 있지만, 

문제는 set.clear(); 함수였다. 

 

<수정한 코드>  -> set.removeAll()을 이용하여 수정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int cnt = 0;
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> visited = new HashSet<>();
        set.add(n);
        while (!set.contains(m)) {
            ArrayList<Integer> list = new ArrayList<>();
            visited.addAll(set);
            for(int x : set) {
                list.add(x-1);
                list.add(x+1);
                list.add(2*x);
            }
            for(int x : list) {
                if (x > 1000000 || m < 0) continue;
                set.add(x);
            }
            set.removeAll(visited);
            cnt++;
        }
        System.out.println(cnt);
    }
}

 

 

chatGPT에게 물어본 결과,

 

set.clear()는 내부적으로 해시 테이블의 모든 버킷 (배열 요소)를 지워고, 버킷들을 초기화하는 방식이다. 

즉, 메모리에서 데이터를 제거하면서 해시 테이블 구조 자체는 그대로 남아있는 상태. 

한 번에 많은 데이터를 담았다 비우는 경우, 메모리 해제가 즉시 일어나지 않고 내부 구조가 커진 채로 유지될 가능성이 있다. 

=> 해시 테이블의 구조는 남아 있고, 메모리 해제가 느려질 수 있음. 내부 버킷 크기가 유지됨.

 

set.removeAll()은 내부적으로 데이터를 하나식 제거하는 방식이다. 

이 과정에서 HashSet의 내부 구조는 점진적으로 줄어들 수 있고, 가비지 컬렉터가 필요 없는 데이터를 조금씩 회수하면서 메모리 사용량이 완화되는 효과가 있을 수 있다. 

=> 데이터를 하나씩 제거하면서 메모리를 조금씩 회수할 기회가 생김. 해시 테이블 크기도 동적으로 조정될 수 있음. 

 

 

---

 

조금 더 깊게 들어가서 두 함수가 메모리에 어떤 영향을 미치는 지, 가비지 컬렉터 (Garbage Collector, GC)가 언제 개입하는지에 대해 알아보자면,

 

clear()

- HashSet의 모든 요소를 한 번에 제거

- 내부적으로 버킷 배열 자체는 그대로 남아있지만, 버킷에 연결된 노드들이 모두 쓰레기 객체가 됨

- 메모리엔 여전히 객체가 남아 있지만, 이 객체들을 참고하는 포인터가 없어져서  "GC의 대상"이 됨

- GC가 실행되기 전까지는 메모리에서 지워지지 않아, 메모리 사용량이 순간적으로 매우 높아짐.

 

비유: 창고에 있는 모든 상자를 한꺼번에 버리려고 밖에 쌓아둔 상황. 청소차(= GC)가 오기 전까지 창고 주변에 엄청난 쓰레기 더미가 생김.

 

removeAll()

- 하나씩 순차적으로 제거

- 각 요소가 제거될 때마다 바로바로 쓰레기 객체가 되고 , GC가 필요하면 제거해 갈 수 있음

- 한 번에 많은 쓰레기 객체가 생기지 않아 메모리 사용량이 급격히 증가하지 않음

 

비유: 상자를 하나씩 버리는 상황. 청소차(= GC)가 지나갈 때마다 조금씩 치워주기 때문에 쓰레기 더미가 많이 쌓이지 않음.

 

 

 

GC는 언제 개입하는가?

1. Heap 메모리가 부족할 때

2. JVM 이 한가할 때 (Idle 상태)

3. System.gc() 같은 명시적 호출 (보장되지 않음)

 

clear() 사용 시,

쓰레기 객체가 대량 생산되어 Heap 메모리 부족 상태에 빨리 도달할 수 있음. GC가 강제로 실행되면서 Stop-the-World(일시중지) 현상이 발생하고 메모리를 비우는 데 시간이 걸리

 

removeAll() 사용 시,

객체가 하나씩 제거되면서 쓰레기 객체 생성 되어 GC가 조금씩 메모리를 청소할 여유가 됨. 메모리 사용량이 급격히 늘어나지 않고, GC가 부드럽게 실행

 

 

결국, clear() 실행 시 많은 쓰레기 객체가 한 번에 생성 되고, GC 실행 전까지 메모리를 차지하여 메모리 초과가 발생.

 

 

---

 

 

stackoverflow에서도 비슷한 질문에 대해서 

새로운 HashSet을 만들어서 사용하는 것이 clear()를 사용하는 것 보다 좋다고 했다. 

 

 

 

물론 이 문제에 대해서는 BFS와 Queue를 사용하는 것이 더 효율적이라고 한다.

+) GPT의 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        if (n == m) {
            System.out.println(0);
            return;
        }

        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.add(n);
        visited.add(n);
        int cnt = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int x = queue.poll();

                if (x == m) {
                    System.out.println(cnt);
                    return;
                }

                int[] next = {x - 1, x + 1, 2 * x};
                for (int nx : next) {
                    if (nx >= 0 && nx <= 1000000 && !visited.contains(nx)) {
                        visited.add(nx);
                        queue.add(nx);
                    }
                }
            }
            cnt++;
        }
    }
}

 

 

 

 

<참고 자료>

https://stackoverflow.com/questions/17155664/memory-efficency-of-clearing-a-hashset-vs-creating-a-new-hashset

Memory efficency of clearing a HashSet vs. creating a new HashSet