[JAVA] #Deque VS Queue #ArrayDeque VS LinkedList #Map

💻 Java Collection?

Java의 컬렉션 프레임워크는 데이터를 효율적으로 저장하고 조작할 수 있는 다양한 인터페이스와 클래스를 제공합니다. 이 포스트에서는 Deque와 Queue의 성능 차이, ArrayDeque와 LinkedList의 성능 비교, 그리고 Map에서 키를 비교하는 방법에 대해 알아보겠습니다.

---

🔹 Deque와 Queue의 성능 차이

Deque(Double-Ended Queue)와 Queue는 모두 Java에서 큐 자료구조를 구현한 인터페이스입니다. 하지만 이 둘은 기능적 차이뿐만 아니라, 성능 면에서도 약간의 차이가 있습니다.

• Queue: 큐는 기본적으로 FIFO(First-In-First-Out) 방식으로 동작하는 자료구조입니다. 가장 많이 사용되는 구현체는 LinkedList와 PriorityQueue입니다. LinkedList는 삽입과 삭제가 O(1) 시간이 소요되는 반면, PriorityQueue는 요소를 정렬해야 하기 때문에 삽입과 삭제에 O(log n) 시간이 소요됩니다.
• Deque: Deque는 양방향으로 요소를 삽입하고 삭제할 수 있는 자료구조입니다. ArrayDeque와 LinkedList가 대표적인 구현체입니다. Deque는 양쪽 끝에서의 삽입과 삭제를 O(1) 시간에 처리할 수 있어 Queue보다 유연한 구조를 제공합니다.

Deque와 Queue 성능 비교

Deque와 Queue의 성능 차이는 구현체에 따라 달라집니다. Deque 인터페이스를 구현한 두 가지 대표적인 클래스는 ArrayDeque와 LinkedList입니다. 이제 이 둘의 성능 차이를 살펴보겠습니다.

• ArrayDeque: 배열 기반으로 구현되어 있으며, 중간에 요소를 추가하거나 삭제하는 경우 성능이 저하될 수 있습니다. 하지만 끝부분에서의 삽입과 삭제는 매우 빠릅니다(O(1)).
• LinkedList: 연결 리스트 기반으로 구현되어 있으며, 양쪽 끝에서의 삽입과 삭제가 O(1)로 빠릅니다. 그러나 메모리 오버헤드가 더 크고, 순차 접근 성능은 ArrayDeque에 비해 떨어집니다.

다음은 ArrayDeque와 LinkedList의 성능을 비교하는 간단한 예제입니다.

Deque<Integer> arrayDeque = new ArrayDeque<>();
Deque<Integer> linkedList = new LinkedList<>();

// ArrayDeque 성능 테스트
long start = System.nanoTime();
for (int i = 0; i < 1000000; i++) {
    arrayDeque.addLast(i);
}
long end = System.nanoTime();
System.out.println("ArrayDeque 삽입 시간: " + (end - start) + " ns");

// LinkedList 성능 테스트
start = System.nanoTime();
for (int i = 0; i < 1000000; i++) {
    linkedList.addLast(i);
}
end = System.nanoTime();
System.out.println("LinkedList 삽입 시간: " + (end - start) + " ns");

위의 테스트에서는 ArrayDeque가 끝부분에서의 삽입/삭제에서 더 나은 성능을 보여줍니다. 하지만 만약 중간 삽입/삭제가 빈번하다면 LinkedList가 더 유리할 수 있습니다.

---

🔹 Map과 키 비교

Java의 Map 인터페이스는 키와 값의 쌍으로 데이터를 저장하는 자료구조입니다. Map에서 키를 비교하는 방법과 성능에 중요한 영향을 미치는 요소들을 살펴보겠습니다.

Map에서 키가 정확히 일치하는지 확인하는 방법

Map에서 키가 정확히 일치하는지 확인하는 방법은 equals() 메서드를 사용하는 것입니다. Map은 내부적으로 키를 비교할 때 equals() 메서드를 호출하여 두 키가 같은지 확인합니다.

• equals() 메서드: equals() 메서드는 두 객체가 의미적으로 동일한지 비교합니다. 이 메서드를 오버라이드하여 객체 비교 로직을 커스터마이징할 수 있습니다.

예시:

Map<String, String> map = new HashMap<>();
map.put("key1", "value1");

boolean isEqual = map.containsKey("key1"); // true

위 코드에서 containsKey() 메서드는 내부적으로 equals()를 사용하여 key1이 존재하는지 확인합니다. equals() 메서드가 정확히 구현되어 있다면, 정확한 키 비교가 가능합니다.

Map의 키로 사용된 객체가 동일한지 확인하는 방법

키로 사용된 객체가 동일한지 확인할 때는 equals()와 hashCode() 메서드를 모두 고려해야 합니다.

• hashCode() 메서드: hashCode()는 객체를 해시 테이블에 저장할 때 사용되는 정수 값을 반환합니다. 두 객체가 equals() 메서드로 동일한지 판별될 경우, 동일한 hashCode 값을 반환해야 합니다. 그렇지 않으면 해시 충돌이 발생해 성능이 저하될 수 있습니다.
• equals()와 hashCode()의 관계: Map은 내부적으로 키를 저장할 때 hashCode()로 해시 값을 생성한 후, equals()로 동일성을 확인합니다. 이 두 메서드를 올바르게 구현하는 것이 중요합니다.

예시:

class Person {
    private String name;
    private int id;

    public Person(String name, int id) {
        this.name = name;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
}

Map<Person, String> personMap = new HashMap<>();
personMap.put(new Person("Alice", 1), "Developer");

boolean exists = personMap.containsKey(new Person("Alice", 1)); // true

위 코드에서 equals()와 hashCode() 메서드를 적절하게 오버라이드하여 동일한 속성 값을 가진 Person 객체들이 같은 키로 인식되도록 했습니다.

---

💡 정리

• Deque와 Queue 성능 차이: Deque는 양방향에서의 삽입과 삭제에 유리하며, ArrayDeque는 메모리 효율성과 끝부분에서의 성능이 뛰어납니다. LinkedList는 중간 삽입/삭제에서 더 좋은 성능을 보일 수 있습니다.
• Map과 키 비교: Map에서 키 비교는 equals()와 hashCode() 메서드에 의해 결정됩니다. 올바르게 구현된 equals()와 hashCode()는 Map에서 키로 사용된 객체의 동일성을 정확하게 판단하는 데 필수적입니다.