Java의 트리맵

이 기사를 읽고 있다면 지도 인터페이스와 적절하게 적용할 수 있는 위치에 대해 잘 알고 있을 것입니다. 그렇지 않다면 여기로 오십시오 . 오늘 우리는 Java TreeMap의 구현 기능, 특히 HashMap과 어떻게 다른지, 올바르게 사용하는 방법에 대해 이야기할 것입니다.

TreeMap, HashMap 및 LinkedHashMap 비교

Map 인터페이스의 가장 많이 사용되는 구현은 HashMap입니다. 사용하기 쉽고 데이터에 대한 빠른 액세스를 보장하므로 대부분의 문제를 해결하는 데 가장 적합합니다. 대부분이지만 전부는 아닙니다. 때로는 구조화된 방식으로 데이터를 저장하고 탐색할 수 있어야 합니다. 이 경우 Map 인터페이스(TreeMap)의 또 다른 구현이 도움이 됩니다. TreeMap은 SortedMap을 상속하는 NavigableMap 인터페이스를 구현하고 Map 인터페이스를 상속합니다. NavigableMap 및 SortedMap 인터페이스를 구현함으로써 TreeMap은 HashMap에서 사용할 수 없는 추가 기능을 받지만 성능 측면에서 비용을 지불합니다. LinkedHashMap 도 있습니다.또한 특정 순서(지도에 데이터를 추가하는 순서)로 데이터를 저장할 수 있습니다. 이 세 가지 클래스의 차이점 을 이해하려면 다음 표를 살펴보십시오. 보시다시피 이러한 클래스에는 공통점이 많지만 몇 가지 차이점도 있습니다. TreeMap 클래스가 가장 다재다능하지만 항상 null을 키로 저장할 수는 없습니다. 또한 TreeMap의 요소에 액세스하는 데 가장 오랜 시간이 걸립니다. 따라서 정렬된 순서로 데이터를 저장할 필요가 없다면 HashMap 또는 LinkedHashMap 을 사용하는 것이 좋습니다 .

레드 블랙 트리

내부적으로 TreeMap은 red-black 트리라는 데이터 구조를 사용합니다. 이 구조에 데이터를 저장하는 것이 바로 데이터 정렬을 제공하는 것입니다. 그렇다면 이것은 어떤 나무일까요? 알아 봅시다! 숫자-문자열 쌍을 저장해야 한다고 상상해 보십시오. 숫자 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101이 키가 됩니다. 기존 목록에 데이터를 저장하고 키가 101인 요소를 찾아야 하는 경우 이를 찾으려면 13개 요소를 모두 거쳐야 합니다. 13개 요소의 경우 이것은 큰 문제가 아니지만 백만 개로 작업하면 큰 문제가 발생합니다. 이러한 문제를 해결하기 위해 프로그래머는 약간 더 복잡한 데이터 구조를 사용합니다. 레드 블랙 트리가 무대에 들어가는 곳입니다!요소 검색은 트리의 루트(이 경우 61)에서 시작됩니다. 그런 다음 노드 값을 찾고 있는 값과 비교합니다. 값이 작으면 왼쪽으로 이동합니다. 더 크면 오른쪽으로 이동합니다. 이 프로세스는 원하는 값을 찾거나 값이 null 인 요소 (트리의 잎)를 만날 때까지 반복됩니다. 빨간색과 검은색은 트리 탐색 및 균형 조정을 단순화하는 데 사용됩니다. 레드-블랙 트리를 구축할 때 항상 준수해야 하는 규칙이 있습니다.

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

규칙 3, 4, 5를 함께 고려하면 노드 색상이 어떻게 트리를 더 빠르게 탐색할 수 있는지 이해할 수 있습니다. 검은색 노드를 통과하는 경로는 항상 빨간색 노드를 통과하는 경로보다 짧습니다. 따라서 트리의 전체 크기는 "블랙 높이"라고 하는 블랙 노드의 수에 의해 결정됩니다. 레드-블랙 트리 데이터 구조는 다양한 프로그래밍 언어로 구현됩니다. 인터넷에는 많은 Java 구현이 있으므로 여기에서 머뭇거리지 않겠습니다. 대신 계속해서 TreeMap의 기능에 대해 알아보겠습니다.

SortedMap 및 NavigableMap 인터페이스에서 오는 메서드

HashMap과 마찬가지로 TreeMap은 Map 인터페이스를 구현합니다. 즉, TreeMap에는 HashMap에 존재하는 모든 메서드가 있습니다. 그러나 TreeMap은 SortedMap 및 NavigableMap 인터페이스도 구현하므로 이들로부터 추가 기능을 얻습니다. SortedMap은 Map을 확장 하고 정렬된 데이터 세트와 관련된 메서드를 추가하는 인터페이스입니다 .

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

NavigableMap 은 SortedMap을 확장하고 지도 요소 간 탐색을 위한 메서드를 추가하는 인터페이스입니다.

• 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) : ceilingKey(K obj) 메서드와 유사하며 키-값 쌍(또는 null)만 반환합니다.
• floorEntry(K obj) : floorKey(K obj) 메서드와 유사하며 키-값 쌍(또는 null)만 반환합니다.
• lowerEntry(K obj) : lowerKey(K obj) 메서드와 유사하며 키-값 쌍(또는 null)만 반환합니다.
• higherEntry(K obj) : higherKey(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에는 비교기의 인스턴스를 허용하는 또 다른 생성자가 있습니다. 이 비교자는 요소가 저장되는 순서를 담당합니다.

트리맵의 예

이 풍부한 추가 메서드는 불필요해 보일 수 있지만 언뜻 생각하는 것보다 훨씬 더 유용한 것으로 판명되었습니다. 다음 예제를 함께 살펴보겠습니다. 우리가 대기업의 마케팅 부서에서 일하고 있고 광고를 보여주고 싶은 사람들의 데이터베이스가 있다고 상상해 보십시오. 명심해야 할 두 가지 세부 사항이 있습니다.

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

각 개인에 대한 모든 관련 정보를 저장할 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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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을 만듭니다 . 생성자에 연령별로 사람을 정렬하는 비교기를 전달합니다. 임의의 값으로 맵을 채웁니다. 이제 작은 데이터 저장소에서 첫 번째 성인에 대한 참조를 얻고 싶습니다. Stream API를 사용하여 이 작업을 수행합니다. 그런 다음 광고를 표시하는 메서드에 전달하는 두 개의 별도 지도를 얻습니다. 우리가 이 작업을 수행할 수 있었던 많은 방법이 있습니다. TreeMap 클래스의 메소드 무기고를 사용하면 모든 필요에 맞는 맞춤형 솔루션을 만들 수 있습니다. 항상 IDE에서 문서나 팁을 사용할 수 있으므로 모두 기억할 필요는 없습니다. 배운 내용을 보강하려면 Java 과정에서 비디오 강의를 시청하는 것이 좋습니다. 지금은 여기까지입니다! 이제 TreeMap 클래스가 명확해지고 실제 코딩 작업을 해결하는 데 적절하게 적용되기를 바랍니다.