Java集合のまとめ

7469 ワード

List
順序付けされたセットは、重複する要素を許可し、複数のnull要素を挿入し、要素の索引に従って要素にアクセスすることができます。
ArayList
下の配列が実現され、参画なしのコンストラクタは標準的に10の空き配列を実現します。
位置索引で直接検索

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

インデックスなしで直接挿入し、指定された位置に挿入して存在する配列コピー

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

存在する配列コピーを削除

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArayList拡張容量は、配列サイズが設定容量を超えると自動的に1.5倍の大きさに拡大されます。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //   1.5   
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //System.arraycopy                  ，Arrays.copyOf           ，    System.arraycopy
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Linked List
下の層は双方向チェーンで実現されます。
Vector
Stock
セット
重複要素のセットは含まれていません。最大1つのnull要素が含まれています。
ハイセット
特性:

は、HashMapに基づいて実現され、無秩序容器は、データを格納する一意性に重きを置いている。

により、null値

の存在が許可される。

非スレッドセキュリティ実現

HashSet反復は、fail−fast機構

に従う。
クラスのメンバー変数は、要素を挿入してmapのkeyオブジェクトとして、valueオブジェクトはObjectに変わりません。

private transient HashMap map;

private static final Object PRESENT = new Object();

無参画構造関数

public HashSet() {
        map = new HashMap<>();
    }

HashSet検索、挿入、削除操作はすべてHashMapによって実現されます。

public boolean contains(Object o) {
        return map.containsKey(o);
    }

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
public boolean contains(Object o) {
        return map.containsKey(o);
    }

Linked HashSet
特徴:

はHashSetに継承され、Linked HashMapに基づいて

を実現した。

秩序化容器は、Linked HashMapによって反復順序が要素挿入順序に一致するように実現される。

非スレッドセキュリティ実現

Linked HashSet反復は、fail-fast機構

に従う。

//           HashSet    
public LinkedHashSet() {
        super(16, .75f, true);
    }

このコンストラクタはLinked HashMapを使って実現して、元素FIFOを保証します。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet
特徴:

は、TreeMapに基づいて実現され、TreeMapによって規則化が保証される

。

.操作時間の複雑さを削除し、log（n）

とする。

非スレッドセキュリティ

反復は、fail−fast機構

に従う。

は、null値オブジェクト

を許可しない。
メンバー変数、TreeSet内部はTreeMapに基づいて実現されます。

private transient NavigableMap m;

//      Object
private static final Object PRESENT = new Object();

//     
public TreeSet() {
        this(new TreeMap());
    }

ローズマリー:

//     
public Iterator iterator() {
        return m.navigableKeySet().iterator();
    }
//     
public Iterator descendingIterator() {
        return m.descendingKeySet().iterator();
    }

Map
Mapはcollectionのサブインターフェースまたは実装クラスではなく、各Entryは2つのオブジェクトを持ち、キーオブジェクトと値オブジェクトは、Mapは同じ値のオブジェクトを持つことがありますが、キーオブジェクトは唯一です。
hashMap
特性:

非スレッドセキュリティ

キーオブジェクトは、1つのnull値を許容し、複数のnull値

を許容する。

父類はAbstractMap

です。

無秩序容器

hashTable
特性:

は、null値

を許さない。

スレッドセキュリティ

Hashtableの父はDictionary

です。

無秩序容器

Linked HashMap
特性:

非スレッドセキュリティ

順序のコンテナであり、内部維持リンクのすべてのEntry双方向ポインタは、反復順序とEntry挿入順序が一致することを実現する。
Linked HashMapのNodeはHashMapのNodeを継承しながら、ヘッドポインタを追加します。

static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

TreeMap
特性:

は、マホガニーに基づいて

を実現する。

秩序化容器は、keyオブジェクトクラスによってComprableインターフェースまたはコンパレータCompratorによって並べ替えられた

を実現する。

添削時間の複雑さはlog(n)

です。

非スレッドセキュリティ実現

TreeMapのput方法

public V put(K key, V value) {
        Entry t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry parent;
        // split comparator and comparable paths
        Comparator super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable super K> k = (Comparable super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

その中でcompreの方法

final int compare(Object k1, Object k2) {
        //comparator TreeMap     
        return comparator==null ? ((Comparable super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

基本データタイプ包装類、String類などのデフォルトでComprableインターフェースを実現し、直接keyオブジェクト

とすることができます。

カスタムオブジェクト:

Comprableインターフェースを実現し、Compreto方法

を書き換える。

は、コンパレータ類をカスタマイズし、Compratorインターフェースを実現させるために、以下の構成により、カスタムコンパレータ類

を使用することを指定する。
集合スレッドの安全実現

スレッド安全包装類

Set s = Collections.synchronizedSet(new HashSet(...));

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));


SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

fail-fastメカニズム
すなわち、迅速な失敗機構であり、Java集合のエラー検出機構である。複数のスレッドがセットを構造的に変更する操作を行うと、プログラムはConcerentModificationExceptionに異常が発生します。

//  ArrayList         ，     next  remove      modCount == expectedModCount（       modCount  ）

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

自分で家計簿を書きます。

メンバー変数とメソッドの違いを継承します。