면접 필수: LinkedHashMap 소스 코드 분석 (JDK 8)
개술
윗글 에서 우 리 는 이미 이 야 기 를 나 누 었 는데
HashMap 이 편 은 윗글 의 기초 위 에 있다.따라서 위의 글 을 보지 못 했다 면 면접 필수: HashMap 소스 코드 분석 (JDK 8) 본 고 는 몇 가지 일반적인 방법 으로 시작 하여 LinkedHashMap 의 소스 코드 를 읽 을 것 입 니 다.구조 방법 - > 상용 API (증가, 삭제, 수정, 검사) 의 순서에 따라 원본 코드 를 읽 고 읽 기 방법 에 관련 된 변수의 의 미 를 설명 합 니 다.LinkedHashMap 의 특징 을 파악 하고 장면 을 적용 한다.만약 본문 에 정확 하지 않 은 결론, 견해 가 있다 면 여러분 은 저 와 토론 하고 함께 발전 하 는 것 을 제기 해 주 십시오. 감사합니다.
2 개요
요약 하면
LinkedHashMap 은 관련 배열, 해시 표 입 니 다. 스 레 드 가 안전 하지 않 고 key 를 null 로 허용 합 니 다. value 는 null 입 니 다.그것 은 HashMap 에서 계승 하여 Map 인 터 페 이 스 를 실현 했다.그 내부 에 양 방향 링크 도 유지 하고 데 이 터 를 삽입 하거나 데 이 터 를 방문 하거나 수정 할 때마다 노드 를 증가 하거나 링크 의 노드 순 서 를 조정 합 니 다.교체 시 출력 순 서 를 결정 합 니 다.기본 적 인 상황 에서 옮 겨 다 닐 때의 순 서 는 노드 를 삽입 하 는 순서에 따른다.이것 도
HashMap 와 가장 큰 차이 이다.또한 구조 할 때 accessOrder 파 라 메 터 를 전송 하여 옮 겨 다 니 는 순서 로 방문 하 는 순서에 따라 출력 할 수 있 습 니 다.계승 자
HashMap 이기 때문에 HashMap 상기 에서 분석 한 특징 은 수출 이 무질서 한 것 을 제외 하고 다른 LinkedHashMap 이 모두 있다. 예 를 들 어 확장 전략, 하 쉬 통 의 길 이 는 반드시 2 의 N 순서 등 이다.LinkedHashMap 실현 할 때 오 버 라 이 드 를 다시 쓰 는 몇 가지 방법 이다.출력 시퀀스 의 질서 있 는 수 요 를 만족 시 킵 니 다.예제 코드:
이 인 스 턴 스 코드 에 따라 먼저 현상
LinkedHashMap 의 특징 을 살 펴 보 자. 데 이 터 를 삽입 하거나 방문 하거나 데 이 터 를 수정 할 때마다 노드 를 증가 하거나 링크 의 노드 순 서 를 조정 한다.교체 시 출력 순 서 를 결정 합 니 다. Map map = new LinkedHashMap<>();
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
map.put("4", "d");
Iterator> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println(" accessOrder=true :");
map = new LinkedHashMap(10, 0.75f, true);
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
map.put("4", "d");
map.get("2");//2
map.get("4");//4
map.put("3", "e");//3
map.put(null, null);// null
map.put("5", null);//5
iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
출력:
1=a
2=b
3=c
4=d
accessOrder=true :
1=a
2=b
4=d
3=e
null=null
5=null
3 노드
LinkedHashMap 의 노드 Entry 는 HashMap.Node 로부터 계승 되 어 그 기초 위 에서 확장 되 었 다.양 방향 링크 로 바 뀌 었 습 니 다. static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
이 동시에 클래스 에 두 개의 구성원 변수
head tail 가 있 는데 각각 내부 양 방향 링크 의 표 두, 표 꼬리 를 가리킨다. //
transient LinkedHashMap.Entry head;
//
transient LinkedHashMap.Entry tail;
4 구조 함수
// false， 。 true， 。
// true ， LruCach
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
// ，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// ，
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
// ， ，
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// Map ，
public LinkedHashMap(Map extends K, ? extends V> m) {
super();
accessOrder = false;
// ， map 。
putMapEntries(m, false);
}
소결: 구조 함수 가
HashMap 에 비해 하나의 accessOrder 매개 변 수 를 증가 시 켰 다.교체 시의 노드 순 서 를 제어 하 는 데 사용 합 니 다.5 증가
LinkedHashMap 어떤 put 방법 도 다시 쓰 지 않 았 다.그러나 새로운 노드 를 구축 하 는 newNode() 방법 을 다시 썼 습 니 다. newNode() 은 HashMap 의 putVal() 방법 에서 호출 되 고 putVal() 방법 은 데이터 putMapEntries(Map extends K, ? extends V> m, boolean evict) 를 대량으로 삽입 하거나 하나의 데이터 public V put(K key, V value) 를 삽입 할 때 호출 됩 니 다.LinkedHashMap 재 작성 newNode() 은 새로운 노드 를 구축 할 때마다 linkNodeLast(p); 을 통 해 새로운 노드 를 내부 양 방향 링크 의 끝 에 연결 했다. // ， `LinkedHashMap.Entry` `Node`.
Node newNode(int hash, K key, V value, Node e) {
LinkedHashMap.Entry p =
new LinkedHashMap.Entry(hash, key, value, e);
linkNodeLast(p);
return p;
}
// ，
private void linkNodeLast(LinkedHashMap.Entry p) {
LinkedHashMap.Entry last = tail;
tail = p;
//
if (last == null)
head = p;
else {//
p.before = last;
last.after = p;
}
}
그리고
HashMap 전문 적 으로 LinkedHashMap 에 게 남 겨 진 afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 방법. // Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { }
// ， ， evict 。 LruCache 。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry first;
//LinkedHashMap 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
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
void afterNodeInsertion(boolean evict) 과 boolean removeEldestEntry(Map.Entry eldest) 는 LruCache 를 구축 하 는 데 필요 한 반전 으로 LinkedHashMap 에서 무시 할 수 있다.삭제
LinkedHashMap 재 작성 remove() 방법 도 없다. 삭제 논리 와 HashMap 차이 가 없 기 때문이다.그러나 그것 은 이 반전 방법 을 다시 썼 다.이 방법 은 afterNodeRemoval() 방법 에서 리 셋 되 고 Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) 노드 를 삭제 하 는 모든 방법 에서 호출 된다. 앞에서 분석 한 바 와 같이 노드 작업 을 삭제 하 는 진정한 집행자 이다. // e ， e
void afterNodeRemoval(Node e) { // unlink
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)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;
// null ， b
if (a == null)
tail = b;
else// a b
a.before = b;
}
조사 하 다
removeNode() 다시 쓰기 LinkedHashMap 방법: public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
대비
get() getOrDefault() 에서 의 실현 HashMap 은 구성원 변수 (구조 함수 시 할당) LinkedHashMap 가 true 인 상황 에서 반전 accessOrder 함 수 를 증가 시 켰 을 뿐이다. public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
void afterNodeAccess(Node e) 함수 에서 현재 방문 한 노드 e 를 내부 의 양 방향 링크 의 끝으로 이동 합 니 다. void afterNodeAccess(Node e) { // move node to last
LinkedHashMap.Entry last;//
// accessOrder true ， e
if (accessOrder && (last = tail) != e) {
// e p
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
//p ， null
p.after = null;
// p null， p ， p a
if (b == null)
head = a;
else// p b a
b.after = a;
// p null， a b
if (a != null)
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;
}
// p
tail = p;
// modCount。
++modCount;
}
}
주의해 야 할 것 은
afterNodeAccess() 함수 에서 수정 afterNodeAccess() 하기 때문에 modCount 모드 에서 교체 accessOrder=true 할 때 방문 데 이 터 를 동시에 조회 하면 LinkedHashMap 교체 순서 가 바 뀌 었 기 때문이다.7.2 containsValue
그것 은 이 방법 을 다시 써 서
fail-fast 의 실현 보다 더욱 효율 적 이다. public boolean containsValue(Object value) {
// ， value ，
for (LinkedHashMap.Entry e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
대비
HashMap 는 두 개의 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;
}
편력
다시 썼 습 니 다
HashMap 다음 과 같 습 니 다. public Set> entrySet() {
Set> es;
// LinkedEntrySet
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet> {
public final Iterator> iterator() {
return new LinkedEntryIterator();
}
}
최종 Entry Iterator:
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator> {
public final Map.Entry next() { return nextNode(); }
}
abstract class LinkedHashIterator {
//
LinkedHashMap.Entry next;
//
LinkedHashMap.Entry current;
int expectedModCount;
LinkedHashIterator() {
// ，next LinkedHashMap
next = head;
// modCount， fail-fast
expectedModCount = modCount;
// null
current = null;
}
// next
public final boolean hasNext() {
// next null， next head
return next != null;
}
//nextNode() next() 。
// ， LinkedHashMap， 。
final LinkedHashMap.Entry nextNode() {
// e。
LinkedHashMap.Entry e = next;
// fail-fast
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// null，
if (e == null)
throw new NoSuchElementException();
// e
current = e;
// e
next = e.after;
// e
return e;
}
// 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;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
주의해 야 할 것 은
entrySet() 교체 기 안의 nextNode() 방법 이다.이 방법의 실현 을 통 해 알 수 있 듯 이 교체 next() 는 내부 에서 유지 하 는 더 블 링크 의 헤더 부터 순환 수출 하 는 것 이다.한편, 쌍 링크 노드 의 순 서 는 LinkedHashMap 의 증가, 삭제, 수정, 검사 할 때 모두 업데이트 된다.삽입 순서에 따라 출력 할 지, 접근 순서에 따라 출력 할 지 만족 합 니 다.총결산
LinkedHashMap 는 LinkedHashMap 의 소스 코드 에 비해 간단 하 다.큰 나무 밑 은 더 위 를 잘 식 히 기 때문이다.그것 은 반복 되 는 순 서 를 바 꾸 기 위해 몇 가지 방법 만 다시 썼 다.HashMap 과 비교 해 가장 큰 차이 이기 도 하 다.데 이 터 를 삽입 하거나 데 이 터 를 방문 하거나 수정 할 때마다 노드 를 증가 하거나 링크 의 노드 순 서 를 조정 합 니 다.교체 시 출력 순 서 를 결정 합 니 다.HashMap 기본 값 은 false 이 고 교체 할 때 출력 순 서 는 노드 를 삽입 하 는 순서 입 니 다.true 라면 출력 순 서 는 방문 노드 의 순서에 따른다.true 를 위 한 경우 이 기초 위 에 하 나 를 구축 할 수 있 습 니 다 HashMap. accessOrder 는 put 방법 을 다시 쓰 지 않 았 다.그러나 이 는 새로운 노드 를 구축 하 는 LruCache 방법 을 다시 썼 다. 새로운 노드 를 구축 할 때마다 새로운 노드 를 내부 양 방향 링크 의 끝 부분 LinkedHashMap 의 모드 에서 newNode() 함수 에서 현재 방문 한 노드 e 를 내부 의 양 방향 링크 의 꼬리 부분 으로 이동 합 니 다.주의해 야 할 것 은 accessOrder=true 함수 에서 수정 afterNodeAccess() 하기 때문에 afterNodeAccess() 모드 에서 교체 modCount 할 때 방문 데 이 터 를 동시에 조회 하면 accessOrder=true 교체 순서 가 바 뀌 었 기 때문이다.LinkedHashMap 는 교체 기 안의 fail-fast 방법 이다.이 방법의 실현 을 통 해 알 수 있 듯 이 교체 nextNode() 는 내부 에서 유지 하 는 더 블 링크 의 헤더 부터 순환 수출 하 는 것 이다.한편, 쌍 링크 노드 의 순 서 는 next() 의 증가, 삭제, 수정, 검사 할 때 모두 업데이트 된다.삽입 순서에 따라 출력 할 지, 접근 순서에 따라 출력 할 지 만족 합 니 다.LinkedHashMap 에 비해 작은 최적화 가 있 고 LinkedHashMap 방법 을 재 작성 하여 내부 링크 를 직접 옮 겨 다 니 며 value 값 이 같 는 지 비교 했다.그럼 마지막 작은 문제 가 있 나 요?왜 재 작성
HashMap 방법 도 내부 링크 의 key 보다 순환 하지 않 습 니까?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
