Javaコレクション(まとめ)
文書ディレクトリ Javaコンテナ List 一、ArrayList fail-fast(高速障害) シーケンス化および逆シーケンス化 VectorとArrayListの同一と相違 二、LinkedList LinkedList検索に対する最適化 三、CopyOnWriteArrayList(ReentrantLockオブジェクトの属性がある) addメソッド(ロック可能) getメソッド(ロックなし) まとめ Map 1.8HashMap LinkedHashMap 重要な3つの関数 まとめ LinkedHashMapを使用してLRU を実装
Javaコンテナ
List
一、ArrayList1、初期サイズ10、拡張容量現在の1.5 2、拡張はArrays.copyOf()を使用して元の配列全体を新しい配列にコピーします. 3、変数の方式はfor循環遍歴増強for循環反復器 がある
fail-fast(クイック失敗)
modCountレコードlistを使用して変更(削除を増やす)した回数
シーケンス化と逆シーケンス化
VectorとArrayListの同一と相違
同じ点:の下位層は配列で実現された である.のデフォルトの長さはすべて10 です.
相違点: Vectorは、メソッドにSynchronized が追加されているため、スレッドが安全です.容量拡張、Vector 2倍、ArrayList 1.5倍 二、LinkedList LinkedListは双方向チェーンテーブルによって実現するList である. LinkedListは、キュー、両端キュー、スタックの特徴 を実現できる両端キューである.は、ヘッダ、テール参照 を含む.
LinkedListの検索に対する最適化
index<双方向チェーンテーブルの長さの1/2であれば、前後から検索します.そうでなければ、後ろから前へ検索します.
三、CopyOnWriteArrayList(ReentrantLockオブジェクトの属性がある)
addメソッド(ロック付き)
まず配列を前の配列容量+1の容量の配列にコピーし、他のスレッドが同時に遍歴すると、新しい配列ではなく元の配列が遍歴する可能性があります.
removeはaddと同様に、コピーして削除してから値を割り当てます.
getメソッド(ロックなし)
まとめ1、CopyOnWriteArrayListはReentrantLockを使用して枷をかけ、スレッドの安全を保証する. 2、CopyOnWriteArrayListの書き込み操作はまず新しい配列をコピーし、新しい配列の中で修正し、修正が終わったら新しい配列で古い配列を置き換え、性能が低い. 3、CopyOnWriteArrayListの読み取り操作はランダムアクセスをサポートし、時間複雑度はO(1)である. 4、CopyOnWriteArrayListは読み書き分離の思想を採用し、読み書き操作はロックをかけず、書き込み操作はロックをかけ、書き込み操作は大きなメモリ空間を占有するため、読み書きが多く、書き込みが少ない場合に適用される. CopyOnWriteArrayListは最終的な一致性のみを保証し、リアルタイムの一致性を保証しない.欠陥は、読みながら書く場合、必ずしも最新のデータ がリアルタイムで読めるとは限らない.
Map
1.8HashMap
参考自分で整理したブログ最大容量2の30乗 1バケツ中の元素の個数が8以上である場合に木化 .バケツ中の元素が6以下である場合、チェーンテーブル に変換される.バケツ中の元素の個数が64に達すると が樹化する.にはmodCount属性があり、反復時に高速失敗操作を実行するための がある.
====
LinkedHashMap
配列+赤と黒のツリー+単一チェーンテーブル+双方向チェーンテーブルLRUは、次の関数を書き換える必要があります.たとえば、書き直すことができます.
ブログ参照
重要な3つの関数 1、afterNodeAccessはノードがアクセスされた後に呼び出され、主にputが既に存在する要素の或いはget()の時に呼び出され、accessOrderがtrueである場合、呼び出すこの方法はアクセスしたノードを双方向チェーンテーブルの末尾 に移動する.2、afterNodeInsertionはHashMapのputValメソッドで呼び出され、HashMapではこのメソッドの実装が空であり、evictがtrueであれば最も古いヘッダノードが除去されることがわかる. 3、afterNodeRemovalはノードが削除されたときに呼び出され、デュアルチェーンテーブルからノードを削除します.
まとめ
(1)LinkedHashMapはHashMapから継承され、HashMapのすべての特性を有する.
(2)LinkedHashMap内部では、双方向チェーンテーブルがすべての要素を格納することを維持している.
(3)accessOrderがfalseである場合、要素を挿入する順序で要素を遍歴することができる.
(4)accessOrderがtrueの場合、要素にアクセスする順序で要素を巡回することができる.
(5)LinkedHashMapの実現は非常にすばらしく、多くの方法はHashMapに残されたフック(Hook)であり、これらのHookを直接実現すれば対応する機能を実現することができ、put()を書き換える必要はない.
(6)デフォルトのLinkedHashMapでは古い要素は削除されません.古い要素を削除する必要がある場合は、removeEldestEntry()メソッドを書き換えて削除ポリシーを設定する必要があります.
(7)LinkedHashMapはLRUキャッシュ淘汰戦略を実現するために使用することができる.
LinkedHashMapによるLRUの実装
LinkedHashMapはどのようにLRUキャッシュの淘汰戦略を実現しますか?
まず、LRUが何者なのか見てみましょう.LRU、Least Recently Usedは、最近最も少なく使用されている要素、すなわち、最近最も少なく使用されている要素を優先的に淘汰します.
LinkedHashMapを使用すると、accessOrderをtrueに設定すると、この戦略を実現するのに十分ではないでしょうか.答えは肯定的だ.次のコードを見てください.
Javaコンテナ
List
一、ArrayList
fail-fast(クイック失敗)
modCountレコードlistを使用して変更(削除を増やす)した回数
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
シーケンス化と逆シーケンス化
private void readObject(java.io.ObjectInputStream s)
private void writeObject(java.io.ObjectOutputStream s)
VectorとArrayListの同一と相違
同じ点:
相違点:
LinkedListの検索に対する最適化
index<双方向チェーンテーブルの長さの1/2であれば、前後から検索します.そうでなければ、後ろから前へ検索します.
public E get(int index)
{
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index)
{
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
三、CopyOnWriteArrayList(ReentrantLockオブジェクトの属性がある)
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
public CopyOnWriteArrayList() // setArray(new Object[0]);
public CopyOnWriteArrayList(Collection<? extends E> c) // Collection Object[] array
public CopyOnWriteArrayList(E[] toCopyIn) // toCopyIn array
}
addメソッド(ロック付き)
まず配列を前の配列容量+1の容量の配列にコピーし、他のスレッドが同時に遍歴すると、新しい配列ではなく元の配列が遍歴する可能性があります.
public boolean add(E e)
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
//
int numMoved = len - index;
if (numMoved == 0) //
newElements = Arrays.copyOf(elements, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
public boolean addIfAbsent(E e)
private boolean addIfAbsent(E e, Object[] snapshot) --- , jdk souorceCode
removeはaddと同様に、コピーして削除してから値を割り当てます.
getメソッド(ロックなし)
public E get(int index) {
return get(getArray(), index);
}
まとめ
Map
1.8HashMap
参考自分で整理したブログ
====
LinkedHashMap
配列+赤と黒のツリー+単一チェーンテーブル+双方向チェーンテーブルLRUは、次の関数を書き換える必要があります.たとえば、書き直すことができます.
public boolean removeEldestEntry(Map.Entry<K,V>eldest)
{
// ,
return size()>this.capacity;
}
ブログ参照
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
重要な3つの関数
//HashMap , , LinkedHashMap
//
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
//LinkedHashMap
/*
， put() get() ，
accessOrder true， 。
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// accessOrder = true ,
// accessOrder = true, e tail
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
/*
， HashMap putVal() ， HashMap 。
evict:
evict true, (head)
removeEldestEntry() false， 。
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// evict true， ， , head
//head
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//HashMap.removeNode() HashMap ， afterNodeRemoval() ；
removeNode(hash(key), key, null, false, true);
}
}
// ( )
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
/*
afterNodeInsertion -> HashMap.removeNode() -> afterNodeRemoval
e
*/
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p 。
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
/*
LinkedHashMap LRU,
1) accessOrder true -->
2) removeEldestEntry --> true , false
*/
まとめ
(1)LinkedHashMapはHashMapから継承され、HashMapのすべての特性を有する.
(2)LinkedHashMap内部では、双方向チェーンテーブルがすべての要素を格納することを維持している.
(3)accessOrderがfalseである場合、要素を挿入する順序で要素を遍歴することができる.
(4)accessOrderがtrueの場合、要素にアクセスする順序で要素を巡回することができる.
(5)LinkedHashMapの実現は非常にすばらしく、多くの方法はHashMapに残されたフック(Hook)であり、これらのHookを直接実現すれば対応する機能を実現することができ、put()を書き換える必要はない.
(6)デフォルトのLinkedHashMapでは古い要素は削除されません.古い要素を削除する必要がある場合は、removeEldestEntry()メソッドを書き換えて削除ポリシーを設定する必要があります.
(7)LinkedHashMapはLRUキャッシュ淘汰戦略を実現するために使用することができる.
LinkedHashMapによるLRUの実装
LinkedHashMapはどのようにLRUキャッシュの淘汰戦略を実現しますか?
まず、LRUが何者なのか見てみましょう.LRU、Least Recently Usedは、最近最も少なく使用されている要素、すなわち、最近最も少なく使用されている要素を優先的に淘汰します.
LinkedHashMapを使用すると、accessOrderをtrueに設定すると、この戦略を実現するのに十分ではないでしょうか.答えは肯定的だ.次のコードを見てください.
public class LRUTest
{
public static void main(String[] args)
{
LRU<Integer,Integer> lru = new LRU(5,0.75f);
lru.put(1,1);
lru.put(2,2);
lru.put(3,3);
lru.put(4,4);
lru.put(5,5);
lru.put(6,6);
lru.put(7,7);
System.out.println(lru.get(4));
lru.put(6,666);
System.out.println(lru);
}
}
class LRU extends LinkedHashMap<K,V>
{
private int capacity;
public LRU(int capacity,int loadFactor)
{
super(capacity,loadFactor,true);
this.capacity = capacity;
}
/**
* removeEldestEntry()
* @param eldest
* @return
*/
public boolean removeEldestEntry(Map.Entry<K,V>eldest)
{
// ,
return size()>this.capacity;
}
}