JDK 용기 와 병발 - Map - LinkedHashMap

개술
      링 더 블 링크 가 있 는 HashMap, 비 스 레 드 안전.   
1) HashMap 에서 교체 기 를 옮 겨 다 니 는 효율 이 높 지 않 습 니 다. 이 더 블 체인 표층 은 키 값 이 맞 는 전 체 를 옮 겨 다 니 는 것 을 편리 하 게 하기 위해 서 입 니 다.
2) 추가 삭제 검사 작업 에서 이 쌍 링크 를 유지 하기 때문에 그 성능 은 HashMap 보다 약간 낮다.
3) 간단 한 LRU 캐 시 기능 을 실현 할 수 있다.
4) 교체 기 fail - fast;
데이터 구조
       HashMap 을 바탕 으로 이중 링크 를 추가 하면 HashMap 층 의 배열, 단일 링크 데이터 구조 와 아무런 관계 가 없습니다.

 private transient Entry header; //          

private static class Entry extends HashMap.Entry {
	// These fields comprise the doubly linked list used for iteration.
	Entry before, after; //        

	Entry(int hash, K key, V value, HashMap.Entry next) {
		super(hash, key, value, next);
	}

	//           
	private void remove() {
		before.after = after;
		after.before = before;
	}

	//      ，    existingEntry        
	private void addBefore(Entry existingEntry) {
		after  = existingEntry;
		before = existingEntry.before;
		before.after = this;
		after.before = this;
	}

	//   put、get   ，        ，       。
	//   LinkedMap access-ordered ，             ；  do nothing
	//              ，             
	void recordAccess(HashMap m) {
		LinkedHashMap lm = (LinkedHashMap)m;
		if (lm.accessOrder) {
			lm.modCount++;
			remove();
			addBefore(lm.header);
		}
	}

	//  LinkedHashMap HashMap      ，      ，          
	void recordRemoval(HashMap m) {
		remove();
	}
}

구조 기

//          ：true        ；false        ，    
private final boolean accessOrder;

//      、      
public LinkedHashMap(int initialCapacity, float loadFactor) {
	super(initialCapacity, loadFactor);
	accessOrder = false;
}

//        
public LinkedHashMap(int initialCapacity) {
	super(initialCapacity);
	accessOrder = false;
}

//     
public LinkedHashMap() {
	super();
	accessOrder = false;
}

//  Map  
public LinkedHashMap(Map extends K, ? extends V> m) {
	super(m);
	accessOrder = false;
}

//      、    、    
public LinkedHashMap(int initialCapacity,
					 float loadFactor,
					 boolean accessOrder) {
	super(initialCapacity, loadFactor);
	this.accessOrder = accessOrder;
}

첨삭 하 다.
      링크 드 HashMap 은 HashMap 에 비해 더 블 링크 를 유지 하 는 것 입 니 다.
초기 화
      HashMap 의 기초 구조 기 는 이 방법 을 호출 합 니 다. header 노드 의 초기 화 는 쌍 사슬 표층 과 HashMap 의 데이터 구조 층 이 독립 된 것 을 나타 냅 니 다.

void init() {
	header = new Entry<>(-1, null, null, null);
	header.before = header.after = header;
}

늘다

//  HashMap                     
void createEntry(int hash, K key, V value, int bucketIndex) {
	HashMap.Entry old = table[bucketIndex];
	Entry e = new Entry<>(hash, key, value, old);
	table[bucketIndex] = e;
	e.addBefore(header); //       
	size++;
}

삭제 하 다.
      Entry 의 recordRemoval 방법 을 호출 하여 쌍 사슬 표층 에서 현재 노드 를 삭제 합 니 다.
고치다
      Entry 의 recordAccess 방법 을 호출 합 니 다. accessOrder 가 true 일 때 LRU 의 특성 을 유지 합 니 다.
교체 기
     더 블 링크 를 기반 으로 키 쌍 의 전체 스 트 리밍 을 실현 합 니 다.기본 교체 기 는 링크 드 HashIterator, KeyIterator, ValueIterator, Entry Iterator 가 모두 계승 되 었 습 니 다.

private abstract class LinkedHashIterator implements Iterator {
	Entry nextEntry    = header.after; //      
	Entry lastReturned = null;

	int expectedModCount = modCount;

	public boolean hasNext() {
		return nextEntry != header; //       header    ，         
	}

	public void remove() {
		if (lastReturned == null)
			throw new IllegalStateException();
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();

		LinkedHashMap.this.remove(lastReturned.key);
		lastReturned = null;
		expectedModCount = modCount;
	}

	Entry nextEntry() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
		if (nextEntry == header)
			throw new NoSuchElementException();

		Entry e = lastReturned = nextEntry;
		nextEntry = e.after;
		return e;
	}
}

특성
어떻게 간단 한 LRU 캐 시 기능 을 실현 합 니까?
1）Override removeEldestEntry 방법, 간단 한 LRU 기능 구현:

/*    LRU      ：
 * private static final int MAX_ENTRIES = 100;
 *
 * protected boolean removeEldestEntry(Map.Entry eldest) {
 * 	   return size() > MAX_ENTRIES;
 * }
 */
protected boolean removeEldestEntry(Map.Entry eldest) {
	return false;
}

2) accessOrder 매개 변 수 를 가 진 구조 기 를 사용 하여 더 블 링크 를 설정 하여 방문 순서에 따라 정렬 합 니 다.

accessOrder = true;

3) 링크 드 HashMap 의 추가 검사 방법 은 모두 Entry 의 recordAccess 방법 으로 호출 되 며, 방문 한 노드 를 더 블 링크 끝 으로 이동 시 켜 최신 방문 으로 만 듭 니 다.삭제 방법 은 Entry 의 recordRemoval 방법 을 호출 하여 쌍 사슬 표층 에서 현재 노드 를 삭제 합 니 다.이렇게 해서 LRU 의 특성 을 유지 할 수 있 습 니 다.4) 추가 요청 에 대한 새로운 키 값 이 있 을 때마다 addEntry 는 removeEldestEntry 방법 으로 가장 오래된 노드 를 삭제 할 지 여 부 를 확인 합 니 다 (이곳 의 삭 제 는 HashMap 의 데이터 구조 와 더 블 체인 표층 에서 진 행 됩 니 다). 필요 하 다 면 삭제 합 니 다.이렇게 하면 간단 한 LRU 캐 시 기능 이 구현 된다.

//                
//     removeEldestEntry       LRU  
// LinkedHashMap removeEldestEntry        LRU 
void addEntry(int hash, K key, V value, int bucketIndex) {
	super.addEntry(hash, key, value, bucketIndex);

	//      LRU  
	Entry eldest = header.after;
	if (removeEldestEntry(eldest)) {
		removeEntryForKey(eldest.key);
	}
}