Hashtable의 내용이 메모리의 크기에 어떤 영향을 줍니까?

Question

Hashtable A에 5 백만 개의 고유 값으로 매핑 된 5 백만 개의 키가 있고 Hashtable B에 20 만 개의 고유 값으로 매핑 된 5 백만 개의 키가 있다면 Hashtable B와 비교할 때 얼마나 많은 메모리가 Hashtable A에 사용됩니까?

모든 키와 값은 약 20-50 자 길이의 문자열입니다.

내 초기 추측은 해시 테이블 A는 해시 테이블 B로 약 두 배의 공간을 차지 것입니다,하지만 당신은 매핑을 포함 할 경우 다음 해시 테이블 B를 사용합니다 :

(500 만 키 + 5 백만 매핑 + 20 개 값)/(500 만 개의 키 + 5 백만 개의 매핑 + 5 백만 값) = .66

해시 테이블 A의 66.6 %가 사용합니다. 그러나 키와 값이 String 인 경우 매핑에서 많은 키 또는 값을 사용할지 여부는 알 수 없습니다.

댓글?

Answer 1

해시 테이블의 "값"은 기존 값이라고 가정하기 때문에 해시 테이블을 많이 사용하지 않아도됩니다. 총 비용의 증가는 주로 가치의 크기에 기초합니다. 결국 모든 키가 null로 매핑 될 수 있습니다.

또한 키 크기에 따라 영향을 줄 수도 있고 아닐 수도 있습니다. 예를 들어, 문자열과 같은 5 백만 개의 무거운 객체에서 정수와 같은 5 백만 개의 가벼운 객체로의 매핑은 5 백만 개의 무거운 객체를 20 개의 다른 Integer 값으로 매핑하는 것과 다를 바 없습니다.

Answer 2

리터럴 문자열을 저장하는 경우 JVM이이를 수용 할 수 있습니다.이 경우 20 키 버전의 메모리 사용량이 훨씬 적습니다 (계산 방법을 모르는 경우). 그러나 이러한 마법에 종속되지 않는 표준 해시 테이블 구현의 경우, 다른 버킷에 저장되어 있는지 여부에 관계없이 각 "버킷"에 값이 저장되므로 동일한 양의 메모리를 사용하게됩니다.