TreeMap 또는 HashMap?
이 질문에 이미 답변이 있습니다.
해시 맵이나 트리 맵은 언제 사용합니까?
정렬해야 할 때 TreeMap을 사용하여 요소를 반복 할 수 있다는 것을 알고 있습니다. 하지만 그게 다야? 지도를 참조하거나 최적의 특정 용도를 참조하려는 경우 최적화가 없습니까?
해시 테이블은 (일반적으로)의 복잡성 내에서 제한된 검색 작업 (조회)을 수행 O(n)<=T(n)<=O(1)하며 평균 케이스 복잡성은 O(1 + n/k); 그러나 이진 검색 트리 (BST)는의 복잡성 내에서 제한된 검색 작업 (조회)을 수행 O(n)<=T(n)<=O(log_2(n))하며 평균 케이스 복잡성은 O(log_2(n)). 장점, 단점, 작업 시간 복잡성 및 코드 복잡성을 이해하려면 각 (및 모든) 데이터 구조의 구현을 알고 있어야합니다.
예를 들어, 해시 테이블의 항목 수에는 충돌 목록과 함께 고정 된 수의 항목 (일부는 전혀 채워지지 않을 수 있음)이있는 경우가 많습니다. 반면에 트리에는 일반적으로 노드 당 두 개의 포인터 (참조)가 있지만 구현에서 노드 당 두 개 이상의 자식 노드를 허용하는 경우 더 많을 수 있으며 노드가 추가됨에 따라 트리가 커질 수 있지만 허용하지 않을 수 있습니다. 중복. (Java TreeMap의 기본 구현은 중복을 허용하지 않습니다.)
또한 고려해야 할 특별한 경우가 있습니다. 예를 들어 특정 데이터 구조의 요소 수가 제한없이 증가하거나 데이터 구조의 기본 부분의 한계에 접근하면 어떻게 될까요? 재조정 또는 정리 작업을 수행하는 상각 작업은 어떻습니까?
예를 들어, 해시 테이블에서 테이블의 요소 수가 충분히 커지고 임의의 수의 충돌이 발생할 수 있습니다. 반면에 트리는 일반적으로 삽입 (또는 삭제) 후 재조정 절차가 필요합니다.
따라서 캐시와 같은 것이 있다면 (예 : 제한된 요소의 수 또는 크기가 알려져 있음) 해시 테이블이 가장 좋은 방법 일 것입니다. 그러나 사전과 같은 것이 있으면 (예 : 한 번 채워지고 여러 번 조회) 나무를 사용합니다.
그러나 이것은 일반적인 경우에만 해당됩니다 (정보가 제공되지 않음). 사용할 데이터 구조를 결정할 때 올바른 선택을하기 위해 발생하는 프로세스를 이해해야합니다.
다중 맵 (범위 지정 조회) 또는 컬렉션의 정렬 된 병합이 필요한 경우 해시 테이블이 될 수 없습니다.
TreeMap보장 된 O (log n) 조회 시간 (및 삽입 등)을 HashMap제공 하는 반면 해시 코드가 키를 적절하게 분산하는 경우 O (1) 조회 시간을 제공합니다.
항목을 정렬해야하는 경우가 아니라면 HashMap. 또는 ConcurrentHashMap물론 있습니다. 나는 그들 모두의 차이점에 대한 세부 사항을 기억할 수 없지만 HashMap완벽하게 합리적인 "기본"옵션입니다. :)
완전성을 위해 한 달 정도 전에 다양한 맵의 내부에 대해 Stack Overflow에 대한 논의가 있었다는 점을 지적해야합니다. 이 질문 의 의견을 참조하십시오. bestsss가 기꺼이 그렇게 할 수 있다면이 답변에 복사 할 것입니다.
둘 사이의 가장 큰 차이점은 구현에 사용되는 기본 구조입니다.
HashMaps는 배열과 해싱 함수를 사용하여 요소를 저장합니다. 배열에 항목을 삽입하거나 삭제하려고하면 해싱 함수가 키를 객체가 저장되어야하는 배열의 인덱스로 변환합니다 (충돌 무시). 해시 맵은 대량의 데이터를 반복 할 필요가 없기 때문에 일반적으로 매우 빠르지 만 모든 키 / 값을 새 배열에 복사해야하므로 채워지면 속도가 느려집니다.
TreeMaps는 정렬 된 트리 구조에 데이터를 저장합니다. 이는 더 많은 공간을 할당하고 여기에 복사 할 필요가 없음을 의미하지만, 작업을 수행하려면 이미 저장된 데이터의 일부를 반복해야합니다. 때때로 많은 양의 구조를 변경합니다.
두 개의 Hashmap 중 정렬이 필요하지 않을 때 일반적으로 더 나은 성능을 제공합니다.
추가 / 포함 / 제거 작업 LinkedHashMap만큼 빠르지 HashMap만 삽입 순서를 유지하는 것도 잊지 마십시오 .
HashMap에 새 요소를 삽입하는 것이 평균적으로 TreeMap에 요소를 삽입하는 것보다 훨씬 빠릅니다. 요소를 정렬 할 필요가 없다면 HashMap을 사용하겠습니다.
참고 URL : https://stackoverflow.com/questions/5329358/treemap-or-hashmap
'IT박스' 카테고리의 다른 글
| 트렁크와 지점의 차이점을 찾으십니까? (0) | 2020.10.27 |
|---|---|
| ActiveRecord 데이터 유형에 대한 문서 페이지는 어디에 있습니까? (0) | 2020.10.27 |
| 사람이 읽을 수 있고 사용할 수있는 짧지 만 고유 한 ID 생성 (0) | 2020.10.27 |
| 경고 : 원격 HEAD는 존재하지 않는 참조를 참조하므로 체크 아웃 할 수 없습니다. (0) | 2020.10.27 |
| React-단일 구성 요소의 마운트 및 마운트 해제 애니메이션 (0) | 2020.10.27 |