[Java] removeAll, retainAll 내부 동작 분석, batchRemove

removeAll과 retainAll 메서드는 모두 내부적으로 batchRemove 메서드를 호출하며, 제거 방식만 complement 파라미터로 구분한다.

• removeAll: complement = false (컬렉션에 있는 요소 제거)
• retainAll: complement = true (컬렉션에 있는 요소만 유지)

public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);
}

 

boolean batchRemove(Collection<?> c, boolean complement,
   final int from, final int end) {
  Objects.requireNonNull(c);
  final Object[] es = elementData;
  int r;
  // Optimize for initial run of survivors
  for (r = from;; r++) {
   if (r == end)
    return false;
   if (c.contains(es[r]) != complement)
    break;
  }
  int w = r++;
  try {
   for (Object e; r < end; r++)
    if (c.contains(e = es[r]) == complement)
     es[w++] = e;
  } catch (Throwable ex) {
   // Preserve behavioral compatibility with AbstractCollection,
   // even if c.contains() throws.
   System.arraycopy(es, r, es, w, end - r);
   w += end - r;
   throw ex;
  } finally {
   modCount += end - w;
   shiftTailOverGap(es, w, end);
  }
  return true;
}

 

batchRemove 핵심 동작

1. 첫 번째 remove 대상 탐색

for (r = from;; r++) {
  if (r == end)
   return false;
  if (c.contains(es[r]) != complement)
   break;
}

해당 루프는 제거할 필요가 없는 연속된 요소를 건너뛰는 최적화이다. 첫 번째로 제거되어야 하는 요소를 찾을 때까지 반복한다.

 

2. remove 수행

int w = r++;
try {
  for (Object e; r < end; r++)
   if (c.contains(e = es[r]) == complement)
    es[w++] = e;
}

• w: 쓰기 위치 인덱스 (유지할 요소를 복사할 위치)
• r: 읽기 위치 인덱스 (검사 중인 요소 위치)

 

r을 증가시키며 배열에서 조건에 맞는 요소가 발견되면 w 위치에 복사하고 w를 증가시킨다. (즉, 조건에 맞지 않는 요소는 스킵)

이렇게 해당 루프는 조건에 맞는 요소만 유지하면서 배열을 압축시킨다.

• 투 포인터(Two Pointers) 알고리즘 활용: r(읽기)와 w(쓰기) 인덱스
• 한 번의 순회로 모든 작업 완료 (불필요한 반복 제거)

 

3. 요소 재배치

finally {
  modCount += end - w;
  shiftTailOverGap(es, w, end);
}

• modCount: 구조적 변경 횟수를 증가시켜 fail-fast 동작을 지원
• shiftTailOverGap: 제거된 요소들로 인한 공백을 없애는 작업

/** Erases the gap from lo to hi, by sliding down following elements. */
private void shiftTailOverGap(Object[] es, int lo, int hi) {
  System.arraycopy(es, hi, es, lo, size - hi);
  for (int to = size, i = (size -= hi - lo); i < to; i++)
   es[i] = null;
}

 

1) 제거 구간 이후의 요소들을 제거 구간의 시작 위치로 복사

System.arraycopy(es, hi, es, lo, size - hi);

 

• es: 내부 배열
• hi: 제거 구간의 끝 인덱스
• lo: 제거 구간의 시작 인덱스
• size - hi: 제거 구간 이후 남은 요소의 개수

 

2. 새 크기(i) 이후부터 원래 크기(to) 사이의 모든 요소를 null로 설정 

for(int to= size, i =(size -= hi - lo); i <to; i++) es[i]=null;

• size -= hi - lo: ArrayList의 크기를 갱신하고 새 크기를 i에 할당
• to: 원래 크기

위처럼 배열이 참조할 필요할 필요가 없어진 경우는 null로 설정해 가비지 컬렉션이 가능하게 해준다.

---

시간 복잡도

1. Big O: 각 요소마다 c.contains() 호출 필요 (m : 컬렉션 c의 크기, n : 컬렉션 c의 contains 시간 복잡도)
   • List 크기가 m이면 최대 m번의 contains 호출
   • ArrayList/ LinkedList: contains는 O(n), 총 O(n·m)
   • TreeSet : contains: O(log n), 총 O(m* log n)
   • HashSet: contains: O(1), 총 O(n)
2. 컬렉션 크기(m)가 상수인 경우
   • 예시: 컬렉션 c가 (m:100개) 이하의 고정된 크기를 가질 때
   • 분석
     • c가 ArrayList인 경우: c.contains() 시간 복잡도는 O(n), 전체 연산: O(n × m) = O(n × 100) = O(n)
     • c가 HashSet인 경우: c.contains() 시간 복잡도가 O(1), 전체 연산: O(m) = O(1)
     • 결론: m이 상수라면 선형 시간(O(n)) 으로 처리
3. 컬렉션 크기(m)가 n에 비례하는 경우
   
   • 예시: c가 n의 1% 크기를 가질 때 (m = 0.01n)
   • 분석:
     • c가 ArrayList인 경우: c.contains() 시간복잡도 O(m) = O(0.01n) 이므로, 전체 연산은 O(n × 0.01n) = O(n²) 
     • c가 HashSet인 경우: c.contains() 시간복잡도 O(1), 전체 연산: O(n)
     • 결론: m이 n에 비례하면 O(n²)이 됨 (단, c가 HashSet은 O(n))

 

 

 

참고자료 : 

자바로 배우는 핵심 자료구조와 알고리즘(Think Data Structures)

https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L897