면접 필수 2: JDK 1.8 링크 드 HashMap 실현 원리 및 소스 분석
14965 단어 자바 소스 코드 분석
개술
본 고 는 링크 드 하 쉬 맵 의 소스 코드 분석 은 JDK 1.8 을 바탕 으로 하 는 것 입 니 다. 링크 드 하 쉬 맵 은 하 쉬 맵 을 바탕 으로 하 는 기능 확장 이기 때문에 하 쉬 맵 의 소스 코드 와 실현 원 리 를 파악 해 야 합 니 다. 모 르 시 면 제 다른 하 쉬 맵 의 실현 원리 와 소스 코드 분석 을 먼저 읽 으 십시오.
중점: 본문 에 분석 이 잘못된 부분 이 있 으 면 댓 글로 지적 해 주세요!!!!다시 한 번 강조 하 겠 습 니 다. 이 글 을 읽 기 전에 HashMap 의 소스 코드 를 먼저 알 아야 합 니 다. 제 다른 HashMap 의 실현 원리 와 소스 코드 분석 을 읽 어서 이해 할 수 있 도록 하 세 요.
링크 드 HashMap 의 데이터 구조
링크 드 하 쉬 맵 의 실현 원 리 를 알 고 싶 으 면 먼저 그의 데이터 구조 (즉 저장 체제) 를 알 아야 한다. 하 쉬 맵 과 마찬가지 로 링크 드 하 쉬 맵 의 데이터 구조 도 배열 과 링크 를 통 해 구 성 된 산 목록 이다.
null null 다른 것 은 링크 드 하 쉬 맵 이 산 목록 을 바탕 으로 내부 에서 유지 하 는 것 은 양 방향 링크 가 매번 증가, 삭제, 수정,검사 할 때 링크 의 노드 순 서 를 추가 하거나 삭제 하거나 조정 합 니 다.accessOrder=true 인 자 를 통 해 옮 겨 다 니 는 순 서 를 방문 하 는 순서에 따라 출력 할 수 있 습 니 다.LinkedHashMapEntry 이 하 쉬 맵 의 Node 을 계승 하고 이 를 바탕 으로 양 방향 링크 로 확장 하 는 소스 코드 는 다음 과 같 습 니 다.static class LinkedHashMapEntry extends HashMap.Node {
LinkedHashMapEntry before, after;//
LinkedHashMapEntry(int hash, K key, V value, Node next) {
super(hash, key, value, next);// HashMap Node
}
}
그 밖 에 링크 드 HashMap 은 두 개의 구성원 변 수 를 추가 하여 각각 링크 의 머리 노드 와 꼬리 노드 를 가리킨다.
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry tail;
증가, 변경 put (key, value) 방법 소스 코드
LinkedHashMap 은 HashMap 의 put, putVal () 방법 을 다시 쓰 지 않 고 putVal () 에서 호출 된 다음 세 가지 방법 만 다시 썼 습 니 다.
newNode() 방법 으로 노드 노드 노드 afterNodeAccess(e) 추상 적 인 방법 afterNodeInsertion(evict) 추상 적 인 방법
public V put(K key, V value) {
// hash ， putVal ， ，
return putVal(hash(key), key, value, false, true);
}
여기 서 저 는 이 세 가지 복사 방법 소스 코드 를 분석 할 것 입 니 다. put (), putVal () 방법 에 대한 상세 한 분석 은 위의 HashMap 의 실현 원리 와 소스 코드 분석 에서 put 방법 소스 코드 를 읽 으 십시오.
1: new Node () 방법 원본 을 다시 썼 습 니 다.
다른 것 은 puutVal () 방법 에서 호출 된 new Node 방법 을 다시 쓰 고 새 노드 를 만 들 때 이 노드 를 링크 끝 에 연결 하 는 것 입 니 다
linkNodeLast(p). Node newNode(int hash, K key, V value, Node e) {
// LinkedHashMapEntry
LinkedHashMapEntry p =
new LinkedHashMapEntry(hash, key, value, e);
//
linkNodeLast(p);
return p;
}
// link at the end of list ，
private void linkNodeLast(LinkedHashMapEntry p) {
LinkedHashMapEntry last = tail;
tail = p;
//
if (last == null)
head = p;
else {
//
p.before = last;
last.after = p;
}
}
2: 애 프 터 Node Access (Node e) 복사
노드 가 접근 한 후 put 키 가 존재 할 때
afterNodeAccess(Node e) 방법 으로 정렬 합 니 다. /**
* put(key,value) key ，
* assessOrder=true，
* @param e
*/
void afterNodeAccess(Node e) { // move node to last
LinkedHashMapEntry last;//
if (accessOrder && (last = tail) != e) {// assessOrder&&
LinkedHashMapEntry p =
(LinkedHashMapEntry)e, b = p.before, a = p.after;//p b a 、
p.after = null;// after null， after
//
if (b == null)
//b==null ，p null， p ， p a
head = a;
else
// ，
b.after = a;
if (a != null)
//a != null p null， a b
a.before = b;
else// p null， p 。 last p b
last = b;
if (last == null)// null ，
//
head = p;
else {
// p last， last p
p.before = last;
last.after = p;
}
//
tail = p;
// modCount
++modCount;
}
}
3: 애 프 터 NodeInsertion 복사 (Node e)
/**
* ， evict
* @param evict false
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry first;//
// && null&& ， false
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
/**
*LinkedHashMap false 。 true 。
* LruCache Cache true
* @param eldest
* @return
*/
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
주의: 이 두 가지 방법
void afterNodeInsertion(boolean evict) 과 boolean removeEldestEntry(Map.Entry eldest) 은 LruCache 를 구축 하 는 데 필요 한 반전 입 니 다. 링크 드 HashMap 에서 무시 할 수 있 습 니 다.검색: get (key) 과 getOrDefault (key, defaultValue) 방법 원본 코드
부모 클래스 HashMap 에 비해 복사
get(key) getOrDefault( key, defaultValue) 두 가지 방법 이 있 습 니 다. 검색 과정 은 부모 클래스 와 같 습 니 다. 검색 이 완 료 된 후에 구조 기 accessOrder=true 의 시간 에 따라 afterNodeAccess(e) 방법 으로 현재 방문 한 노드 e 를 내부 의 양 방향 링크 의 꼬리 부분 으로 이동 합 니 다. public V get(Object key) {
Node e;
// Node HashMap ，
if ((e = getNode(hash(key), key)) == null)
return null;
//accessOrder，
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
/**
* {@inheritDoc}
*/
public V getOrDefault(Object key, V defaultValue) {
Node e;
// Node HashMap ，
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
// //accessOrder，
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
삭제: remove () 방법 원본 코드
링크 드 HashMap 의 reove () 는 HashMap 의 논리 와 같 기 때문에 재 작성
removeNode() 방법 이 없습니다. 여기 서 너무 많은 분석 을 하지 않 습 니 다. 상세 한 과정 은 HashMap 의 실현 원리 와 소스 분석 중의 remove() 방법의 소스 코드 를 읽 으 십시오. removeNode() 방법 에서 노드 를 삭제 한 후에 호출 된 afterNodeRemoval() 이 리 셋 방법 을 다시 썼 을 뿐 그 소스 코드 는 다음 과 같 습 니 다./**
* e ， e
* @param e
*/
void afterNodeRemoval(Node e) { // unlink
LinkedHashMapEntry p =
(LinkedHashMapEntry)e, b = p.before, a = p.after;
// p
p.before = p.after = null;
// null， a
if (b == null)
head = a;
else
// b a
b.after = a;
if (a == null)// null ， b
tail = b;
else
// a b
a.before = b;
}
확장: 복사
containsValue(Object value) 는 HashMap 의 실현 보다 효율 적 입 니 다. public boolean containsValue(Object value) {
// for , Value
for (LinkedHashMapEntry e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
한편, HashMap 의
containsValue 방법 은 두 개의 for 순환 으로 구성 되 고 조회 효율 이 상대 적 으로 낮은 소스 코드 는 다음 과 같다.public boolean containsValue(Object value) {
Node[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {//
for (Node e = tab[i]; e != null; e = e.next) {//
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
옮 겨 다 니 기: entry Set () 방법 원본
여기 에는 상기 HashMap 의
entrySet() 방법 소스 코드 와 비교 분석 이 필요 하고 LinkedHashMap 의 entrySet() 방법 소스 코드 를 이해 하기 쉽다. public Set> entrySet() {
Set> es;
// LinkedEntrySet()
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
주로 LinkedEntry Set
Iterator> iterator() 방법 을 사 용 했 습 니 다. LinkedEntry Set 은 LinkedHashMap 의 내부 클래스 로 계승 AbstractSet> 집합 되 었 습 니 다. 상세 한 소스 코드 는 간단 합 니 다. 여기 서 상세 하 게 분석 하지 않 습 니 다.링크 드 HashMap 에서 내부 클래스
LinkedEntrySet 의 iterator() final class LinkedEntrySet extends AbstractSet> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator> iterator() {
// LinkedEntryIterator
return new LinkedEntryIterator();
}
.... ...
}
위의 HashMap 의 extrySet 방법 소스 코드 와 상기 소스 코드 분석 을 통 해 알 수 있 듯 이 우리 가 HashMap 또는 LinkedHashMap 에서 entry Set () 의 Iterator () 방법 으로 돌아 오 는 Iterator 와 달리 각각
new EntryIterator(); 과 new LinkedEntryIterator() 돌아 오 는 Iterator 대상 을 통 해 집합 하 는 과정 이다. 그 다음 에 나 는 그 소스 코드 에 대해 집합 하 는 과정 을 분석 할 것 이다.링크 드 HashMap 의 교체 기
LinkedEntryIterator 소스 코드final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator> {
// next `nextNode()`
public final Map.Entry next() { return nextNode(); }
}
nextNode() 방법 은 부류 LinkedHashIterator 중의 방법 이 고 링크 드 하 쉬 맵 의 본질 LinkedHashIterator 은 집합 을 실현 하 는 것 이다. 그 소스 코드 분석 은 다음 과 같다.abstract class LinkedHashIterator {
LinkedHashMapEntry next;//
LinkedHashMapEntry current;//
int expectedModCount;
/**
*
* ：expectedModCount ：
* HashMap ，LinkedHashMap , , modCount expectedModCount ,
* , HashMap ,modCount ,
* expectedModCount ModCount , ConcurrentModificationException()
*/
LinkedHashIterator() {
// next
next = head;
// ， modCount
expectedModCount = modCount;
// null
current = null;
}
public final boolean hasNext() {
// ， next null
return next != null;
}
/**
* nextNode() ， Iterator next ，
* LinkedHashMap ， 。
*/
final LinkedHashMapEntry nextNode() {
//e
LinkedHashMapEntry e = next;
//
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//current =next
current = e;
//next next ，
next = e.after;
return e;
}
/**
* Iterator HashMap removeNode
* ， modCount != expectedModCount ， ，
* HashMap removeNode
*
*/
public final void remove() {
Node p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
// HashMap ，removeNode
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
HashMap 의 역 사 는 본질 적 으로 Iterator
next() 방법 을 통 해 이 루어 진 것 이 고 next() 는 호출 nextNode() 방법 이다. nextNode 의 소스 코드 를 통 해 알 수 있 듯 이 교체 LinkedHashMap 는 내부 에서 유지 하 는 더 블 링크 의 헤더 부터 순환 수출 을 시작 하 는 것 이다.한편, 더 블 링크 노드 의 순 서 는 링크 드 HashMap 의 증가, 삭제, 수정, 검사 할 때 모두 업데이트 된다.삽입 순서에 따라 출력 할 지, 접근 순서에 따라 출력 할 지 만족 합 니 다.총결산
본 고 는 상기 HashMap 의 실현 원리 와 소스 코드 분석 을 바탕 으로 분석 한 것 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
면접 필수 2: JDK 1.8 링크 드 HashMap 실현 원리 및 소스 분석링크 드 하 쉬 맵 은 하 쉬 맵 을 바탕 으로 하 는 기능 확장 이기 때문에 하 쉬 맵 의 소스 코드 와 실현 원 리 를 파악 해 야 합 니 다. null null 다른 것 은 링크 드 하 쉬 맵 이 산 목록 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
