HashMap 용량 과 부하 인자 사용 설명
그러면
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// HashMap ，
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// index = (n - 1) & hash， ， index
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // index
Node<K,V> e; K k;
// key key ， e p（ value e value）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ， ，
else if (p instanceof HashMap.TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //
for (int binCount = 0; ; ++binCount) {
// index
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 8 ，
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// ， key ， ， value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e != null ， key ， value， e.value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// size ，
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}매번 put 이후 확장 이 필요 한 지,size 가 총 용량*부하 인 자 를 초과 하면 확장 합 니 다.기본적으로 16*0.75=12 개.
1.왜 초기 용량 은 16
용량 이 2 의 멱 일 때 상기 n-1 에 대응 하 는 이 진 수 는 모두 1 이 어야 key 의 hashcode 와&연산 을 한 후에 균일 하 게 분포 할 수 있 고 이렇게 해야만 hash 충돌 횟수 를 줄 일 수 있다.기본 값 이 왜 16 인지 에 대해 서 는 2,4,8 이 아니 라 32,64,1024 등 이 라 고 생각 합 니 다.너무 작 으 면 몇 가지 요 소 를 놓 지 못 하고 확장 해 야 한다 고 생각 합 니 다.확장 은 성능 을 소모 하 는 작업 입 니 다.수치 가 너무 크 면 더 많은 메모리 공간 을 낭비 할 것 이다.따라서 일상적인 개발 에서 HashMap 이 노드 에 저 장 될 수 있 는 수량 을 예측 할 수 있다 면 초기 화 할 때 용량 을 지정 해 야 한다.
2.왜 부하 인자 가 0.75 입 니까?
또한 종합 적 인 고려 이기 도 합 니 다.만약 에 너무 작 게 설정 하면 HashMap 은 puut 의 소량의 데 이 터 를 한 번 씩 확대 해 야 하고 확대 작업 은 대량의 성능 을 소모 합 니 다.만약 에 너무 크게 설정 하면 1 로 설정 하면 용량 이 16 이 고 현재 배열 에서 차지 하 는 15 개 를 가정 한 다음 에 put 데 이 터 를 들 어 와 야 한다.배열 index 를 계산 할 때 hash 충돌 이 발생 할 확률 은 15/16 에 달 할 것 이다.이것 은 HashMap 이 hash 충돌 을 감소 하 는 원칙 에 위배 된다.
HashMap 은 용량 이 밸브 값 에 도달 해야만 용량 을 늘 릴 수 있 습 니까?큰 실수!
인터넷 에 올 라 온 많은 글 을 보면 HashMap 은 요소 가 부하 인자 대응 수 에 이 르 렀 을 때 확장 이 발생 한다 고 한다.만약 당신 이 소스 코드 를 보 았 다 면,사실은 또 하나의 상황 이 발생 할 수도 있 습 니 다.나무 가 모양 화 될 때.
대상 은 결국 어떻게 HashMap 에 넣 었 습 니까?
HashMap 밑바닥 은 수조+체인 테이블 로 구성 되 어 있 기 때문에 모 르 는 사람들 이 쉽게 이해 할 수 있 도록 하기 위해 서 우 리 는 먼저 HashMap 밑바닥 이 수조 라 고 가정 하고 체인 테이블 을 상관 하지 않 는 다.
대상 add 가 HashMap 에 있 을 때 HashMap 의 add 방법 은 어떻게 이 대상 이 배열 의 어느 위치 에 있 는 지 확인 합 니까?
JDK 1.8 로 말 하면(다른 JDK 버 전 은 조금 다 르 지만 대동소이 하 다)모든 대상 이 천성적으로 계승 되 었 거나 프로그래머 가 Object 류 의 hashCode()방법 을 스스로 덮어 썼 다 는 것 을 알 아야 한다.이 방법 은 대상 의 hashcode 값 을 되 돌려 준다.
HashMap 에는 방법 이 있 습 니 다.먼저 HashMap 에 추가 할 대상 의 hashCode 를 받 은 다음 에 이 hashCode 가 다 르 거나 대상 자체 의 hashCode 를 오른쪽으로 16 자리 옮 기 는 방법 이 있 습 니 다.(사람 말 이 아 닌 것 같 지 않 습 니까?이 절 차 는 교란 이 라 고 합 니 다.이렇게 하 는 목적 은 hashCode 모든 사람 이 가능 한 한 사용 하도록 하 는 것 입 니 다.이해 하지 못 하면 다음 읽 기 에 영향 을 주지 않 습 니 다).hashCode 는 상기 절 차 를 거 친 후에&(배열 길이-1)계산 한 결 과 는 바로 이 대상 이 배열 에 있 는 위치 입 니 다.나 자신 도 말 하 는 것 이 사람 말 이 아니 라 고 생각한다.다음은 예 를 들 어 이해 하기 쉽다.
여기 Student 대상 이 있 는 hash Code 는:a 입 니 다.
먼저 이 a 를 오른쪽으로 16 자리 옮 기 고 b=a>>16;
그리고 a=a&b;
배열 의 위 치 는 a&(배열 길이-1)와 같 습 니 다.
상기 소스 코드 는 다음 과 같 습 니 다.
h=key.hashCode();
h = key.hashCode()) ^ (h >>> 16）
배열 위치=h&(배열 길이-1);
자,우 리 는 요소 가 어떻게 hashMap 의 배열 에서 어떻게 위 치 를 정 하 는 지 이미 알 고 있 습 니 다.지금 은 극단 적 인 상황(발생 할 수 없 지만 저 는 이 예 를 들 어)을 가정 합 니 다.
배열 길이 가 1 이 라 고 가정 하고 소스 코드 에 따라:
배열 위치=h&(배열 길이-1)
그러면:
배열 위치=h&(1-1)=0,어떤 대상 이 든 배열 의 0 번 째 위치 로 위치 합 니 다.
이거 잘 이해 되 죠?요소 가 같 든 안 같 든 배열 의 길이 가 1 이기 때문에 요 소 는 배열 의 0 번 째 위치 로 통 합 됩 니 다.한 배열 에 한 요소 만 넣 는 거 아 시 죠?그럼 어 떡 하지?우 리 는 링크 로 이 문 제 를 해결 하고 이 위치 에 위치 한 요 소 를 링크 로 연결 합 니 다.이것 이 바로 내 가 처음에 말 한 것 이다.hashMap 은 배열+링크 이다.
그 나무 형 화 는 또 무엇 입 니까?
우리 가 왜 HashMap 을 사용 해 야 하 는 지 생각해 보 세 요.Hash 알고리즘 을 통 해 이상 적 인 상황 에서 시간 복잡 도 O(1)를 찾 을 수 있 기 때 문 입 니 다.특히 빠 르 지만 이상 적 인 상황 이 라 고 했 습 니 다.만약 에 상기 hash 충돌(누가 jb 가 지은 이름,바로 위 에서 말 한 것 입 니 다.두 요 소 는 배열 의 같은 위치 에 위치 합 니 다)이 발생 하고 hash 충돌 이 빈번 하면...그러면 우리 가 get 요 소 를 얻 었 을 때 이 배열 을 찾 았 습 니 다.배열 에서 링크 를 한 번 더 옮 겨 다 녀 야 get 요 소 를 찾 을 수 있 습 니 다.HashMap 을 사용 하 는 초심 을 잃 었 습 니까?(링크 를 옮 겨 다 녀 야 하기 때문에 시간 복잡 도가 이전 보다 높 습 니 다)
그래서 JDK 1.8 은 빨 간 검 은 나무 라 는 데이터 구 조 를 사용 하여 링크 가 너무 긴 문 제 를 해결 할 수 있다.
처음에 내 가 말 했 던 것 으로 돌아 가면 왜 나무 가 모양 화 될 때 확장 이 일어 날 수 있 습 니까?
방금 예 를 들 어 배열 의 길 이 는 1 이 고 모든 요 소 는 배열 의 0 번 째 위치 에서 하나의 링크 를 형성 했다.이 예 는 극단 적 인 상황 이다.배열 의 길이 가 너무 작 으 면 자 연 스 럽 게 hash 충돌 이 자주 발생 한다.그 성장 링크 는 긍정 적 인 것 이다.이때 나무 형 화 는 실제 적 으로 기준 을 치료 하지 않 고 근본 적 인 원인 은 배열 이 너무 짧 기 때문이다.따라서 JDK 1.8 소스 코드 에 서 는 트 리 화 를 실행 하기 전에 먼저 배열 의 길 이 를 검사 하고,길이 가 64 보다 작 으 면 트 리 화 대신 배열 을 확대 한다.
그래서 용량 을 늘 릴 때 두 가지 상황 이 발생 한다.하 나 는 원소 가 밸브 값 에 이 르 렀 다 는 것 이다.하 나 는 HashMap 가 트 리 화 를 준 비 했 지만 수조 가 너무 짧 은 것 을 발견 했다.이 두 가지 상황 은 모두 용량 을 늘 릴 수 있다.
이상 의 HashMap 용량 과 부하 인자 사용 설명 은 바로 소 편 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 께 참고 가 되 고 저희 도 많이 사랑 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 1411] 비슷한 단어 (JAVA)원본 알파벳이 숌하게 바뀔 경우, 이를 HashMap을 이용해서 쌍으로 묶어준다. HashMap 사용법이 익숙하지 못 해서 어려웠던 문제이다. HashMap 사용법 30분 💬 투포인터 버전 참고...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
