HashMap 구현에서 배열 테이블 크기 조정

Aug 20 2020

이것은 HashMap의 내부 구현을 아는 사람들을위한 간단한 질문입니다. :)

초기 크기는 버킷 16 개, 부하 계수는 0.75입니다. 의미 12가되면 32 개의 버킷으로 크기가 조정됩니다.

제 질문은 12 개의 키-값 쌍을 얻거나 12 개의 '채워진'버킷을 얻을 때 버킷이 16 개에서 32 개로 크기가 조정됩니까? 16 개의 버킷에서 12 개의 모든 키-값 쌍이 동일한 버킷에 삽입 될 수 있기 때문에 요청합니다. 이 경우 다른 15 개가 완전히 비어 있으므로 크기를 조정하는 것이 이상 할 것입니다.

감사합니다, 이것에 대한 의견을 주시면 감사하겠습니다 :)

답변

2 ThRnk Aug 20 2020 at 20:07

이 링크 에서 언급했듯이 .

이는 해시 맵의 12 번째 키-값 쌍이 크기를 16으로 유지함을 나타냅니다. 13 번째 요소 (키-값 쌍)가 해시 맵에 들어 오자마자 크기가 기본값 2 ^ 4 = 16 버킷에서 2 ^로 증가합니다. 5 = 32 개의 버킷.

각 키가 삽입 된 위치에 관계없이 부하율과 전류 용량의 곱이 초과되면 테이블 크기가 조정됩니다.

HashMap은로드 팩터에 도달 할 때까지 사용 된 버킷 수에 대해 신경 쓰지 않고 충돌 가능성이 너무 커지고 맵 크기를 조정해야한다는 것을 알고 있습니다. 이미 많은 충돌이 발생했지만.

2 AndrewBlagij Aug 20 2020 at 20:03

JavaDoc에서 https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#put-K-V-

When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

따라서 HashMap은 12 개의 키-값 쌍이있을 때 크기를 조정합니다. 항목의 크기를 조정하면 버킷이 변경되기 때문에 이상하지 않습니다.