LinkedHashMap vs HashMap! = LinkedList vs ArrayList

Question

LinkedHashMap은 HashMap보다 더 빠른 반복 속도를 가지고 있는데, 그 요소는 서로 이중으로 연결되어 있기 때문입니다. 또한이 때문에 LinkedHashMap은 요소를 삽입하거나 삭제할 때 속도가 느립니다. 아마도 이러한 링크도 업데이트해야하기 때문일 것입니다. I는 LinkedList의 요소는 또한 이중 연결되는 것을 ArrayList를 VS LinkedList의 행 유사성을 볼 수 있지만

는, I는 ArrayList를보다 느리게 을 반복하여 빠르게 삽입 및 삭제 시간을 가지고 읽었다.

왜 이런가요? 아마 나는 어딘가에서 실수를 저지르고 있는가?

건배!

Answer 1

비유가 작동하지 않습니다. LinkedList와 ArrayList는 List와는 관련이없는 두 가지 구현입니다. 그러나 LinkedHashMap은 HashMap과 동일한 데이터 구조이지만 LinkedList가 포함되어있어 반복을보다 빠르고 일관성있게 수행합니다.

LinkedHashMap 반복이 HashMap 반복보다 빠르다는 이유는 HashMap 반복이 모든 버킷, 심지어 비어있는 버킷을 반복해야한다는 것입니다. LinkedHashMap에 데이터를 가리키는 목록이 있다는 사실은 빈 버킷을 건너 뛸 수 있음을 의미합니다. 제거 시간이 일정하기 때문에 LinkedHashMap의 목록은 링크 된 목록입니다 (일부 arrray 지원 목록 인 경우 O (n)이 아닌).

Answer 2

일부 세부 정보 :

의 LinkedHashMap의 반복자 순서는지도에 삽입 순서와 동일합니다. 따라서 LinkedList 부분은 끝에 "삽입"(꼬리를 추적하는 링크 된 목록의 경우 O (1)) 만 필요하며 Map 부분은 O (1) 인지도 삽입 만 수행합니다. 일반적인 연결리스트 삽입은 O (N)이며, ArrayList 삽입은 삽입이 일어나기 전에 내용을 1 슬롯에 걸쳐 배열 복사해야합니다.

Answer 3

반복 목록 반복 실행 시간 (각 요소에 액세스)은 '이론적으로'배열 목록과 동일합니다. 둘 다 O (n) (Big-O Notation) 런타임이 필요합니다. 그러나 배열에 대한 메모리 할당은 연속적인 메모리 블록 (링크 된 요소는 개별적으로 할당되며 메모리의 어느 위치 에나있을 수 있음)을 통해 이루어지기 때문에 캐싱이 적용됩니다.

Answer 4

링크 된 목록을 반복하려면 각 요소의 모든 참조 (링크)를 따라야합니다. 이러한 참조는 거의 모든 곳을 가리킬 수 있습니다. 다음 요소가 캐싱에 좋지 않은 현재 메모리 다음에 오는 것은 아닙니다. 각 참조를 검색해야하므로 속도가 느립니다. 배열은 메모리에서 연속적이며 다음 요소는 요소 크기만큼 증가 된 현재 요소의 메모리 위치입니다.

이중 연결 목록의 경우 앞뒤 요소의 참조 만 변경해야하므로 배열의 아무 곳이나 삽입하는 속도가 매우 빠릅니다. 반면에 배열은 모든 요소가 새로운 요소를위한 공간을 만들기 위해 복사 될 수 있기 때문에 모든 배열이 복사되기 때문에 느립니다. 배열에 할당 된 연속 메모리가 충분하지 않고 새로 추가 된 요소가 더해지면 요소를 추가해도 전체 배열이 복사됩니다.

특히 큰 데이터 세트를 다룰 때 삽입 차이가 있음을 알 수 있습니다. arraycopy()이 아무리 빠를지라도 이중 연결된 목록은 항상 삽입 속도가 빠릅니다. HashMaps는 거의 반복되지 않고 삽입 및 순서에만 의존하기 때문에 이중 연결 목록은 성능을 향상시킬 수 있습니다.