내가 해시 맵을 이해했기 때문에 내부 데이터 구조는 2D 배열로 볼 수 있습니다. 첫 번째 인덱스는 "키"이고 두 번째 인덱스는 동일한 키에 해시 된 값을 포함하는 배열입니다. 내 생각에, 당신은 미래의 엔트리를 고려하기 위해 충분히 큰 배열을 초기화 할 필요가있다. 그렇지 않으면 어떤 점에서 배열을 확대하거나 모든 값 해시 값을 같은 값으로 늘려야한다. 특정 크기의 배열을 초기화하는 데 드는 초기 비용 때문에 해시 맵의 초기 비용이 높고 연결 목록이 많다는 뜻입니다.HashMap에 연결된 목록보다 많은 메모리가 필요합니까?
링크드 목록은 X 항목 수를 나타내는 데 필요한만큼의 메모리 만 필요합니다. 이 가정에서 나는 맞습니까? 나는 많은 사람들이 LinkedList가 더 많은 메모리를 사용한다고 말하기 때문에 혼란 스러울뿐입니다.
지도에 키와 값이 있다는 것을 잊고 있습니다. 목록의 모든 항목에 대해 맵에 2가 있습니다. 따라서 LinkedList의 저장 용량이 n 인 경우 2n이 필요합니다. 그 외에, 당신이 지적했듯이, 당신은 약간의 여유 공간을 가져야 만합니다. 그래서 이제는 2n + 2n * .c까지 (1 + c) 2n입니다. 여기서 c는 .25와 같은 분수입니다.
이렇게하면 연결 목록과 비교하여 '높은'공간 요구 사항이 적용됩니까? 나는 당신이 제한된 메모리 요구 사항을 가지고 있지 않다면 그렇게 생각하지 않는다. 기억할 것은, 어떤 요소에 대해서도 일정 시간 액세스 할 수 있다는 것입니다. 링크 된 목록의 경우 O (n)에 액세스하십시오.
마지막으로 맵은 키와 값이있는 문제로 작동하고 목록은 주로 값에만 관련되므로 이러한 데이터 구조를 적용하는 문제는 서로 다른 경향이 있으므로 질문이 적합하지 않을 수 있습니다.
그냥 몇 가지 번호 :
빈의 HashMap가 128 바이트가 필요합니다 오버 헤드가 64 바이트 + 항목 당 36 바이트입니다. 10K 항목의 경우 예상 오버 헤드는 ~ 360K입니다.
빈 LinkedList에는 48 바이트가 필요합니다. 오버 헤드는 24 바이트와 항목 당 24 바이트입니다. 10K 항목의 경우 , 예상되는 오버 헤드는 ~이다 240K
소스 : http://www.ibm.com/developerworks/java/library/j-codetoheap/
