자바 집합 시리즈 의 링크 드 HashMap 소스 분석
8636 단어 Java집합 하 다.LinkedHashMap
1.링크 드 하 쉬 맵 내 부 는 어떤 구 조 를 사 용 했 습 니까?
이 를 통 해 알 수 있 듯 이 링크 드 HashMap 은 HashMap 에서 계승 되 었 기 때문에 링크 드 HashMap 내부 도 하나의 해시 표 이다.다만 링크 드 HashMap 은 하나의 Entry 를 다시 썼 고 원래 HashMap 의 Entry 에 두 개의 구성원 변 수 를 추 가 했 는데 그것 이 바로 전 계 결점 인용 과 후 계 결점 인용 이다.이렇게 하면 모든 노드 를 연결 시 켜 하나의 양 방향 링크 를 구성 하고 요 소 를 얻 을 때 이 양 방향 링크 를 직접 옮 겨 다 니 면 됩 니 다.링크 드 하 쉬 맵 이 이 룬 엔 트 리 가 어떤 모습 인지 살 펴 보 자.
private static class Entry<K,V> extends HashMap.Entry<K,V> {
//
Entry<K,V> before;
//
Entry<K,V> after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
//
private void remove() {
before.after = after;
after.before = before;
}
//
private void addBefore(Entry<K,V> existingEntry) {
//
after = existingEntry;
//
before = existingEntry.before;
//
before.after = this;
//
after.before = this;
}
// ,
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//
if (lm.accessOrder) {
lm.modCount++;
//
remove();
//
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
// put
void addEntry(int hash, K key, V value, int bucketIndex) {
// addEntry
super.addEntry(hash, key, value, bucketIndex);
// LRU , ,
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
// addEntry
void createEntry(int hash, K key, V value, int bucketIndex) {
// HashMap Entry
HashMap.Entry<K,V> old = table[bucketIndex];
// LinkedHashMap Entry
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//
e.addBefore(header);
size++;
}
3.어떻게 LinkedHashMap 을 이용 하여 LRU 캐 시 를 실현 합 니까?
우 리 는 캐 시 실현 이 컴퓨터 의 메모리 에 의존 한 다 는 것 을 알 고 있 습 니 다.메모리 자원 은 상당히 제한 되 어 있 습 니 다.무제 한 저장 요 소 는 불가능 합 니 다.그래서 우 리 는 용량 이 부족 할 때 일부 요 소 를 적당 하 게 삭제 해 야 합 니 다.그러면 어떤 요 소 를 삭제 하 는 것 이 좋 습 니까?LRU 알고리즘 은 하나의 데이터 가 최근 에 방 문 된 적 이 있다 면 앞으로 방 문 될 확률 도 높다 는 사상 이다.그래서 자주 접근 하지 않 는 데 이 터 를 삭제 할 수 있 습 니 다.다음은 링크 드 하 쉬 맵 내부 에서 LRU 체 제 를 어떻게 실현 하 는 지 살 펴 보 자.
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
//
private transient Entry<K,V> header;
//
private final boolean accessOrder;
...
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// key value
public V get(Object key) {
// key Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null) {
return null;
}
// ,
e.recordAccess(this);
return e.value;
}
private static class Entry<K,V> extends HashMap.Entry<K,V> {
...
//
private void addBefore(Entry<K,V> existingEntry) {
//
after = existingEntry;
//
before = existingEntry.before;
//
before.after = this;
//
after.before = this;
}
// ,
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//
if (lm.accessOrder) {
lm.modCount++;
//
remove();
//
addBefore(lm.header);
}
}
...
}
// put
void addEntry(int hash, K key, V value, int bucketIndex) {
// addEntry
super.addEntry(hash, key, value, bucketIndex);
// LRU , ,
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
// ,
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
public class LRUMap<K, V> extends LinkedHashMap<K, V> {
private int capacity;
LRUMap(int capacity) {
// ,
super(capacity, 1f, true);
this.capacity = capacity;
}
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest) {
//
return this.size() >= capacity;
}
public static void main(String[] args) {
LRUMap<Integer, String> map = new LRUMap<Integer, String>(4);
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");
System.out.println(" :" + map);
String s = map.get(2);
System.out.println(" :" + map);
map.put(4, "d");
System.out.println(" :" + map);
}
}
주의:상기 모든 분석 은 JDK 1.7 을 바탕 으로 버 전 간 에 차이 가 있 을 수 있 으 므 로 독자 들 은 주의해 야 합 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
