LinkedHashSet/LinkedHashMap

1. LinkedHashSet과 LinkedHashMap이란?

Java 표준 라이브러리에는 Set과 Map 컬렉션의 여러 구현이 있습니다. 가장 널리 쓰이는 것은 HashSet과 HashMap입니다. 이 구조들은 해시를 통해 요소에 빠르게 접근할 수 있지만 순회 시 어떤 순서도 보장하지 않습니다. 순서가 중요할 때는 LinkedHashSet과 LinkedHashMap이 도움이 됩니다.

• LinkedHashSet — 요소가 추가된 순서를 기억하는 Set입니다.
• LinkedHashMap — 키–값 쌍의 삽입 순서(또는 필요에 따라 접근 순서)를 기억하는 Map입니다.

구현은 “일반적인” HashSet/HashMap과 거의 같지만, 요소의 순서를 저장하기 위해 이중 연결 리스트가 추가되어 있습니다.

2. 삽입 순서와 접근 순서

삽입 순서

기본적으로 LinkedHashSet과 LinkedHashMap은 순회할 때 요소를 추가된 순서대로 반환하도록 보장합니다(for-each/이터레이터).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// 출력: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// 출력: 1 -> one, 2 -> two, 3 -> three

접근 순서(LinkedHashMap 전용)

LinkedHashMap에는 마지막 접근 기준(access order) 모드가 있습니다. 맵을 생성할 때 생성자의 세 번째 인자로 true를 전달하면, 요소에 접근할 때마다(get/put) 해당 엔트리가 리스트 끝으로 이동합니다.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // 키 2에 접근

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// 출력: 1 3 2 (2는 마지막 — 해당 키에 접근했기 때문)

removeEldestEntry로 만드는 LRU 캐시

LinkedHashMap의 가장 큰 “장점”은 LRU 캐시(Least Recently Used, “가장 오래 사용되지 않은”)를 간단히 구현할 수 있다는 점입니다. 메서드 removeEldestEntry(Map.Entry<K,V> eldest)만 재정의하면 됩니다. 이 메서드가 true를 반환하면 새 항목을 추가할 때 가장 “오래된” 요소가 제거됩니다.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — 접근 순서
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 사용 예:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // 1을 가장 "최근"으로 만듦
cache.put(4, "four"); // 2가 제거됨(가장 오래된 항목)
System.out.println(cache.keySet()); // [3, 1, 4]

3. 메모리와 성능 비용: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

동작 방식

내부는 일반 HashSet/HashMap과 거의 동일하지만, 각 요소가 이중 연결 리스트에도 저장됩니다. 이 추가 구조가 삽입/접근 순서를 “기억”합니다.

메모리 비용

각 노드의 prev/next 참조 때문에 더 많은 메모리가 필요합니다. 수백만 개의 요소에서는 차이가 두드러지지만, 일반적인 작업에서는 결정적 순서를 위한 합리적인 비용입니다.

성능 비용

삽입/검색/삭제 같은 기본 연산은 여전히 암ortized O(1)입니다. 리스트를 함께 순회해야 하므로 순회는 약간 느려지지만, 대부분의 경우 차이는 미미합니다. 또한 “가장 오래된 항목 제거”(LRU) 시나리오는 매우 효율적인데, “가장 오래된” 요소가 항상 리스트의 머리에 있기 때문입니다.

정리하면, 순서가 중요하다면 LinkedHashSet/LinkedHashMap을 선택하세요. 메모리를 절약해야 하고 순서가 필요 없다면 HashSet/HashMap이면 충분합니다.

4. 캐싱, 결정적 출력, 안정적인 테스트

캐싱(LRU)

LinkedHashMap은 크기 제한과 “오래된” 요소의 자동 삭제가 필요한 캐시의 이상적인 기반입니다. 라이브러리/프레임워크, 파일·이미지, 계산 결과 캐싱 등에 활용됩니다.

결정적 출력

리포트, 내보내기, 직렬화처럼 데이터 표현의 예측 가능성이 중요한 경우 LinkedHashSet/LinkedHashMap을 사용하세요. 테스트에서는 특히 중요합니다 — 실행할 때마다 순서가 흔들리지 않습니다.

안정적인 테스트

단위 테스트에서는 기대하는 컬렉션과 실제 결과를 자주 비교합니다. 순서가 보장되지 않으면 테스트가 간헐적으로 실패할 수 있습니다. “Linked” 구현을 사용하면 결정성이 안정성을 보장합니다.

예: HashMap vs LinkedHashMap 비교

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // 순서는 임의일 수 있음!
System.out.println(linkedMap.keySet()); // 항상 1, 2, 3, 4, 5

5. 큐를 위한 LinkedList vs ArrayDeque

LinkedList

• List, Deque, Queue 인터페이스를 구현합니다.
• 이중 연결 리스트: 앞/뒤에서의 삽입·삭제가 빠릅니다.
• 큐(FIFO), 스택(LIFO), 양방향 덱으로 사용할 수 있습니다.

ArrayDeque

• Deque, Queue를 구현합니다(단, List는 아님).
• 배열 기반이며 자동으로 확장됩니다.
• 큐/스택 연산에서 LinkedList보다 대체로 더 빠르고 오버헤드가 적습니다.
• null 요소를 지원하지 않습니다.

언제 무엇을 사용할까?

• 큐와 스택 — 거의 항상 ArrayDeque.
• 중간에서의 삽입/삭제가 많고 리스트 기능도 필요 — LinkedList.
• 순서를 갖는 Set/Map — LinkedHashSet/LinkedHashMap.

예: 작업 큐

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

예: 스택

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

요약:
— 큐와 스택에는 ArrayDeque.
— 중간 삽입이 잦은 리스트에는 LinkedList.
— 순서가 필요한 Set/Map에는 LinkedHashSet/LinkedHashMap.

6. LinkedHashSet/LinkedHashMap 사용 시 흔한 실수

오류 №1: HashSet/HashMap이 순서를 유지한다고 기대함.
HashSet/HashMap은 순서를 보장하지 않습니다. 순서가 중요하다면 LinkedHashSet/LinkedHashMap을 사용하세요.

오류 №2: 캐시에 LinkedHashMap을 쓰면서 removeEldestEntry를 재정의하지 않음.
LRU를 구현하려면 removeEldestEntry를 재정의해야 합니다. 그렇지 않으면 맵이 제한 없이 커집니다.

오류 №3: 필요도 없는데 큐/스택에 LinkedList를 사용함.
대부분의 경우 ArrayDeque가 더 빠르고 더 경제적입니다.

오류 №4: LinkedHashMap이 정렬해 준다고 기대함.
LinkedHashMap은 삽입/접근 순서를 유지할 뿐 키로 정렬하지 않습니다. 정렬이 필요하면 TreeMap을 사용하세요.

오류 №5: ArrayDeque에 null 추가.
ArrayDeque는 null 요소를 지원하지 않습니다 — NullPointerException이 발생합니다.

오류 №6: 순서를 고려하지 않고 컬렉션을 비교함.
LinkedHashSet/LinkedHashMap과 일반 HashSet/HashMap을 비교할 때는 요소 순서의 차이를 고려하세요.