Course 모듈 1 - Lecture: TreeMap 컬렉션 소개

어느 날 대학에서 개인 데이터의 키 역할을 하는 동급생의 성을 오름차순으로 정렬하는 코드를 작성해야 했습니다. 나는 이것에 많은 시간을 보냈다. 하지만 그때 TreeMap 클래스 에 대해 알았다면 훨씬 더 빨리 작업을 완료했을 것입니다.

트리맵 이란 무엇입니까 ? 요소를 키-값 쌍으로 저장하고 키별로 정렬하는 사전과 유사한 데이터 구조입니다.

어디에서 어떻게 사용할 수 있습니까? 글쎄요, 같은 반 친구의 성을 가진 동일한 과제에 이상적이었을 것입니다. 값을 오름차순으로 저장해야 하는 경우 자체 정렬 알고리즘을 작성하는 대신 TreeMap을 만들고 그 안에 값을 입력하기만 하면 됩니다.

Integer 및 String 과 같은 유형을 오름차순으로 정렬합니다. 그러나 TreeMap 에 사용자 정의 유형을 넣으려면 클래스 인스턴스를 정렬하는 방법을 나타내는 compareTo() 메서드 를 구현하도록 클래스에서 Comparable 인터페이스를 구현해야 합니다.


public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

compareTo() 메서드를 재정 의하여 알파벳 역순으로 이름을 기준으로 값을 정렬합니다.


TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

값은 다음 순서로 저장됩니다.


Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

TreeMap 클래스는 NavigableMap 인터페이스를 구현하며 , 이는 SortedMap 인터페이스 를 확장합니다 . 이를 통해 TreeMap 클래스는 트리를 사용하여 정렬된 순서로 값을 저장할 수 있습니다.

Wikipedia에서 말했듯이 트리는 먼저 값을 비교한 후 노드에 데이터를 저장하는 자체 균형 이진 검색 구조입니다.

간단히 말해서 레드-블랙 트리는 값이 루트보다 크면 오른쪽 하위 트리에 값이 적으면 왼쪽 하위 트리에 값을 저장하는 데이터 구조입니다. 이 구현은 구조의 값을 매우 빠르게 조회할 수 있습니다.

레드-블랙 트리는 자체적으로 균형을 이루고 있으므로 각각의 새 값이 삽입될 때마다 구조가 변경됩니다. 먼저 추가된 값이 처음에는 루트로 간주되지만 균형 조정 과정에서 다른 값이 루트가 될 수 있습니다.

자, 이제 TreeMap 이 무엇이고 어떻게 작동하는지 알았습니다 .

TreeMap은 Comparable 인터페이스를 구현하고 compareTo() 메서드를 재정의 하는 클래스의 객체만 저장할 수 있음 을 기억하십시오 .

하지만 다양한 라이브러리에서 로드된 타사 클래스를 사용하고 있고 그 안에 Comparable을 구현할 수 없다면 어떻게 될까요? 이에 대한 해결책이 있습니다. 자신의 Comparator 를 작성하십시오 .

Comparator 는 compare() 메서드가 있는 인터페이스입니다. 이를 사용하여 개체를 비교하고 TreeMap 에 저장할 수 있습니다 .


Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

이 예제에서는 사용자 지정 Comparator를 만들고 TreeMap 을 클래스에 전달했습니다 .

Java 8부터 람다 식을 사용하여 작성할 수 있습니다.


TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

즉, TreeMap 에 값을 저장하려면 정렬 방법을 지정해야 합니다. 이를 수행하는 두 가지 방법이 있습니다. Comparable을 구현하거나 자신의 Comparator를 구현합니다 .

하지만 null을 TreeMap 에 키로 넣어야 한다면 어떻게 해야 할까요 ? HashMap을 사용 하면 이 작업을 수행할 수 있습니다. 예, 하지만 TreeMap은 이를 어떻게 처리합니까?


TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

이 코드를 실행하면 오류가 발생합니다.

java.base/java.util.TreeMap.put(TreeMap.java:561)에서 스레드 "main" java.lang.NullPointerException의 예외

문제는 내부적으로 TreeMap 클래스가 compareTo() 메서드를 사용하여 값을 비교한다는 것입니다 . 확실히 null 값을 전달할 수 있으며 코드가 컴파일됩니다. 그러나 런타임에 메서드가 null 값 에서 호출되어 NullPointerException이 발생하기 때문에 오류가 발생합니다.

HashMap과 TreeMap의 비교

TreeMap 과 달리 HashMap에서는 null 을 키로 저장할 수 있습니다 . 구조에는 모든 null 키에 대한 특정 위치가 있습니다. HashMap은 해시 값을 기반으로 이동하는 위치를 결정하고 비교가 필요하지 않은 해시 값을 계산하기 때문에 null 키를 저장할 수 있습니다 . 따라서 모든 null 키에는 제자리가 있습니다.

이제 값을 정렬된 순서로 저장해야 할 때 무엇을 사용해야 하는지, 정렬 규칙을 설정하는 방법을 알게 되었습니다.

﻿TreeMap 컬렉션 소개

HashMap과 TreeMap의 비교

TreeMap 컬렉션 소개