java HashMap 확장 설명 및 예제 코드

HashMap 확장

서론：

HashMap의 size가 default를 초과하면(용량*로드 팩터) 때, 확장 작업이 발생합니다. 이는 비용이 큰 작업입니다.

왜 확장이 필요합니까?63;HashMap 기본 용량은16,HashMap에 요소가 지속적으로 추가됨에 따라 hash 충돌의 확률이 높아지면, 각 캡에 해당하는 링크드 리스트가 더 길어집니다.

이렇게 되면 검색 성능에 영향을 미치게 됩니다. 왜냐하면 각각의 요소를 찾기 위해 링크드 리스트를 탐색하고, 객체가 일치하는지 확인해야 하기 때문입니다.

검색 성능을 향상시키기 위해 확장만을 통해 hash 충돌을 줄이고, 요소의 key를 최대한 균일하게 분포시키기 위해 확장만을 통해 확장합니다.

확장 기본

로드 팩터의 기본 값은 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

용량의 기본 값은16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // =16

HashMap은 생성할 때 용량과 로드 팩터를 지정할 수 있는 생성자를 제공합니다.

 public HashMap(int initialCapacity, float loadFactor)

기본적으로, HashMap의 size가 default를 초과하면16*0.75=12라고 할 때,

또한 각 Entry(또는 캡)에 최소한 하나의 요소가 있을 때마다 확장이 이루어집니다.

 if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
}

확장할 때, 컨테이너 용량이 두 배로 증가

 resize(2 * table.length);

확장할 때 요소의 배열 인덱스를 다시 계산해야 합니다

1、새로운 Entry 배열을 다시 할당
2、원래 요소의 새로운 배열 내 인덱스를 다시 계산(자원 소모가 많음)

읽어주셔서 감사합니다, 많은 도움이 되길 바랍니다. 많은 사이트 지원에 감사합니다!