Java에서 TreeMap의 내부 작동-java지도 시간-php.cn

Java에서 TreeMap의 내부 작동

WBOY

풀어 주다： 2023-08-26 11:41:16

앞으로

663명이 탐색했습니다.

TreeMap은 NavigableMap 인터페이스를 구현하는 Java Collection Framework의 클래스입니다. 이는 맵의 요소를 트리 구조에 저장하고 키-값 쌍을 정렬된 순서로 저장하는 효율적인 대안을 제공합니다. TreeMap은 내부적으로 레드-블랙 트리를 사용합니다. 자체 균형 이진 검색 트리인 TreeMap은 요소의 정렬 순서를 유지할 수 있도록 Comparable 인터페이스 또는 사용자 정의 Comparator를 구현해야 합니다. 그렇지 않으면 이 기사에서는 java.lang.ClassCastException이 발생하게 됩니다. TreeMap이 Java에서 내부적으로 작동하는 방식.

Java에서 TreeMap의 내부 작동 방식

TreeMap의 내부 작동 방식을 이해하려면 TreeMap이 요소를 저장하는 데 사용하는 레드-블랙 트리 알고리즘에 대한 개요가 필요합니다.

레드 블랙 트리와 TreeMap의 관계

레드-블랙 트리는 다음과 같은 속성을 갖는 자체 균형 이진 검색 트리입니다.

각 노드에는 빨간색이나 검은색으로 표시되는 추가 비트가 포함되어 있습니다. 이 색상은 나무의 균형을 유지하는 데 사용됩니다.
루트 노드의 색상은 항상 검은색입니다.
빨간색 노드는 이웃과 같은 색상의 다른 노드를 가질 수 없습니다.
루트 노드부터 빈 노드까지 모든 경로의 블랙 노드 수가 동일해야 합니다.

Java에서 TreeMap의 내부 작동

이제 TreeMap의 구조를 살펴보겠습니다.

Java에서 TreeMap의 내부 작동

TreeMap에 요소를 추가하면 두 번째 요소부터 현재 항목의 키가 이전 항목보다 큰지 작은지 확인합니다. 왼쪽에 추가되고 더 큰 값이 상위 항목 오른쪽에 추가됩니다.

TreeMap 생성자

프로그램에서 TreeMap 컬렉션을 사용하려면 먼저 TreeMap 클래스의 인스턴스를 만들어야 합니다. 이를 위해 Java는 다음 생성자를 제공합니다.

TreeMap(): 빈 TreeMap 컬렉션을 생성합니다.
TreeMap(Map mapInstance): 다른 맵의 항목을 사용하여 트리 맵을 만들 수 있습니다.
TreeMap(Comparator comparatorInstance): 비교기를 사용하여 정렬된 빈 트리 맵을 생성할 수 있습니다.
TreeMap(SortedMap sortedmapInstance): 정렬된 맵의 항목으로 트리 맵을 만들 수도 있습니다.

위에서 논의한 사항을 더 잘 이해할 수 있도록 몇 가지 예를 살펴보겠습니다.

예

다음 예에서는 빈 TreeMap을 만든 다음 'put()' 메서드를 사용하여 일부 요소를 여기에 저장합니다. for-each 루프를 사용하여 세부 정보를 인쇄합니다. 결과는 정렬된 순서로 표시됩니다.

import java.util.*;
public class Example1 {
   public static void main(String[] args) {
      // creating a TreeMap
      TreeMap<String, Integer> TrMap = new TreeMap<>();
      // Adding elements in the map
      TrMap.put("Kurti", 4000);
      TrMap.put("Shirt", 3000);
      TrMap.put("TShirt", 1500);
      TrMap.put("Watch", 2000);
      TrMap.put("Perfume", 2500);
      // printing the details of map 
      System.out.println("Elements of the map: ");
      // iterating through the map
      for (String unKey : TrMap.keySet()) {
         // printing details of each node
         System.out.println("Item: " + unKey + ", Price: " + 
TrMap.get(unKey));
      }
      String frstKey = TrMap.firstKey(); // accessing first key
      String lstKey = TrMap.lastKey(); // accessing last key
      System.out.println("Accessing name of first key in Map: " + 
frstKey);
      System.out.println("Accessing name of last key in Map: " + 
lstKey);
   }
}

로그인 후 복사

출력

Elements of the map: 
Item: Kurti, Price: 4000
Item: Perfume, Price: 2500
Item: Shirt, Price: 3000
Item: TShirt, Price: 1500
Item: Watch, Price: 2000
Accessing name of first key in Map: Kurti
Accessing name of last key in Map: Watch

로그인 후 복사