24. 자바랭 다음으로 많이 쓰는 애들은 컬렉션 - Part3(Map)

24-1 Map이란?

• 키와 값이 1:1로 매칭된 자료구조
  • 키는 중복되면 안 된다.

24-2 Map을 구현한 주요 클래스들을 살펴보자

• HashMap, TreeMap, LinkedHashMap을 주로 사용
• HashTable
  • Map을 구현한 클래스지만 다른 구현 클래스들과 특징이 다름

HashMap, TreeMap, LinkedHashMap	HashTable
컬렉션 뷰 사용	Enumeration 객체를 통해 데이터 처리
데이터를 순환하여 처리 가능	데이터를 순환하여 처리 불가
이터레이션 도중 안전한 삭제 가능	기능 제공 X

• HashMap과 HashTable의 차이

기능	HashMap	HashTable
키나 값에 null 저장 가능 여부	O	X
쓰레드 안전	X	O

24-3 HashMap 클래스에 대해서 자세히 알아보자

• HashMap의 상속 관계

  • java.lang.Object
    • java.util.AbstractMap<K, V>
      • java.util.HashMap<K, V>

• HashMap에 담을 데이터의 사이즈를 예측할 수 있으면 생성 시에 initialCapacity를 지정해 주어 성능 향상하자.

• 키의 hashCode() 값으로 버킷(List)을 찾고 버킷에 데이터가 여러개 있으면 equals()를 사용해 동일한 값이 있는지 찾는다.

24-4 HashMap 객체에 값을 넣고 확인해보자

• 없는 키로 값을 꺼내려 하면 null 리턴

24-5 HashMap 객체의 값을 확인하는 다른 방법들을 알아보자

• keySet(), values(), entrySet(), containsKey(), containsValue()

24-6 정렬된 키의 목록을 원한다면 TreeMap을 사용하자

• TreeMap은 키를 정렬하여 저장한다.
  • TreeMap은 SortedMap을 구현하였기 때문
    • SortedMap을 구현한 클래스는 키를 모두 정렬하여야 한다.

24-7 Map을 구현한 Properties 클래스는 알아두면 편리하다

• Properties 클래스는 HashTable을 확장
• 시스템 속성을 담고 있음
• 자주 사용되는 키들

• 시스템 속성을 HashTable에 담지 않고 굳이 Properties 클래스를 따로 만들어서 담는 이유는 Properties가 제공하는 아래의 메소드들 때문이다.

24-8 자바의 자료 구조를 정리해보자

이분탐색

정의

• 결정 문제의 답이 이분적일 때 사용하는 탐색 방법
  • 결정 문제
    • 답이 Yes or No인 문제

결정 문제

• ex)
  • 배열 1, 5, 13, 18, 24, 28, 30, 33, 35, 38, 40에서 임의의 요소는 28 이상인가?

이분적

	1	5	13	18	24	28	30	33	35	38	40
28 이상인가?	F	F	F	F	F	T	T	T	T	T	T

• 위의 예시를 표로 나타냈는데 결정 문제에 대한 답이 24, 28을 기준으로 두 구간으로 나뉘는 것을 볼 수 있다.

치환

• 만약 정확히 28을 찾는 문제라면 28 이상인 요소들 중에서 가장 작은 요소를 찾으면 된다.
• 혹은 28 이하인 요소 중에서 가장 큰 요소를 찾아도 된다.

알고리즘

1. 결정 문제를 check(x)라고 할 때, check(lo) != check(hi)가 되도록 lo, hi 초기값 세팅.
2. while(lo + 1 < hi)동안 mid = (lo + hi) / 2일 때
   • check(mid) = check(lo)면 lo = mid;
   • check(mid) = check(hi)면 hi = mid;
3. lo + 1 = hi가 되면 while문 종료. lo와 hi 중 어느 것이 답인지 생각해보고 출력.

Reference

• 참고