자바 용기 류 소스 분석 - LinkedHashMap
12602 단어 자바
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>링크 드 하 쉬 맵 은 하 쉬 맵 을 계승 하여 맵 인 터 페 이 스 를 실현 했다.
LinkedHashMap 은 두 개의 속성 만 정의 합 니 다:
1 /**
2 * The head of the doubly linked list.
3 *
4 */
5 private transient Entry<K,V> header;
6 /**
7 * The iteration ordering method for this linked hash map: true
8 * for access-order, false for insertion-order.
9 * true ，false
10 */
11 private final boolean accessOrder;링크 드 리스트 는 모두 다섯 가지 구조 방법 을 제공 했다.
1 // 1， 、 LinkedList
2 public LinkedHashMap(int initialCapacity, float loadFactor) {
3 super(initialCapacity, loadFactor);
4 accessOrder = false;
5 }
6 // 2， LinkedHashMap，
7 public LinkedHashMap(int initialCapacity) {
8 super(initialCapacity);
9 accessOrder = false;
10 }
11 // 3， LinkedHashMap，
12 public LinkedHashMap() {
13 super();
14 accessOrder = false;
15 }
16 // 4， map LinkedHashMap， （16） (map.zise()/DEFAULT_LOAD_FACTORY)+1 ，
17 public LinkedHashMap(Map<? extends K, ? extends V> m) {
18 super(m);
19 accessOrder = false;
20 }
21 // 5， 、 LinkedHashMap
22 public LinkedHashMap(int initialCapacity,
23 float loadFactor,
24 boolean accessOrder) {
25 super(initialCapacity, loadFactor);
26 this.accessOrder = accessOrder;
27 }구조 방법 에서 알 수 있 듯 이 기본적으로 삽입 순 서 를 사용 하여 키 값 을 추출 하 는 순 서 를 유지 합 니 다. 모든 구조 방법 은 부모 류 의 구조 방법 을 호출 하여 대상 을 만 듭 니 다.
링크 드 HashMap 은 양 방향 링크 를 바탕 으로 하 는 것 이 고 속성 에 header 노드 가 정 해 져 있 습 니 다. 왜 구조 방법 이 초기 화 되 지 않 았 습 니까?
링크 드 하 쉬 맵 에는 init () 방법 이 있 습 니 다. 하 쉬 맵 의 구조 방법 은 모두 init () 방법 을 사용 합 니 다. 여기 서 링크 드 하 쉬 맵 의 구조 방법 은 부모 구조 방법 을 호출 한 후에 부모 구조 방법 에서 init () 방법 을 호출 합 니 다.
1 void init() {
2 header = new Entry<K,V>(-1, null, null, null);
3 header.before = header.after = header;
4 }init () 방법 을 보면 header 를 초기 화하 고 양 방향 순환 링크 를 만 들 었 습 니 다 (링크 드 List 의 저장 구조 와 같 습 니 다).
transfer (HashMap. Entry [] new Table) 방법 은 init () 방법 과 마찬가지 로 HashTable 에서 도 호출 됩 니 다. transfer (HashMap. Entry [] new Table) 방법 은 HashMap 에서 resize (int new Capacity) 방법 을 호출 할 때 호출 됩 니 다.
1 void transfer(HashMap.Entry[] newTable) {
2 int newCapacity = newTable.length;
3 for (Entry<K,V> e = header.after; e != header; e = e.after) {
4 int index = indexFor(e.hash, newCapacity);
5 e.next = newTable[index];
6 newTable[index] = e;
7 }
8 }링크 노드 e 의 해시 값 에 따라 e 가 새로운 용량 의 table 배열 에 있 는 색인 을 계산 하고 e 를 계산 한 색인 에 참조 하 는 링크 에 삽입 합 니 다.
containsValue(Object value)
1 public boolean containsValue(Object value) {
2 // Overridden to take advantage of faster iterator
3 if (value==null) {
4 for (Entry e = header.after; e != header; e = e.after)
5 if (e.value==null)
6 return true;
7 } else {
8 for (Entry e = header.after; e != header; e = e.after)
9 if (value.equals(e.value))
10 return true;
11 }
12 return false;
13 }부모 클래스 의 contains Value (Object value) 방법 을 다시 쓰 고 header 를 통 해 링크 를 옮 겨 다 니 며 table 배열 을 조회 하지 않 고 값 과 value 가 같은 지 판단 합 니 다.
get(Object key)
1 public V get(Object key) {
2 Entry<K,V> e = (Entry<K,V>)getEntry(key);
3 if (e == null)
4 return null;
5 e.recordAccess(this);
6 return e.value;
7 }get (Object key) 방법 은 HashMap 의 getEntry (Object key) 방법 으로 노드 를 가 져 오고 이 노드 의 value 값 을 되 돌려 줍 니 다. 노드 가 null 이면 null 로 되 돌려 줍 니 다. recordAccess (HashMap < K, V > m) 는 LinkedHashMap 의 내부 클래스 Entry 를 소개 하 는 방법 입 니 다.
clear()
1 public void clear() {
2 super.clear();
3 header.before = header.after = header;
4 }clear () 방법 은 부모 클래스 의 방법 clear () 방법 을 먼저 호출 한 다음 에 링크 의 header 노드 의 before 와 after 인용 을 모두 header 자신, 즉 header 노드 는 양 방향 순환 링크 입 니 다. 그러면 원래 링크 의 나머지 노드 에 접근 할 수 없습니다. 그들 은 모두 GC 에 의 해 회 수 됩 니 다.
이상 의 내용 은 많 고 적 음 은 모두 LinkedHashMap 의 내부 류 Entry < K, V > 와 관련 되 어 있 으 며, 아래 에 이 내부 류 를 상세 하 게 소개 합 니 다.
1 // 、 ， HashMap Entry。
2 private static class Entry<K,V> extends HashMap.Entry<K,V> {
3 //
4 Entry<K,V> before, after;
5 //
6 Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
7 super(hash, key, value, next);
8 }
9
10 // ， after before
11 private void remove() {
12 // ， GC
13 before.after = after;
14 after.before = before;
15 }
16
17 // （ ）
18 private void addBefore(Entry<K,V> existingEntry) {
19 // after existingEntry
20 after = existingEntry;
21 // before existingEntry
22 before = existingEntry.before;
23 // existingEntry after
24 before.after = this;
25 // existingEntry before
26 after.before = this;
27 }
28
29 // get put （put HashMap.Entry put
30 // ） recordAccess(HashMap<K,V> m)
31 // accessOrder true， ，
32 // header ， 。
33 // HashMap.Entry
34 // recordAccess(HashMap<K,V> m)
35 void recordAccess(HashMap<K,V> m) {
36 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
37 if (lm.accessOrder) {
38 lm.modCount++;
39 remove();
40 addBefore(lm.header);
41 }
42 }
43 // recordAccess(HashMap<K.V> m) ， HashMap.Entry 。 （remove）
44 void recordRemoval(HashMap<K,V> m) {
45 remove();
46 }
47 }내부 클래스 Entry 를 소 개 했 습 니 다. 다음은 Entry 노드 를 만 들 고 Entry 를 추가 하 는 두 가지 방법 입 니 다.
createEntry(int hash,K key,V value,int bucketIndex)
1 void createEntry(int hash, K key, V value, int bucketIndex) {
2 HashMap.Entry<K,V> old = table[bucketIndex];
3 Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
4 table[bucketIndex] = e;
5 e.addBefore(header);
6 size++;
7 }createEntry (int hash, K key, V value, int bucketIndex) 방법 은 부모 클래스 HashMap 의 방법 을 덮어 씁 니 다. 이 방법 은 table 배열 의 크기 를 넓 히 지 않 습 니 다. 이 방법 은 table 에 있 는 bucketIndex 의 노드 를 먼저 보존 한 다음 Entry 의 구조 방법 (부모 클래스 HashMap. Entry 로 호출 되 는 구조 방법) 을 사용 하여 노드 를 추가 합 니 다. 현재 노드 의 next 참조 지향 table[bucketIndex] 의 노드, 그 다음 에 호출 된 e. addBefore (header) 는 링크 를 수정 하고 e 노드 를 header 노드 에 추가 합 니 다.
이 방법 은 table [bucketIndex] 의 링크 에 노드 를 추가 하고 링크 드 HashMap 자체 의 링크 에 노드 를 추가 합 니 다.
addEntry(int hash, K key, V value, int bucketIndex)
1 void addEntry(int hash, K key, V value, int bucketIndex) {
2 createEntry(hash, key, value, bucketIndex);
3 Entry<K,V> eldest = header.after;
4 if (removeEldestEntry(eldest)) {
5 removeEntryForKey(eldest.key);
6 } else {
7 if (size >= threshold)
8 resize(2 * table.length);
9 }
10 }먼저 createEntry (int hash, K key, V value, int bucketIndex) 방법 을 호출 한 다음 LinkedHashMap 에서 '가장 오래된' (최근 최소 사용) 노드 를 가 져 옵 니 다. 이 어 removeEldestEntry (Entry < K, V > eldest) 방법 과 관련 되 어 있 습 니 다.
1 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
2 return false;
3 }왜 이 방법 은 처음부터 끝까지 false 로 돌아 갑 니까?
위의 addEntry (int hash, K key, V value, int bucketIndex) 방법 을 결합 하면 링크 드 HashMap 을 정상 적 인 Map 으로 만 들 고 '가장 오래된' 노드 를 제거 하지 않 습 니 다.
왜 코드 에서 이 부분의 논 리 를 직접 제거 하지 않 고 이렇게 설계 되 었 습 니까?
이것 은 개발 자 에 게 편 의 를 제공 합 니 다. 만약 에 맵 을 Cache 로 사용 하고 크기 를 제한 하려 면 LinkedHashMap 을 계승 하고 removeEldestEntry (Entry < K, V > eldest) 방법 을 다시 쓰 십시오. 이렇게:
1 private static final int MAX_ENTRIES = 100;
2 protected boolean removeEldestEntry(Map.Entry eldest) {
3 return size() > MAX_ENTRIES;
4 }링크 드 하 쉬 맵 은 상기 내용 을 제외 하고 교체 와 관련 된 세 가지 방법 과 세 가지 내부 유형 과 추상 적 인 내부 유형 이 있 는데 그것 이 바로 new Key Iterator (), new Value Iterator (), new Entry Iterator () 와 Key Iterator 류, Value Iterator 류, Entry Iterator 류 와 링크 드 하 쉬 Iterator 류 이다.
세 가지 new 방법 은 각각 대응 하 는 세 가지 인 스 턴 스 를 되 돌려 줍 니 다. 세 가지 유형 은 모두 추상 적 인 링크 드 Hash Iterator 에서 계승 합 니 다. 다음은 교체 와 관련 된 세 가지 유형 을 보 겠 습 니 다.
1 private class KeyIterator extends LinkedHashIterator<K> {
2 public K next() { return nextEntry().getKey(); }
3 }
4 private class ValueIterator extends LinkedHashIterator<V> {
5 public V next() { return nextEntry().value; }
6 }
7 private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
8 public Map.Entry<K,V> next() { return nextEntry(); }
9 }위 에서 알 수 있 듯 이 이 세 가지 유형 은 모두 간단 합 니 다. 하나의 next () 방법 만 있 습 니 다. next () 방법 도 링크 드 Hash Iterator 류 에 해당 하 는 방법 을 호출 하 는 것 입 니 다. 키 Iterator 류, Value Iterator 류, Entry Iterator 류 와 링크 드 Hash Iterator 류 를 호출 하 는 것 입 니 다.
다음은 링크 드 Hash Iterator 류 의 내용 입 니 다.
1 private abstract class LinkedHashIterator<T> implements Iterator<T> {
2 Entry<K,V> nextEntry = header.after;
3 Entry<K,V> lastReturned = null;
4 // LinkedList ListItr expectedModCount
5 int expectedModCount = modCount;
6 // header ， ，
7 public boolean hasNext() {
8 return nextEntry != header;
9 }
10 // lastReturned
11 public void remove() {
12 if (lastReturned == null)
13 throw new IllegalStateException();
14 if (modCount != expectedModCount)
15 throw new ConcurrentModificationException();
16 LinkedHashMap.this.remove(lastReturned.key);
17 lastReturned = null;
18 expectedModCount = modCount;
19 }
20 //
21 Entry<K,V> nextEntry() {
22 if (modCount != expectedModCount)
23 throw new ConcurrentModificationException();
24 if (nextEntry == header)
25 throw new NoSuchElementException();
26 //
27 Entry<K,V> e = lastReturned = nextEntry;
28 //
29 nextEntry = e.after;
30 return e;
31 }
32 }LinkedHashMap 은 HashMap 및 LinkedList 와 함께 분석 하여 그들의 공통점 과 차이 점 을 비교 해 야 합 니 다. 보완 하기 위해 서 는 그들 간 의 공통점 과 차이 점 을 간단하게 정리 해 야 합 니 다.
HashMap 은 해시 표를 사용 하여 데 이 터 를 저장 하고 지퍼 법 으로 충돌 을 처리 합 니 다. LinkedHashMap 은 HashMap 에서 계승 하 는 동시에 자체 에 하나의 링크 가 있 습 니 다. 링크 를 사용 하여 데 이 터 를 저장 합 니 다. 충돌 이 없습니다. LinkedList 는 LinkedHashMap 과 마찬가지 로 양 방향 순환 링크 를 사용 하지만 간단 한 데 이 터 를 저장 합 니 다. "키 쌍"이 아 닙 니 다.. 그래서 HashMap 과 LinkedHashMap 은 Map 이 고 LinkedList 는 List 입 니 다. 이것 은 그들의 본질 적 인 차이 입 니 다. LinkedList 와 LinkedHashMap 은 모두 내용 의 순 서 를 유지 할 수 있 지만 HashMap 은 순 서 를 유지 하지 않 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
