1. HashMap
: 해시 테이블을 기반으로 구현되어 있으며, 키-값 쌍을 저장할 때 해시 함수를 사용하여 키를 해시 코드로 매핑하고 이 코드를 사용하여 배열 내의 인덱스를 결정합니다.
2. LinkedHashMap
: 내부적으로 해시 테이블과 연결 리스트를 사용하여 구현합니다. ⇒ 삽입 순서를 유지하면서 데이터를 저장합니다.
3. TreeMap
: Red-Black Tree라는 균형 이진 검색 트리를 사용하여 구현합니다. 이진 트리는 키들을 정렬된 순서로 유지하며 탐색, 삽입, 삭제에 O(logN)의 성능을 제공합니다. ⇒ 키들을 정렬된 순서로 유지합니다. 키의 natural ordering 또는 Comparator에 의해 정렬됩니다.
🔎시간복잡도
| get() | put() | remove() | containsKey() | next() | |
|---|---|---|---|---|---|
| HashMap | O(1) | O(1) | O(1) | O(1) | O(h/n) |
| LinkedHashMap | O(1) | O(1) | O(1) | O(1) | O(1) |
| TreeMap | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) |
🙋♀️ HashMap에서 next()의 시간복잡도가 O(h/n)인 이유가 뭘까요?
h: 데이터의 수, n: map의 사이즈
⇒ 만약, 해시 테이블에 [1, , , 4, , ,2 , ,9 ]가 있을 때 숫자 2를 찾고 싶은 경우 바로 찾을 수도 있지만 그렇지 못 한 경우에는 map의 크기 만큼인 O(h)만큼 탐색해야 할 수도 있습니다. 따라서, 최악의 경우 해당 버킷에서 요소를 찾는 데 O(h)의 시간이 걸리며, 이를 전체 버킷 수 n으로 나눈 O(h/n)의 시간 복잡도를 나타내는 것입니다.
🙋♀️ HashMap에서 n의 사이즈는 언제 동적으로 바뀌나요??
⇒ 일반적으로 Java의 기본 HashMap 구현에서는 부하 계수가 0.75이며, 이 값은 요소의 개수가 배열 크기의 75%를 넘으면 내부 배열의 크기를 두 배로 확장한다는 말입니다. 이때, 내부 배열의 크기가 증가하면 기존 요소들을 크기에 맞춰 해싱하는 작업이 추가로 일어납니다. ⇒ 해싱 작업은 크기를 변경하기 전의 n 사이즈 만큼 시간복잡도가 일어남. 즉, O(N)
🔎성능
-
HashMap
: 일반적으로 빠른 검색, 삽입 및 삭제 연산을 제공합니다. 대부분의 경우 O(1)의 시간 복잡도를 가지지만 해시 충돌이 발생한 경우 즉, 최악의 경우에는 O(n)의 시간 복잡도를 가질 수 있습니다. -
LinkedHashMap
: HashMap과 유사한 성능을 가지며, 추가 메모리와 연결 리스트 관리를 위한 약간의 오버헤드가 발생할 수 있습니다. -
TreeMap은 이진 트리를 사용하여 키를 정렬하므로 검색, 삽입, 삭제 연산의 시간복잡도는 O(logN)입니다.
