Hashmap 의 용량 이 왜 2 의 幂 次 인지 이야기 하 다
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); // key Entry table[0]
int hash = hash(key.hashCode()); // key.hashcode() hash ，hash hashmap
int i = indexFor(hash, table.length);//
/*
* for ： hash key ， （ ）
*/
for (Entry<K, V> e = table[i]; e != null; e = e.next) {// ：for
Object k;
//hash key ，
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//e.recordAccess(this);
return oldValue;//
}
}
modCount++;
addEntry(hash, key, value, i);// Entry table[i]
return null;// key Entry， null
}
/**
* " "
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}
모두 가 알다 시 피 컴퓨터 안의 비트 연산 은 기본 연산 이 고 비트 연산 의 효율 은 나머지%의 연산 보다 훨씬 높다.
예 를 들 어:
2^n 을 2 진법 으로 바 꾸 면 1+n 개 0,1 을 빼 면 0+n 개 1,예 를 들 어 16->10000,15->01111
그러면&비트 연산 의 규칙 에 따라 모두 1(진)일 때 만 1 이 고,그 0≤연산 후의 결 과 는≤15 이 며,h<=15 를 가정 하면 연산 후의 결 과 는 h 자체 이 고,h>15 이 며,연산 후의 결 과 는 마지막 4 비트 2 진법 으로&연산 후의 값 이 며,최종 적 으로 는%연산 후의 나머지 이다.
용량 이 반드시 2^n 일 때 h&(length-1)=h%length
HashMap 용량 과 부하 인자
HashMap 바 텀 데이터 구 조 는 배열+링크 이 고 JDK 1.8 에는 빨 간 검 은 나무 도 도입 되 어 있 으 며 링크 길이 가 8 개 를 넘 으 면 링크 를 빨 간 검 은 나무 로 바 꾸 어 검색 성능 을 향상 시킨다.그러면
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 의 용량 이 왜 2 의 幂 次 인 지 를 이야기 하 는 것 입 니 다.문 제 는 바로 편집장 이 여러분 에 게 공유 한 모든 내용 입 니 다.여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 많이 응원 해 주시 기 바 랍 니 다.
좋은 웹페이지 즐겨찾기
