정렬된 지도

SortedMap

이 학습에서는 SortedMap 인터페이스를 학습합니다 . 우리는 이 인터페이스 에 나타나는 새로운 메서드와 SortedMap 의 한 구현인 TreeMap 의 기능, 구현 간의 차이점, HashMap 과 비교한 장점을 살펴볼 것입니다 .

지도의 계층 구조가 어떻게 생겼는지 봅시다. SortedMap 인터페이스와 TreeMap 구현 에 특별한 주의를 기울이십시오 . 오늘 우리의 초점은 다음과 같습니다.

SortedMap 인터페이스 는 Map 인터페이스를 확장합니다 . 두 가지 모두 정렬된 값을 저장하고 사용하는 유사한 기능을 설명하기 때문에 여러 가지 면에서 SortedSet ( Set 을 확장함 ) 와 유사합니다 .

SortedSet은 <TValue>와 함께 작동하고 저장하지만 SortedMap은<TKey, TValue>쌍을 저장합니다. 모든 요소를 ​​키의 오름차순으로 저장하는 맵입니다.

SortedMap 인터페이스 는 Map 을 확장합니다 . 다음 메소드를 추가합니다.

TreeMap 클래스

TreeMap 클래스 는 SortedMap 인터페이스 의 구현입니다 . 즉, TreeMap은 SortedMap 에 의해 추가된 모든 메소드 와 Map 인터페이스의 표준 메소드를 구현합니다.

다음과 같은 생성자를 사용하여 TreeMap 개체를 만들 수 있습니다 .

• TreeMap() : 트리로 구현된 빈 맵을 생성합니다.

• TreeMap(Map<? extends TKey, ? extends TValue> map) : 트리를 생성하고 입력 맵의 모든 요소를 ​​추가합니다.

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : 트리를 생성하고 입력 정렬 맵에서 모든 요소를 ​​추가합니다.

• TreeMap(Comparator<? super TKey> comparator) : 빈 트리를 생성합니다. 비교기는 이후에 추가되는 모든 요소를 ​​정렬하는 데 사용됩니다.

여기서 TKey 는 저장된 쌍의 키 유형이고 TValue 는 TreeMap 에 저장된 쌍의 값 유형입니다 .

비교기는 SortedMap / TreeMap 에서 매우 중요합니다. 지도를 정렬하거나 정렬하기 위한 규칙을 설정합니다. 비교기를 제공하지 않으면 SortedMap 을 만들 때 키의 자연스러운 순서가 사용 됩니다 .

TreeMap에 요소 추가

요소는 put() 메서드를 사용하여 쌍으로 맵에 추가됩니다 . 키는 첫 번째 인수로 전달되고 값은 두 번째로 전달됩니다. 예를 들어 학생 및 성적 목록을 생성한다고 가정합니다.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

결과:

키-값 쌍을 추가할 때 키가 이미 컬렉션에 있으면 이전 값이 새 값으로 대체됩니다. 이 동작은 ("Oliver", 3) 및 ("Oliver", 5) 와 같은 동일한 키를 가진 두 쌍의 예에서 설명됩니다 .

우리가 만든 비교기 가 있는 예를 살펴보겠습니다 . 키 문자열의 길이로 정렬된 요소를 저장한다고 가정합니다. 키 길이가 같으면 알파벳순으로 정렬합니다(문자열의 자연스러운 순서).

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

결과 시퀀스는 다음과 같습니다.

이 동작은 인덱스가 숫자 대신 단어( String ) 인 정렬된 배열 또는 목록과 같은 TreeMap 을 만듭니다.

TreeMap 클래스의 SortedMap 메서드

1. 첫 번째 학생의 키를 가져와야 하는 경우 firstKey () 메서드를 사용할 수 있습니다.

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   결과: 첫 번째 키 → Anthony

2. 마지막 학생의 키를 가져와야 하는 경우 lastKey () 메서드를 사용할 수 있습니다.

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   결과: 마지막 키 → Jeff

3. 키 " Sara " 를 사용하여 개체 뒤에 오는 모든 개체를 가져옵니다 .

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   결과: tailMap: {Sara=5, Jeff=4}

4. 키가 " Nick " 인 개체 앞에 오는 모든 개체 가져오기 :

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   결과: headMap: {Anthony=5}

5. " Oliver " 키가 있는 개체 뒤에 오는 모든 개체를 가져오고 " Sara " 키가 있는 개체 앞에 오는 모든 개체를 가져옵니다 .

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   결과: 하위 맵: {Oliver=5, Roxy=5}

HashMap과 SortedMap/TreeMap의 비교

요소가 정렬되고 저장되는 방법에 대해 이야기해 보겠습니다.

• HashMap은 반복할 때 순서를 보장하지 않기 때문에 새 요소가 추가되면 순서가 완전히 바뀔 수 있습니다.

• TreeMap 에서 순서는 compareTo() 메서드(또는 우리가 제공하는 Comparator )에 따른 키의 "자연 순서"를 기반으로 합니다. 또한 TreeMap이 이 정렬 순서에 의존하는 메서드를 포함하는 SortedMap 인터페이스를 구현한다는 사실을 잊지 마십시오 .

이제 성능과 속도를 고려합니다.

• HashMap 은 해싱 키를 기반으로 하는 맵입니다. O(1), 상수 시간에 요소를 삽입하고 가져올 수 있습니다이를 지원하려면 키가hashCode()및equals() 를.

• TreeMap 은 트리 기반 맵입니다. 삽입 및 가져오기 작업에는 로그 시간, 즉O(log n)이는 맵의 요소 수에 따라 다릅니다. 이는 요소가 키 또는 외부 비교기에 의해 제공되는 일종의 비교 메커니즘을 갖기 위해 필요합니다. 이 메커니즘은 반복 순서를 결정합니다.

이러한 요소는 어떤 컬렉션을 언제 사용할지 결정하는 데 도움이 됩니다.

특정 순서로 값을 저장해야 하는 경우 선택은 명백합니다. SortedMap 이 필요 합니다 . HashMap 보다 약간 느리지만 중요한 작업을 수행합니다.

앞에서 언급했듯이 SortedMap은 값이 추가된 시점에 관계없이 맵의 첫 번째(또는 마지막) 키, 값 또는 키-값 쌍을 제공할 수 있습니다. HashMap 구현 은 이것을 할 수 없습니다.

예를 들어 키(학생 이름)와 값(성적)이 있는 지도를 생각해 보십시오. 목록을 알파벳 역순으로 작업하고 싶다고 가정해 보겠습니다.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

예제는 HashMap 을 사용하면 작업이 더 복잡해짐을 보여줍니다. HashMap은 저장 순서나 맵에서 요소를 가져오는 순서를 보장하지 않기 때문입니다.