JDK 1.8 HashMap put 소스 코드 분석
13500 단어 자바
Map map = new HashMap<>();
for (int i = 0; i < 10; i++) {
map.put(i, i);
}
내부 에 무슨 일이 있 었 습 니까?넣 는 방법 을 따라 들 어가 보도 록 하 겠 습 니 다.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash (key) 이 방법 은 무엇 입 니까?계속 해시 따라 들 어가 볼 게 요.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
어떻게 보면 잘 모 르 겠 어 요. (h = key. hashCode () ^ (h > > 16) 이 목적 은 무엇 입 니까?
OK, key. hashCode () 에 대응 하 는 것 은 Integer 의 hashcode 입 니 다. 그러면 Integer 의 hashcode 는 무엇 입 니까?이어서 Integer 가 어떻게 다시 쓴 hashcode 인지 보 세 요.
@Override
public int hashCode() {
return Integer.hashCode(value);
}
public static int hashCode(int value) {
return value;
}
Soga, Integer 의 hashcode 가 int 의 값 이 었 구나, OK, 그럼 지금 h = key. hashCode () 의 값 을 알 수 있 겠 구나.
그런데 왜 h = key. hashCode () 는 그것 의 낮은 16 비트 (h > > > 16) 와 다른 가요?이 뒤에 다시 이야기 하 자. 우 리 는 이 의문 을 가지 고 계속 내 려 다 보 자.
자, 우 리 는 지금 hash 라 는 방법 을 다 본 척 하고 hash 값 을 되 돌려 주 었 다 는 것 을 알 고 있 습 니 다. 사실은 정수 입 니 다.
이제 PutVal 의 입 참 을 살 펴 보 겠 습 니 다.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
미리 말씀 드 리 지만 뒤의 두 매개 변 수 는 우리 가 지금 관심 을 가 질 필요 가 없 기 때문에 보이 지 않 는 척 합 니 다.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
……
}
……
}
우 리 는 먼저 가장 간단하게 볼 때 뒤의 지금 이 예 도 갈 수 없 기 때문에 그것 이 공기 라 고 생각 하고 그것 이 아니 라 공기 라 고 생각한다.
우선, 첫 번 째 if (tab = table) = = null | (n = tab. length) = 0), table = = null 의 경 우 는 하나 입 니 다. 바로 map 가 new 에 나 온 후에 put 데이터 가 없습니다. hashmap 의 구조 함 수 를 보 세 요. table 을 초기 화하 지 않 았 습 니 다. 그 렇 죠?PS: (n = tab. length) = = 0 이 동쪽 은 도대체 언제 촉발 되 는 거 야??관련 소스 코드 를 다 봤 는데 도 발견 하지 못 해서 기분 나 빠...설마 노 는 거 라 고 쓰 여 있 는 건 아니 겠 지?.............................................................
OK, 이제 hashmap 의 초기 화 는 resize 라 는 방법 에 통합 되 었 다 는 것 을 알 게 되 었 습 니 다.
이 어 두 번 째 if (p = tab [i = (n - 1) & hash] = = null) 를 살 펴 보 자. 어떻게 보면 이게 무슨 귀신 인지. 그럼 우리 먼저 맨 안쪽 (n - 1) & hash 부터 말 하 자. 이것 이 바로 hash% (n - 1) 다. 아래 를 보 자.
a = 7, b = 14, c = 8
， a % c b % c， a & (c - 1) b % (c - 1)
7 & (8 - 1)
0111
0111
-------
0111
=7
14 & (8 - 1)
1110
0111
------
0110
=6
어떤 규칙 을 알 아 냈 는 지 그 정 수 는 2 의 N 제곱 - 1 을 제외 하고 최고 위 를 0 으로 바 꾸 고 낮은 위 치 를 모두 1 로 바 꾸 는 것 이다. 그러면 이때 모든 수 A & (2 ^ N - 1) 가 얻 은 결 과 는 A 의 낮은 N 자리 이다.
PS: 이제 왜 h ^ h > > 16, 낮은 16 위 와 높 은 16 위 가 다른 지 아 시 죠?그것 은 바로 16 위의 변 화 를 16 위 에 반응 하 게 하 는 것 이다. 그래 야 극단 적 인 상황 에서 대량의 hash 충돌 이 발생 하 는 것 을 방지 할 수 있다!
그래서 tab [i = (n - 1) & hash] 의 뜻 이 뚜렷 합 니 다. 위치 한 통 = = null 일 때 이 통 이 비어 있 고 데 이 터 를 넣 을 수 있다 는 것 을 설명 합 니 다. 마지막 으로 tab [i] = new Node (hash, key, value, null)
다음은 충돌 을 어떻게 처리 하 는 지 분석 하고 케이스 를 추가 하 겠 습 니 다.
Map map = new HashMap<>();
Random random = new Random();
for (int i = 0; i < 1000000; i++) {
map.put(random.nextInt(10000000), random.nextInt(1000000));
}
이제 드디어 puutVal 의 소스 코드 를 맞 출 수 있 게 되 었 습 니 다.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
OK, 드디어 충돌 이 발생 했 습 니 다. 첫 번 째 if (p. hash = = hash & & & (k = p. key) = = key | | (key! =null && key.equals(k))))
질문: put key 후 key 의 hash 값 을 바 꾸 면 어떻게 됩 니까?
같은 키 를 반복 하면 맨 아래 에 있 는 if 를 봅 시다.
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
하면, 만약, 만약...null, 그럼 값 을 업데이트 해 야 하 는 지 판단 하 시 겠 습 니까?PS: after Node Access 와 after Node Insertion 은 큰 도움 이 되 지만 지금 은 또 잃 어 버 려 도 소 용이 없습니다.
이 어 두 번 째 if if (p instanceof TreeNode) 를 분석 해 이 통 이 빨 간 검 은 나무 노드 인지 아 닌 지 를 판단 한다. 그렇다면 XXX, 이제 putTreeVal 이라는 방법 을 들 어가 보 자.
이 어 마지막 else 를 분석 했다. 이 통 이 링크 라면...
OK, put 의 방법 은 이미 끝까지 분석 되 었 습 니 다. 두 개 만 남 았 습 니 다. 하 나 는 + modCount 입 니 다. 이것 은 도대체 무엇 입 니까?하 나 는 resize ()
알 겠 습 니 다. 먼저 + modCount 를 말씀 드 리 겠 습 니 다. 여기 서 100 W 자 를 생략 하 겠 습 니 다. 제 요리 가 아니 라 다른 지식 을 이야기 할 때 말씀 드 리 겠 습 니 다.
마지막 으로 see resize 라 는 방법 을 보 겠 습 니 다. 재 미 있 고 많은 점 을 이 끌 어 낼 수 있 습 니 다.
new Cap 과 new Thr 를 어떻게 재 계산 하 는 지 분석 해 보 겠 습 니 다.
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
……
}
어떻게 한눈 에 볼 수 있 는 지, WC, 두 개의 매개 변 수 를 다시 계산 해서 나 에 게 이렇게 큰 단락 을 만들어 줘...입 속으로 툭툭 털 었 지만 몸 은 성실 하 게 내 려 다 보 았 다..................................................
사실 이것 은 resize 방법 으로 초기 화 하 는 사고 가 아 닙 니 다.
다음은 int oldCap = (oldTab = = null)?0 : oldTab.length
이 단 계 는 초기 화 를 위 한 것 입 니 다. 만약 oldCap = 0 이 라면 첫 번 째 if 판단 을 건 너 뛰 고 이 몇 가지 상황 을 분석 하 겠 습 니 다.
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75 * 16
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
만약 oldCap * 2 < MAXIMUMCAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY 는 새로운 newThr = oldThr < < 1
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
이 부분 은 바로 oldCap < 16 시 상황 을 처리 하 는 것 입 니 다.
OK, new Cap 과 new Thr 를 다시 계산 하여 분석 하 였 습 니 다. 다음은 새로운 공간 을 분배 하 는 것 입 니 다.그리고 다시 카드 를 섞 습 니 다.
final Node[] resize() {
……
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
put 와 차이 가 많 지 않 습 니 다. 모두 3 부작 입 니 다. 보통 node 이거 나 빨 간 검 은 나무 이거 나 링크 입 니 다.
// lo A，hi B
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
//
next = e.next;
//oldCap 2 N ， 0
// e.hash&oldCap 01 ？
// AB ！
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// A
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//j + oldCap B ， ？
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
질문: 높 고 hashmap 을 보 내 면 어떤 상황 이 발생 합 니까? (1.7 과 1.8), 답 부터 말 하면 1.7 과 1.8 모두 XXX 가 발생 할 수 있 지만 발생 하 는 위 치 는 다르다.
자, put 방법 은 여기까지 만 간단히 말씀 드 리 겠 습 니 다.문제 가 있 거나 다른 견해 가 있 는 사람 은 토론 을 환영 합 니 다!저 는 각종 난치병 을 전문 적 으로 맡 고 있 지만 치료 하지 않 습 니 다. 하하 하.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
