• key, value 쌍으로 이루어진 데이터를 담는 container
• map by tree
• 특징 :
  • 정렬된 형태를 가지고 있다. (key를 기반으로 정렬됨)
  • 모든 key는 고유(중복된 key가 존재할 수 없음)
    • 중복된 key가 들어오면 덮어씌워짐
• Value를 기반으로 정렬 불가
• vlaue를 통해 key 알 수 없음
• 언제 사용하나?
  • 데이터를 정렬된 형태로 관리해야 할 때
  • 특정 조건을 만족하는 데이터를 빠르게 찾아내야 할 때

Binary Search Tree ⇒ O(N)

Balanced BST → Red-Black Tree 구조 : 모든 메소드가 O(log(N))으로 보장되어서 돌아간다.

=⇒ 삽입, 접근, 삭제 모드 O(log(N))

• 조건부 탐색

  • lowerKey

    : Returns the greatest key strictly less than the given key, or null if there no such key.

    —> 매개변수로 주어진 key보다 [작은] (미만 <) 가장 큰 key를 return

  • floorKey

    : Returns the greatest key less than or equal to the given key, or null if there no such key.

    —> 매개변수로 주어진 key보다 [작거나 같은] (이하 <=) 가장 큰 key를 return

  • higherKey

    : Returns the least key strictly greater than the given key, or null if there no such key.

    —> 매개변수로 주어진 key보다 [큰] (초과 >) 가장 작은 key를 return

  • ceilingKey

    : Returns the least key greater than or equal to the given key, or null if there no such key.

    —> 매개변수로 주어진 key보다 [크거나 같은] (이상 >=) 가장 작은 key를 return

  • lastKey

    : 지금 상황에서 가장 큰 Key

  • fisrtKey

    : 지금 상황에서 가장 작은 Key

  • key만 필요할 때도 있지만 key에 연결된 value를 써야하는 경우

    System.out.println(tm.get(tm.firstKey()));

• 탐색을 위한 Iterator 사용 방법 + set

  Set<Map.Entry<String, Integer>> s = tm.entrySet();
  Iterator it = s.iterator();
  while(it.hasNext()){
  	// iterator를 쓰면 it.next() => Object타입
  	Map.Entry<String, Integer> ent = (Map.Entry<String, INteger>)it.next();
  	System.out.println(ent.getKey() + " " + ent.getValue());
  }
  

  for (Map.Entry<String, Integer> ent : tm.entrySet()) {
  	System.out.println(ent.getKey() + " " + ent.getValue());
  }
  

• subMap : EntrySet()으로 가지고 오는거랑 속도 별 차이 없는데 간편

  • sub - map ⇒ 전체 TreeMap의 일부분만 볼 수가 있음 —> 개수 체크
  • 쉽게 할 수 있다. → 동작 속도가 빠른건 아님
  • tm.submap(from, to) ← default로 from은 포함, to는 미포함

  System.out.println(tm2.subMap(1, 500).size());

  • tm.subMap(from, bool, to, bool) ← bool == true : 포함, bool == false : 불포함

  System.out.println(tm2.subMap(1, true, 500, true).size());

• key를 사용자 class로 활용하는 방법 : custom class key

  TreeMap<Node, Integer> tmm = new TreeMap<>();

  ⇒ Node class의 경우는 compareTo로 비교 불가능하기 때문에 에러 발생

  ⇒ 직접 만들어줘야함.

  class Node implements Comparable <Node> {
  	int y;
  	int x;
  	Node(int y, int x) {
  		this.y = y;
  		this.x = x;
  	}
  	@Override
  	public int compareTo(Node o) {
  		if (y == o.y)
  			return x- o.x;
  		return y - o.y;
  	}
  

  TreeMap에서 key 정렬은 무조건 오름차순

• 최적화

  • 모든게 logN으로 돌아간다

    → 특정 상황에 따라 더 느릴수도 있음

    → 같은 logN이여도 절대적인 속도는 다름

  • TreeMap은 [느린] logN에 속함

  • Map에서는 최대한 key를 Integer로 쓰는 것을 권장 → String이 시간 더 오래 걸림

  • TreeMap 은 내부적으로 compareTo로 비교하면서 밸런스 유지 및 접근

• 유형
  • ~Key로 빠른 탐색
  • 스케줄링