Java의 TreeMap 기능

이 기사를 읽고 있다면 지도 인터페이스 와 그 사용법에 익숙할 것입니다. 그렇지 않다면 여기로 가세요. 오늘은 TreeMap의 구현 기능에 대해 이야기하고, 보다 구체적으로 HashMap 과 어떻게 다른지 , 올바르게 사용하는 방법에 대해 이야기하겠습니다.

TreeMap, HashMap 및 LinkedHashMap 비교

Map 인터페이스 의 가장 일반적으로 사용되는 구현은 HashMap 입니다 . 사용하기 쉽고 데이터에 대한 빠른 액세스를 보장하므로 대부분의 작업에 가장 적합합니다. 전부는 아니지만 대부분입니다. 때로는 데이터를 탐색할 수 있는 기능을 갖춘 구조화된 형식으로 데이터를 저장해야 하는 경우도 있습니다. 이 경우에는 Map 인터페이스의 또 다른 구현인 TreeMap 이 도움이 됩니다 . TreeMap은 SortedMap 에서 상속되고 Map 인터페이스 에서 상속되는 NavigableMap 인터페이스를 구현합니다 . NavigableMap 및 SortedMap 인터페이스를 구현 함으로써 TreeMap은 HashMap이 제공하지 않는 추가 기능을 얻지 만 이는 성능 측면에서 대가를 치르게 됩니다. LinkedHashMap 클래스 도 있는데 , 이 클래스를 사용하면 추가된 순서대로 특정 순서로 데이터를 저장할 수 있습니다. 이 세 클래스 간의 차이점을 이해하는 데 도움이 되도록 다음 표를 살펴보세요. 보시다시피, 이 클래스들은 공통점이 많지만 몇 가지 차이점도 있습니다. 클래스 TreeMap는 가장 다기능이지만 항상 null키로 저장할 수는 없습니다. 또한 TreeMap 요소에 대한 액세스 시간이 가장 길어집니다. 따라서 데이터를 정렬된 형태로 저장할 필요가 없다면 HashMap또는 를 사용하는 것이 좋습니다 LinkedHashMap.

붉은 흑단 나무

아마도 눈치채셨겠지만 내부적으로는 TreeMap레드-블랙 트리라는 데이터 구조를 사용합니다. 데이터가 저장되는 순서를 보장하는 것은 이 구조의 데이터 저장입니다. 이 나무는 무엇입니까? 그것을 알아 봅시다! 숫자-문자열 쌍을 저장해야 한다고 상상해 보세요. 숫자 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101이 열쇠가 됩니다. 기존 목록에 데이터를 저장하고 키가 101인 요소를 찾아야 하는 경우 이를 찾으려면 13개 요소를 모두 반복해야 합니다. 13개 요소의 경우 이는 중요하지 않습니다. 백만 개 요소를 사용하면 큰 문제가 발생합니다. 이러한 문제를 해결하기 위해 프로그래머는 약간 더 복잡한 데이터 구조를 사용합니다. 그러므로 레드블랙트리를 만나보세요!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

필요한 요소에 대한 검색은 트리의 루트(우리의 경우 61)부터 시작됩니다. 다음으로 필요한 값과 비교가 이루어집니다. 값이 작으면 왼쪽으로 이동하고, 값이 크면 오른쪽으로 이동합니다. 이는 필요한 값을 찾거나 값이 있는 요소 null(나무 잎)에 도달할 때까지 발생합니다. 빨간색과 검정색은 나무를 더 쉽게 탐색하고 균형을 잡을 수 있도록 사용됩니다. 레드-블랙 트리를 구축할 때 항상 따라야 하는 규칙이 있습니다.

• 뿌리는 검은 색이어야합니다.
• 나무의 잎은 검은색이어야 합니다.
• 빨간색 노드에는 두 개의 검정색 하위 노드가 있어야 합니다.
• 블랙 노드는 모든 하위 노드를 가질 수 있습니다.
• 노드에서 리프까지의 경로에는 동일한 수의 검정색 노드가 포함되어야 합니다.
• 나뭇잎 대신 새 노드가 추가됩니다.

규칙 3, 4, 5를 함께 보면 색상 지정 노드가 트리 탐색 속도를 높이는 방법을 이해할 수 있습니다. 검은색 노드를 통과하는 경로는 항상 빨간색 노드를 통과하는 경로보다 짧습니다. 따라서 트리의 전체 크기는 블랙 노드의 수에 따라 결정되며, 이 크기를 "블랙 높이"라고 합니다. 레드-블랙 트리는 다양한 프로그래밍 언어로 구현됩니다. 인터넷에는 Java 구현이 많이 있으므로 오랫동안 다루지는 않겠지만 계속해서 기능에 대해 알아볼 것입니다 TreeMap.

SortedMap 및 NavigableMap 인터페이스에서 파생된 메서드

마찬가지로 인터페이스를 구현합니다 HashMap. 이는 인터페이스 에 필요한 모든 메소드가 있음을 의미합니다 . 그러나 또한 인터페이스를 구현 하고 추가 기능을 얻습니다. — 정렬된 데이터 세트와 관련된 메소드를 확장하고 추가하는 인터페이스 :TreeMapMapTreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

• firstKey(): 맵의 첫 번째 요소의 키를 반환합니다.
• lastKey(): 마지막 요소의 키를 반환합니다.
• headMap(K end): 처음부터 키가 있는 요소까지 현재 요소의 모든 요소를 ​​포함하는 맵을 반환합니다 end.
• tailMap(K start): 요소에서 시작하여 start끝으로 끝나는 현재 요소의 모든 요소를 ​​포함하는 맵을 반환합니다.
• subMap(K start, K end)start: 요소로 시작하여 키가 있는 요소로 끝나는 현재 요소의 모든 요소를 ​​포함하는 맵을 반환합니다 end.

NavigableMapSortedMap— 지도 요소 간 탐색을 위한 메소드를 확장하고 추가하는 인터페이스 :

• firstEntry(): 첫 번째 키-값 쌍을 반환합니다.
• lastEntry(): 마지막 키-값 쌍을 반환합니다.
• pollFirstEntry(): 첫 번째 쌍을 반환하고 제거합니다.
• pollLastEntry(): 마지막 쌍을 반환하고 제거합니다.
• ceilingKey(K obj): 키 obj보다 크거나 같은 가장 작은 키 k를 반환합니다. 해당 키가 없으면 null을 반환합니다.
• floorKey(K obj): 키 obj보다 작거나 같은 가장 큰 키 k를 반환합니다. 해당 키가 없으면 null을 반환합니다.
• lowerKey(K obj): 키 obj보다 작은 가장 큰 키 k를 반환합니다. 해당 키가 없으면 null을 반환합니다.
• higherKey(K obj): 키 obj보다 큰 가장 작은 키 k를 반환합니다. 해당 키가 없으면 null을 반환합니다.
• ceilingEntry(K obj): 천장키(K obj) 메서드와 유사하지만 키-값 쌍(또는 null)을 반환합니다.
• floorEntry(K obj): FloorKey(K obj) 메소드와 유사하지만 키-값 쌍(또는 null)을 반환합니다.
• lowerEntry(K obj): lowerKey(K obj) 메소드와 유사하지만 키-값 쌍(또는 null)을 반환합니다.
• higherEntry(K obj): highKey(K obj) 메소드와 유사하지만 키-값 쌍(또는 null)을 반환합니다.
• descendingKeySet(): 역순으로 정렬된 모든 키를 포함하는 NavigableSet를 반환합니다.
• descendingMap(): 역순으로 정렬된 모든 쌍을 포함하는 NavigableMap을 반환합니다.
• navigableKeySet(): 저장 순서대로 모든 키를 포함하는 NavigableSet 객체를 반환합니다.
• headMap(K upperBound, boolean incl): 처음부터 upperBound 요소까지 쌍을 포함하는 맵을 반환합니다. incl 인수는 upperBound 요소가 반환된 맵에 포함되어야 하는지 여부를 지정합니다.
• tailMap(K lowerBound, boolean incl): 기능은 이전 방법과 유사하며 lowerBound부터 끝까지의 쌍만 반환됩니다.
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): 이전 방법과 마찬가지로 lowerBound에서 upperBound까지의 쌍이 반환되며 lowIncl 및 highIncl 인수는 새 맵에 경계 요소를 포함할지 여부를 지정합니다.

구현 자체에는 TreeMap우리에게 익숙한 생성자 외에 비교기의 인스턴스를 허용하는 하나가 더 추가됩니다. 이 비교기는 요소가 저장되는 순서를 담당합니다.

TreeMap 사용 예

이러한 풍부한 추가 방법은 불필요해 보일 수 있지만 처음에 생각했던 것보다 훨씬 더 유용한 것으로 판명되는 경우가 많습니다. 이 예를 여러분과 함께 살펴보겠습니다. 우리가 대기업의 마케팅 부서에서 일하고 있고 광고를 보여주고 싶은 사람들의 데이터베이스가 있다고 상상해 보세요. 여기에는 두 가지 뉘앙스가 있습니다.

• 우리는 각 사람에 대한 노출수를 추적해야 합니다.
• 미성년자에게 광고를 표시하는 알고리즘은 다릅니다.

Person개인에 대해 사용할 수 있는 모든 정보를 저장하는 클래스를 만들어 보겠습니다 .

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

우리는 클래스에 로직을 구현합니다 Main:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Main우리가 만든 클래스에서 TreeMap는 key특정 인물이고 는 value이번 달 광고 노출 횟수입니다. 생성자에는 사람들을 연령별로 정렬하는 비교기를 전달합니다. 임의의 값 으로 채웁니다 map. 이제 미니 데이터 저장소의 첫 번째 성인에 대한 참조를 가져와야 합니다. Stream API를 사용하여 이를 수행합니다. 그런 다음 두 개의 독립적인 지도를 얻어 광고를 표시하는 메서드에 전달합니다. 이 문제를 해결할 수 있는 방법은 매우 많습니다. 수업의 다양한 방법을 TreeMap통해 모든 취향에 맞는 솔루션을 만들 수 있습니다. 개발 환경의 문서나 힌트를 언제든지 사용할 수 있으므로 모두 기억할 필요는 없습니다. 그게 다야! 이제 수업 내용이 여러분에게 명확해졌기를 바랍니다 TreeMap. 실제 문제를 해결하는 데 이 수업을 정확하게 적용할 수 있기를 바랍니다.