[자료구조] Map 인터페이스

우선, 글을 작성하기 전 이 글의 모든 내용은 김영한님의 JAVA 강의를 바탕으로 함을 알립니다.

💡Map 인터페이스

Map은 키-값쌍을 저장하는 자료구조이다.

• Key는 중복이 불가능하다. Key를 통해 Value를 빠르게 검색이 가능하다
• Value는 중복이 가능하다.
• Map은 순서를 허용하지 않는다

Map 인터페이스

◻️ HashMap

• 가장 많이 사용
• 해시 인덱스를 통해 요소를 저장
  • key값은 해시함수를 통해 해시 인덱스로 변환되고 데이터 저장, 삭제에 사용됨
• 일반적으로 O(1) 성능을 가짐 (해시 충돌이 많으면 최악의 경우 O(n))

• 주의점!
  • HashSet과 동일하게 해시코드로 변형이 되어야 하는 참조형은 반드시 hashCode()와 equals()를 오버라이딩하여 재정의 해주어야 한다. 따라서, HashMap의 Key로 사용되는 객체는 반드시 hashCode() , equals()를 반드시 구현해야 한다

◻️ LinkedHashMap

• Node를 도입하여 LinkedList를 통해 입력된 요소의 순서를 유지
• 상대적으로 HashMap보다 무거움

◻️ TreeMap

• 레드-블랙 트리 기반으로 정렬된 순서를 가짐
• 모든 key는 Comparator(비교자)에 의해 정렬됨
• get, move, remove는 O(logN)의 성능을 가짐

Set과 Map의 관계

Map의 특징은 중복을 허용하지 않고, 순서를 보장하지 않는다는 것이다. 이 특성은 Set의 특성과 동일하다. 즉, Map의 Key가 결국 Set과 동일하게 작동다는 것을 의미하고, 이는 결국 Set은 Map에서 value부분만 제거된 것이라고 봐도 무방하다. 따라서 다음과 같은 유의미한 상관관계를 갖는다

• HashSet -> HashMap
• LinkedHashSet -> LinkedHashMap
• TreeSet -> TreeMap