[CS] 자료구조 : Java와 HashMap

✏️Map

Map인터페이스는 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용된다. 키는 중복될 수 없지만 값을 중복을 허용한다. 순서가 유지되지 않는다.

 

Map의 상속계층도

 

🔸Java -Map 주요 메서드

1. put(key, value): 지정된 키와 값의 쌍을 Map에 추가합니다. 만약 이미 동일한 키가 존재한다면 해당 키에 대응하는 값을 덮어씁니다.
2. get(key): 지정된 키에 대응하는 값을 반환합니다. 만약 해당 키가 존재하지 않는다면 null을 반환합니다.
3. remove(key): 지정된 키와 그에 대응하는 값을 Map에서 제거합니다. 제거된 값이 반환됩니다.
4. containsKey(key): 지정된 키가 Map에 존재하는지 여부를 확인합니다. 존재하면 true를, 그렇지 않으면 false를 반환합니다.
5. containsValue(value): 지정된 값이 Map에 존재하는지 여부를 확인합니다. 존재하면 true를, 그렇지 않으면 false를 반환합니다.
6. keySet(): Map의 모든 키를 Set으로 반환합니다. Set은 중복을 허용하지 않는 자료구조입니다.
7. values(): Map의 모든 값을 Collection으로 반환합니다. Collection은 중복을 허용하지만, 순서를 보장하지 않는 자료구조입니다.
8. size(): Map에 저장된 키-값 쌍의 개수를 반환합니다

 

🔸HashMap

• 해싱(hashing) + Map
  
  • 해시 함수를 사용하여 매우 빠른 검색과 삽입 속도를 제공한다.
  • 중복된 키를 허용하지 않아 동일한 키로 여러 번 put() 메서드를 호출하면 최신 값으로 덮어쓴다.
  • 순서를 보장하지 않는다. 순서가 중요하다면 LinkedHashMap을 사용하는 것이 좋다.
  • Null키와 Null 값을 허용하여 유연한 데이터 구조를 구성할 수 있다.
  • 스레드 동기화를 제공하지 않기 때문에 멀티스레드 환경에서 안전하지 않다.
• LinkedHashMap
  • HashMap의 하위 클래스로 HashMap의 모든 기능을 상속받는다.
  • HashMap과 다르게 순서를 유지한다. 내부적으로 이중 연결 리스트를 유지함으로써 달성된다.
  • 접근 순서를 기반으로 요소를 정렬하는 것이 가능하여 최근에 가장 적게 사용한 요소를 쉽게 찾아낼 수 있다. 이러한 특성 때문에  LUR(Least Recently Used) 캐싱 알고리즘에 적합하다.
  • HashMap에 비해 약간 더 많은 메모리를 사용한다.
• 해싱과 해시함수
  '해싱'은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정을 의미한다. 이 과정에서 사용되는 함수를 '해시함수'라 하고 이를 이용해서 데이터를 해시테이블에 저장하고 검색한다. '해시 테이블'은 키 - 값을 저장하는 자료구조로, 해시 함수를 사용하여 키를 해시 코드로 변환한 후, 이 해시 코드를 인덱스로 사용하여 값을 저장하거나 검색한다.
  
  

🔸TreeMap

• 이진검색트리 + Map
  
  • Java의 SortedMap 인터페이스를 구현한 클래스. 키-값 쌍을 정렬된 순서로 순회해야 하는 경우에 유용하다.
  • 키를 기준으로 정렬한다. 
  • 균형 이진트리인 레드-블랙 트리를 사용하여 요소를 저장하기 때문에 검색, 삽입, 삭제 연산이 로그 시간 복잡도를 가져 효율적이다.
  • Null 키를 허용하지 않지만 null 값은 허용한다.
  • 멀티스레스 환경에서 동기화를 제공하지 않아 외부 동기화가 필요하다.
• HashMap과 TreeMap의 차이점
  • 정렬 : HashMap은 요소의 순서를 보장하지 않지만, TreeMap은 키를 기준으로 요소를 정렬한다.
  • 성능 : HashMap은 해시 함수를 사용하여 요소를 저장하고 검색하기 때문에 일반적으로 TreeMap보다 빠른 검색 및 삽입 성능을 제공한다. 하지만 TreeMap은 키 기반의 정렬이 필요한 경우에 유용하며, 검색, 삽입, 삭제 연산이 로그 시간 복잡도를 가진다.
  • Null 키 : HashMap은 null 키와 null 값을 허용하지만, TreeMap은 null키를 허용하지 않는다.
• 로그 시간 복잡도
  입력 데이터의 크기가 커질수록 알고리즘이 처리하는데 필요한 시간이 로그 증가한다. 즉, 입력 데이터의 크기가 두 배로 늘어나면, 처리 시간은 단지 한 단계만 증가한다는 것을 의미한다.
  
  정렬된 배열에서 특정 값을 찾기 위해 중간 요소를 확인하고, 찾고자 하는 값이 중간요소보다 작으면 왼쪽 하위 배열을, 크면 오른쪽 하위 배열을 대상으로 동일한 과정을 반복한다. 이 과정을 통해 검색 범위를 매 단계마다 절반으로 줄여나가므로, 전체 요소 수 N에 대해 log2N 단계가 소요되기 때문에 로그 시간 복잡도를 가지게 된다.
  
  O(log N)으로 표현되며, 여기서 N은 입력 데이터의 크기를 나타낸다. 이러한 복잡도를 가진 알고리즘은 대표적으로 인진 검색, 퀵 정렬, 머지 정렬, 힙 정렬 등이 있다.
  
  로그 시간 복잡도를 가진 알고리즘은 대량의 데이터를 처리하는 데 효율적이다.