99클럽 코테 스터디 8일차 TIL Map

HashTable

란?

• Key, Value 로 데이터를 저장하는 자료구조
• 내부적으로 배열(버킷) 을 사용하여 데이터를 저장함.
  실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 함.

특징

• 동기화
  HashTable 의 메소드는 Thread-safe 임. 여러 쓰레드가 동시에 HashTable 을 수정하더라도 데이터의 일관성이 유지됨. 반면에 HashMap 은 Thread-Safe 하지 않음.
• null 허용 안함.
  HashTable 은 key 나 value 값으로 null 을 허용하지 않음. key 또는 Value 값으로 null 을 사용하려고 하면 NullPonterException 이 발생함.
• 성능
  HashTable 의 동기화 특성 때문에 HashMap 에 비해 성능이 떨어질 수는 있음.
  단일 쓰레드 애플리케이션 또는 멀티쓰레드 환경에서 동기화가 필요하지 않는 경우, HashMap 이 더 나은 성능을 가짐.
• 유물임
  자바 초기 버전부터 제공되던 녀석이기 때문에 Map 인터페이스와 함께 새로운 컬렉션 프레임워크가 도입되면서, HashMap 과 같은 보다 현대적인 대안이 제공되기 시작함.

메소드

Map 인터페이스를 구현하므로 Map 인터페이스에서 제공하는 메소드들을 포함하여 아래와 같은 메소드 제공함.

• put(Object key, Object value) : 키와 값을 해시 테이블에 추가
• get(Object key) : 지정된 키에 연결된 값을 반환
• remove(Object key) : 지정된 키와 그에 연결된 값을 해시 테이블에서 제거함.
• containsKey(Object key) : 해시 테이블에 지정된 키가 있는지 여부를 반환
• containsValue(Object value) : 해시 테이블에 지정된 값이 있는지 true,false 반환
• size() : 해시 테이블에 있는 key - value 쌍의 수를 반환
• isEmpty() : 해시 테이블이 비어 있는지 여부를 반환
• clear() : 해시 테이블의 모든 키와 값을 제거

---

LinkedHashMap

란?

• HashMap 에 순서를 추가한 형태로 java.util 에 속한 녀석임.
• HashMap 의 모든 기능을 포함하면서도, 추가적으로 요소가 추가된 순서 또는 마지막에 접근된 순서를 유지함.

특징

• 삽입 순서 유지
  LinkedHashMap 은 요소를 추가한 순서대로 순회함. 내부적으로 double-linked list 를 사용하여 각 요소의 삽입 순서를 기록하기 때문
• 접근 순서 옵션
  생성자에서 accessOrder 플래그를 true 로 설정하면, LinkedHashMap 은 가장 최근에 접근(읽기 또는 쓰기)된 요소를 맨 끝으로 이동시킴. 이는 LRU(Least Recently Used) 캐시를 구현할 때 유용함.
• 성능
  HashMap 과 거의 동일한 성능을 제공함. 삽입과 삭제, 접근 모두 상수 시간 복잡도를 가짐. 순소를 유지하기 위한 추가적인 비용은 매우 작음.
• 용량과 부하계수
  HashMap 과 마찬가지로 LinkedHashMap 도 초기 용량(capacity) 와 부하 계수(load factor) 를 설정할 수 있음. 이는 맵의 성능 튜닝에 사용될 수 있음

사용 사례

삽입 순서 또는 접근 순서가 중요한 경우 사용됨. 예를 들어, 캐시, DB 쿼리 결과, 파일의 내용을 순서대로 저장하고 접근해야 할 때 유용함.

메소드

• put(K key, V value): 지정된 키와 값을 맵에 추가한다. 이미 맵에 동일한 키가 존재하는 경우, 기존 값을 새 값으로 대체한다.
• get(Object key): 지정된 키에 대응하는 값을 반환한다. 키가 맵에 없는 경우 null을 반환함.
• remove(Object key): 지정된 키와 그에 대응하는 값을 맵에서 제거합니다.
• putAll(Map<? extends K,? extends V> m) : 지정된 맵의 모든 매핑을 현재 맵에 추가함.
• clear(): 맵에서 모든 매핑을 제거한다.
• containsKey(Object key): 맵이 지정된 키를 포함하는지 여부를 반환한다.
• containsValue(Object value): 맵이 하나 이상의 키에 지정된 값을 매핑하는지 여부를 반환한다.
• isEmpty(): 맵이 비어 있는지 여부를 검사한다.
• size(): 맵에 있는 키-값 매핑의 수를 반환한다.
• keySet(): 맵의 키 집합을 반환한다. 이 집합의 순회는 맵에 추가된 순서 또는 접근된 순서대로 이루어진다.
• values(): 맵의 값 컬렉션을 반환한다. 이 컬렉션의 순회는 맵의 키 집합 순회 순서와 동일하다.
• entrySet(): 맵의 매핑 집합을 반환한다. 이 집합의 순회는 맵에 추가된 순서 또는 접근된 순서대로 이루어진다.

---

TreeMap

TreeMap 이란?

• Collection Framework 의 일부로 Map 인터페이스를 구현하는 red-black tree 기반의 NavigableMap 구현
• key-value 를 저장하며, 모든 엔트리는 key 에 따라 자동으로 정렬됨.
  • type 이 숫자일 경우 값으로, 문자일 경우 유니코드로 정렬함.
  • 정렬 순서는 기본적으로 부모 key 값과 비교해서 key 값이 낮은 것은 왼쪽 자석 노드에 key 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장함.

특징

1. 정렬된 순서
   TreeMap 은 key 에 따라 자동으로 정렬됨. 기본적으로는 key 의 자연적 순서를 사용하거나, 생성자에 Comparator 를 제공하여 정렬 순서를 사용자가 정의할 수 있음.
2. key 기반 검색
   TreeMap 은 key 를 사용하여 빠르게 검색할 수 있게 해주며, get, put, remove 같은 메서드를 통해 이루어짐
3. 시간 복잡도
   TreeMap 의 검색, 삽입, 삭제 연산은 모두 평균적으로 O(log n) 시간 복잡도를 가짐. n 은 Tree 의 노드 수
4. NavigableMap 인터페이스
   TreeMap 은 NavigableMap 인터페이스를 구현함으로써, key 에 대한 탐색(예 : 가장 가까운 key 찾기, 범위 검색 등) 에 유용한 메서드를 제공함.
5. 범위 검색과 순회
   key 의 자연적 순서를 활용하여, 특정 범위의 key 에 대한 부분 맵 또는 key-value 의 집합을 빠르게 검색하고 순회할 수 있음.

TreeMap 은 일반적으로 Map 으로써 성능이 HashMap 보다 떨어짐.
TreeMap 은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap 보다 오래 걸림.
하지만 정렬된 상태로 Map 을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap 을 사용하는 것이 효율성면에서 좋음.

Red-Black Tree

Red-Black Tree 는 자가 균형 이진 탐색 트리의 일종으로, 각 노드가 빨간색 또는 검은색의 추가 속성을 가지고 있는 특징을 가짐.

Red-Black Tree 에 관해서는 자세하게 다른 곳에다가 적음.

메서드

TreeMap 은 Map 인터페이스의 구현이면서 NavigableMap 구현이기도 하다.

기본 Map 인터페이스 메서드

• put(K key, V value) : 지정된 key 에 value 를 연결함. 이미 해당 key 값이 있으면, 그 값을 새값으로 대체
• get(Object key) : 지정된 key 에 연결된 value 를 반환함. key가 Map 에 없으면 null 을반환함.
• remove(Object key) : 지정된 key 와 그에 해당하는 값을 제거함.
• containsKey(Object key) : 지정된 key 가 Map 에 있는지 확인함.
• containsValue(Object value) : 지정된 값이 Map 에 있는지 확인함.
• size() : 맵에 있는 key-value 쌍의 수를 반환
• isEmpty() : Map 이 비어 있는지 확인함.
• clear() : Map 에 모든 값을 제거함.

NavigableMap 인터페이스 메서드

• firstEntry() : 맵에서 가장 작은 key 를 가진 Entry 를 반환함.
• lastEntry() : 맵에서 가장 큰 key 를 가진 Entry 를 반환함.
• pollFirstEntry() : 맵에서 가장 작은 키를 가진 엔트리를 제거하고 반환함.
• pollLastEntry() : 맵에서 가장 큰 키를 가진 Entry 리를 제거하고 반환함.
• higherEntry(K key) : 지정된 key 보다 바로 더 큰 key 를 가진 엔트리를 반환함.
• lowerEntry(K key) : 지정된 키보다 바로 더 작은 key 를 가진 엔트리를 반환함.
• ceilingEntry(K key) : 지정된 key 와 같거나 더 큰 key 중 가장 작은 key 를 가진 엔트리를 반환함.
• floorEntry(K key) : 지정된 key 와 같거나 더 작은 key 중 가장 큰 key 를 가진 엔트리를 반환함.

정렬과 관련된 메서드

• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) : 지정된 범위 내의 부분 Map 을 반환함.
• headMap(K toKey, boolean inclusive) : 지정된 Key 보다 작은 key 들을 가진 부분 맵을 반환함.
• tailMap(K fromKey, boolean inclusive) : 지정된 key 보다 크거나 같은 key 들을 가진 부분 Map 을 반환함.

---

HashMap

이란?

• Map 인터페이스를 구현하고 있는 대표적인 클래스
• key, value 쌍으로 구성되어 있음.
• 하나의 key 당 하나의 value 를 가질 수 있음.
• 해싱(Hashing) 검색을 사용하기 때문에 데용량 데이터 관리에도 좋은 성능을 보여줌.
  시간 복잡도 O(1)특징
• key 의 고유성 : 각 key는 Map 내에서 유일해야함. 같은 key 로 새로운 값을 put 하면 기존의 값이 새로운 값으로 대체됨.
• 순서 보장 안됨 : HashMap 은 데이터의 순서를 보장하지 않음. 넣은 순서와 Map 을 순회할 때 나오는 순서가 다를 수 있음.
• null 값 허용 : HashMap 은 key 와 value 값으로 null 을 허용함. 하나의 null 키와 여러 null 값들을 저장할 수 있음.
• Thread-safe 하지 않음 : HashMap 은 멀티 쓰레드 환경에서 동시에 수정될 경우 데이터의 일관성을 보장하지 않음. 멀티 쓰레드에서는 ConcurrentHashMap 을 사용하는게 좋음.

---

메소드

• put(K key, V value) : key 와 value 값을 Map 에 추가함. 이미 존재하는 key 에 값을 추가하면, value 교체됨.
• get(Object key) : 지정된 키에 연결된 값을 반환함. key 가 Map 에 없는 경우 null 을 반환함.
• remove(Object key) : 지정된 Key 와 그에 연결된 값을 Map 에서 제거함.
• containsKey(Object key) : Map 에 지정된 key 가 있는지 true, false 를 반환
• containsValue(Object value) : Map 에 지정된 value 가 하나라도 있는지 true,false 를 반환
• size() : Map 에 저장된 key-value 쌍의 수를 반환
• isEmpty() : Map 이 비어 있는지 여부를 확인
• clear() : Map 에서 모든 키와 값을 여부를 확인
• keySet() : Map 에 있는 모든 key 를 Set 형태로 반환
• values() : Map 에 있는 모든 값을 Collection 형태로 반환
• entrySet() : Map 에 있는 모든 key-value 쌍을 Set 의 Map.Entry<K, V> 형태로 반환

HashMap 은 key 를 통해 빠르게 값을 검색해야할 때 유용하다. 특히 데이터를 key-value 쌍으로 관리해야하는 다양한 프로그래밍에서 사용됨.

---

 

내일은 Red-Black Tree...