JDK 용기 와 병발 - Map - Weak HashMap

7820 단어 JDK 용기 와 병발
개술
      약 한 인용 키 를 기반 으로 한 HashMap, 비 스 레 드 안전.
1) key 가 인용 한 대상 이 약 한 인용 만 있 을 때 GC 에서 해당 대상 을 회수 하면 연 결 된 Entry 가 자동 으로 삭 제 됩 니 다.
2) 그 행위 부분 은 GC 에 의존한다.
3) value 는 강 한 인용 이다.value 가 키 를 직접 또는 간접 적 으로 인용 하지 않 았 는 지 확인 하 십시오. 그렇지 않 으 면 키 인용 대상 의 회 수 를 막 을 수 있 습 니 다.간접 인용: value 1 강 은 key 2 의 대상 을 인용 하고 관련 된 value 2 강 은 key 1 의 대상 을 인용 합 니 다.
4) 교체 기 fail - fast.
데이터 구조
      HashMap 과 유일한 차이 점 은 Weak HashMap 은 key 를 Weak Reference 에 밀봉 하고 Reference Queue 와 관련 하여 key 의 약 한 인용 을 실현 하 는 것 입 니 다.
Entry[] table;

/**
* Reference queue for cleared WeakEntries
*/
private final ReferenceQueue queue = new ReferenceQueue<>();

private static class Entry extends WeakReference implements Map.Entry {
	V value;
	int hash;
	Entry next;

	/**
	 * Creates new entry.
	 */
	Entry(Object key, V value,
		  ReferenceQueue queue,
		  int hash, Entry next) {
		super(key, queue);
		this.value = value;
		this.hash  = hash;
		this.next  = next;
	}
} 
   
  

      HashMap :table、threshold , init() ;HashMap put table :

//      、      
public WeakHashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal Initial Capacity: "+
										   initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;

	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal Load factor: "+
										   loadFactor);
	// table、loadFactor   
	int capacity = 1;
	while (capacity < initialCapacity)
		capacity <<= 1;
	table = newTable(capacity);
	this.loadFactor = loadFactor;
	threshold = (int)(capacity * loadFactor);
	useAltHashing = sun.misc.VM.isBooted() &&
			(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
}

//        
public WeakHashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//     
public WeakHashMap() {
	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

//  Map  
public WeakHashMap(Map extends K, ? extends V> m) {
	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
			DEFAULT_INITIAL_CAPACITY),
		 DEFAULT_LOAD_FACTOR);
	putAll(m);
}

첨삭 하 다.
WeakHashMap 에서 잘못된 키 쌍 지우 기
      추가 삭제 및 변경 작업 에서 가장 먼저 하 는 일 은 getTable 을 호출 하 는 것 입 니 다. Weak HashMap 에서 key 참조 대상 이 회수 한 관련 키 쌍 을 삭제 하 는 것 입 니 다.
/**
 * Returns the table after first expunging stale entries.
 */
private Entry[] getTable() {
	expungeStaleEntries();
	return table;
}

//  WeakHashMap   key              
private void expungeStaleEntries() {
	for (Object x; (x = queue.poll()) != null; ) {
		synchronized (queue) {
			@SuppressWarnings("unchecked")
				Entry e = (Entry) x;
			int i = indexFor(e.hash, table.length);

			Entry prev = table[i];
			Entry p = prev;
			while (p != null) {
				Entry next = p.next;
				if (p == e) {
					if (prev == e)
						table[i] = next;
					else
						prev.next = next;
					// Must not null out e.next;
					// stale entries may be in use by a HashIterator
                    //   expungeStaleEntries       modCount   ,
					// HashIterator          ,  next  null
					e.value = null; // Help GC
					size--;
					break;
				}
				prev = p;
				p = next;
			}
		}
	}
}

용량 조정 정책
      HashMap 과 마찬가지 로 확장 과정 에서 만 Weak HashMap 의 특성 을 고려 해 야 합 니 다.
1) 이전 전에 먼저 weakHashMap 에서 key 참조 대상 이 회수 한 관련 키 쌍 을 삭제 하고 이전 과정 에서 회수 한 것 도 이전 하지 않 습 니 다.
2) 이전 완료 후 size 가 threshold / 2 보다 낮은 경우 처리: 용량 이 확장 되 지 않 고 다시 이전 합 니 다.
void resize(int newCapacity) {
	Entry[] oldTable = getTable();//  WeakHashMap   key              :
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}

	Entry[] newTable = newTable(newCapacity);
	boolean oldAltHashing = useAltHashing;
	useAltHashing |= sun.misc.VM.isBooted() &&
			(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
	boolean rehash = oldAltHashing ^ useAltHashing;
	transfer(oldTable, newTable, rehash);
	table = newTable;

	//     getTable、transfer           ,
	// size  threshold / 2,   oldTable, newTable           
	//        ,   WeakHashMap     ,           
	if (size >= threshold / 2) {
		threshold = (int)(newCapacity * loadFactor);
	} else {
		expungeStaleEntries(); //        
		transfer(newTable, oldTable, false);
		table = oldTable;
	}
}

private void transfer(Entry[] src, Entry[] dest, boolean rehash) {
	for (int j = 0; j < src.length; ++j) {
		Entry e = src[j];
		src[j] = null;
		while (e != null) {
			Entry next = e.next;
			Object key = e.get();
			if (key == null) { //   “key         ”         
				e.next = null;  // Help GC
				e.value = null; //  "   "
				size--;
			} else {
				if (rehash) {
					e.hash = hash(key);
				}
				int i = indexFor(e.hash, dest.length);
				e.next = dest[i];
				dest[i] = e;
			}
			e = next;
		}
	}
}

      첨삭 검사 의 조작 과정 은 HashMap 과 같다.
교체 기
      HashMap 과 마찬가지 로 인용 특성 때문에 사용 하 는 두 가지 강 한 인용 을 제외 하고 nextKey, currentKey 는 각각 next () 에서 얻 을 수 있 고 정상적으로 사용 할 때 얻 을 수 있 습 니 다.
    private abstract class HashIterator implements Iterator {
        private int index;
        private Entry entry = null;
        private Entry lastReturned = null;
        private int expectedModCount = modCount;

        /**
         * Strong reference needed to avoid disappearance of key
         * between hasNext and next
         */
        private Object nextKey = null;

        /**
         * Strong reference needed to avoid disappearance of key
         * between nextEntry() and any use of the entry
         */
        private Object currentKey = null;

        HashIterator() {
            index = isEmpty() ? 0 : table.length;
        }

        public boolean hasNext() {
            Entry[] t = table;

            while (nextKey == null) {
                Entry e = entry;
                int i = index;
                while (e == null && i > 0)
                    e = t[--i];
                entry = e;
                index = i;
                if (e == null) {
                    currentKey = null;
                    return false;
                }
                nextKey = e.get(); // hold on to key in strong ref
                if (nextKey == null)
                    entry = entry.next;
            }
            return true;
        }

        /** The common parts of next() across different types of iterators */
        protected Entry nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextKey == null && !hasNext())
                throw new NoSuchElementException();

            lastReturned = entry;
            entry = entry.next;
            currentKey = nextKey;
            nextKey = null;
            return lastReturned;
        }

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

            WeakHashMap.this.remove(currentKey);
            expectedModCount = modCount;
            lastReturned = null;
            currentKey = null;
        }

    }

특성
      Weak HashMap 의 키 값 이 키 에 대한 약 한 인용 으로 HashMap 과 의 차 이 는 키 의 이 특성 에 대한 특수 처리 입 니 다.

좋은 웹페이지 즐겨찾기