Map

🐧 MAP

#사전 #KeyValue #HashMap #TreeMap #LinkedHashMap

HashMap

transient Node<K,V>[] table; // 위의 노드로 만들어진 배열 table ! 

• 내부적으로 Entry 배열을 만들어 관리한다.

• map.put() 메서드를 이용해서 엔트리를 추가하면 Key 값으로 넘겨준 객체의 해시 코드를 계산하여 Entry 배열의 접근 인덱스로 사용한다. (null 가능 !)

• 입력된 순서나 Key 값의 정렬 순서는 지켜지지 않고 다 섞이게 된다.

• 해시 함수를 사용하기 때문에 O(1)으로 다른 Map 보다는 빠른 탐색시간을 갖는다.

hash 충돌 방지

• Open Addressing
• 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다.
• 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다. 데이터 개수가 충분히 적다면 separate Chaining 보다 더 성능이 좋다. 하지만 배열이 커질수록 캐시 효율이라는 장점이 사라진다.
• 그래서 remove메서드가 빈번하게 호출 될 수 있는 HashMap은 separate Chaining을 사용한다.

• Separate Chaining + 보조 해시 함수
• 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분이다.
• 같은 해시값을 가진 키를 링크드 리스트로 저장하는데 8개 이상이 될 경우 Tree로 변경하고, 삭제로 인해 6개가 될 경우 다시 링크드 리스트로 변경한다. ⇒ 일정 크기 이상이 아닐 경우 8개 이상이 되어도 Tree로 변경하지 않습니다.
• 개념상 해시 버킷 인덱스를 계산할 때에는 index = X.hashCode() % M처럼 나머지 연산을 사용하는 것이 맞지만, M값이 2a 일 때는 해시 함수의 하위 a비트 만을 취한 것과 값이 같다. 따라서 나머지 연산 대신 '1 << a – 1' 와 비트 논리곱(AND, &) 연산을 사용하면 수행이 훨씬 더 빠르다.
 

NAVER D2

https://d2.naver.com/helloworld/831311

TreeMap

• Key-Value 쌍을 내부적으로 RedBlack Tree 로 저장하여 관리한다.
• Red-Black Tree : 이진 탐색 트리 중 하나
• Red-Black Tree 형태로 관리하기 때문에 데이터를 탐색하는데 O(log N)의 시간이 걸린다.
알고리즘 ) Red-Black Tree
얼른 iOS글도 써야하는데...ㅎ_ㅎ 뭐 연휴는 기니까.... 히유ㅠㅠ강의자료 보다보니까, 이때 생각도 나고 디게 그립네요. 몇달전에 제가 공부하던것들인데 말이에요. 그 중에서도..네..시험에 Red-Black Tree가 나왔는데.. 바닥에 지우개가 떨어져서 줍지도 못하고 그 샤프 뒤에 있는 그 짱쪼끄만 지우개로 지우면서 문제를 풀었던 기억이 있네요ㅎㅎ 그만큼 지우개가 상당히 중요한 Red-Black Tree입니다 ㅎ 간단하게 Red-Black Tree에 대한 글을 써보려고해요 :) 한글로 적흑트리, 적흑나무 라고 말한 책도 있는데...

https://zeddios.tistory.com/237

• Key 값을 기준으로 정렬된 상태를 유지할 수 있다.

• Key 값으로 사용할 클래스에 Comparator 인터페이스를 구현하면 사용자가 정렬된 순서를 조정할 수 있다
• key의 null을 허용하지 않는다.

Linked Hash Map

• HashMap의 모든 기능을 사용하면서 데이터의 입력된 순서를 기억한다.
• 메모리 사용량이 HashMap 보다 높다. ⇒ 이중 연결 리스트를 사용하기 때문



• Linked Hash Map 에 저장되는 각 항목은 Map.Entry 클래스를 구현한 Node 클래스로 내부에 before, after 멤버를 갖는 연결 리스트 구조를 가지고 있다.

• HashMap 클래스를 확장한 클래스로 엘리먼트 추가/제거는 O(1) 시간에 이뤄지고 모든 멤버들을 순회하는 연산도 O(1) 시간에 이뤄진다.

Concurrent Hash Map

• 멀티스레드 환경에서 스레드 세이프하다.
• 위의 synchronized 부분은 버킷에 이미 노드가 존재하는 경우에 실행되는 코드입니다.
• 즉, update를 할 때 들어오는 코드 → synchronized → 버킷 단위로 락

• 읽기 작업에는 여러 스레드가 동시에 가능하지만 쓰기 작업에는 버킷에 Lock을 사용한다.
• 서로 다른 수정을 한다면(서로 다른 버킷을 수정) 락을 얻기 위해 경쟁하지 않는다.

[Java] ConcurrentHashMap 이란 무엇일까?

HashTable, HashMap, ConcurrnetHashMap 은 많이 유사한 특징들을 가지고 있습니다. 하지만 세부적으로 보면 조금씩 꽤나 차이가 있는데요. 간단하게 어떤 차이가 있는지 알아보면서 시작하겠습니다. public class Hashtable extends Dictionary implements Map , Cloneable, java.io.Serializable { public synchronized int size() { } @SuppressWarnings("unchecked") public synchronized V get(Object key) { } public synchronized V put(K key, V value) { } } Hashtable 클래스의 대부분의 API를 보면 위와 같이 메소드 전체에 synchronized 키워드가 존재하는 것을 볼 수 있습니다.( 메소드 전체가 임계구역으로 설정 됩니다.)

https://devlog-wjdrbs96.tistory.com/269

어떤 상황에 어떻게 사용해야할까?

• 멀티 스레드 환경에서 데이터 일관성이 중요하거나 update 작업이 빈번하고 update성능이 중요할 때
• Concurrent

• 요소를 정렬해야할 경우
• Tree

• 순서고 스레드고 뭐고 다 상관 없어 ! 빠른게 좋아
• HashMap

• 입력순서를 꼭 보장 받아야겠어 !
• LikedHashMap