Javaベース-コレクション

21760 ワード

JAVAコレクション
データを処理する過程で、あるタイプのデータを格納するためにコンテナが必要になることがよくあります.Javaの配列はこのようなコンテナです.しかしJavaの配列には限界があり,定義後の配列長は可変ではなく,配列長を超えるとデータを格納できなくなる.多くの場合、データがどれだけあるか分からないので、不定長のコンテナを持ってデータを格納する必要があります.これが集合です.Javaの集合は汎用的な実装を採用しており、どのタイプのオブジェクトデータも格納できます.Javaの配列:

package test;

import java.util.Arrays;

public class Arr
{
    public static void main(String[] args)
    {
        int[] arr = new int[2];
        arr[0] = 1;
        arr[1] = 2;
        // arr[2] = 3; //     

        System.out.println(Arrays.toString(arr)); //   ：[1, 2]
    }
}

Javaの集合は主に4種類に分けられます.

Listリスト、秩序、繰り返し可能

Queueキュー、順序付け、

繰り返し可能

Setセット、

を繰り返してはいけません

Mapマッピング、無秩序、キー一意、値非一意

各コレクション・タイプには、次のような複数の特定のインプリメンテーション・クラスが含まれます.
1.Listリスト、順序付け、繰り返し可能
一般的なList実装クラスは,ArrayList,LinkedList,Vector,Stackである.
1.1 ArrayListリスト
ArrayList配列リストは、秩序正しく、繰り返し可能であり、内部はArrayによって実現される.オブジェクトを初期化するときに、送信サイズがない場合、リストのサイズはDEFAULT_CAPACITYのデフォルト値10です.リスト容量が足りない場合、リストに要素を追加し続けると、配列コピーにより元の配列が拡張され、拡張方式はint newCapacity = oldCapacity + (oldCapacity >> 1)、すなわち新しい配列容量newCapacityが10 + 10/2 = 15である.複数の要素を一度に6個追加する場合、リスト最小容量minCapacityは10 + 6 = 16を必要とし、新しい容量newCapacityは最小容量minCapacityより小さい場合、新しい配列容量は最小容量値newCapacity = minCapacityをとる.配列リストを挿入、削除するには、配列をコピーして並べ替える必要があります.そのため、どのくらいのデータが格納されているかがわかる場合は、できるだけ初期容量を初期化し、性能を向上させます.

List a = new ArrayList();
a.add(11);
a.add("aaa"); //     
a.get(1);     //         
a.remove(1);  //     2

1.2 LinkedList双方向チェーンテーブル
LinkedListは双方向チェーンテーブルであり、すなわち各要素に前後の要素を指すポインタがある.チェーンテーブルである以上、シーケンス読み出しの効率は非常に高く、ランダム読み出しの効率は低い.indexビット要素をランダムに取得すると、チェーンテーブルはindexとチェーンテーブルの長さの1/2の大きさを比較し、小さい場合はチェーンテーブルのヘッダから要素を検索し、大きい場合はチェーンテーブルの末尾から要素を検索します.

LinkedList l =new LinkedList();
l.add(1);
l.add(2);
l.getFirst(); //        
l.getLast();  //         
l.remove(1); //     2

対照的にArrayListはランダム読み出しデータが多い場合はArrayListを使用すると性能が高く、挿入削除が多い場合はLinkedListを使用すると性能が高い.
1.3 Vectorベクトル、スレッドの安全なリスト
ArrayListと同様に配列によって実現されているが、Vectorはスレッドセキュリティであり、つまり同じ時間に1つのスレッドしかVectorにアクセスできないため、スレッドセキュリティと同時に性能のロスをもたらすため、一般的にArrayListが用いられる.Vectorの拡張もArrayListとは異なり、拡張値を設定することができ、デフォルトでは1回の拡張ごとに元の倍になる.

Vector v = new Vector();
v.add("aa");
v.add("bb");
v.get(1);
v.remove(1);

1.4 Stackスタック、後進先出(LIFO)
StackはVectorから継承されるので配列で実現され、スレッドが安全なスタックです.StackはVectorから継承されるためVectorで定義されたメソッドを持つが、スタックデータ型としてはVectorでスタックに関係のないメソッドは推奨されず、スタックデータ型を破壊しないようにできるだけStackで定義されたスタック関連メソッドのみを使用する.

Stack s = new Stack();
s.push(1);
s.push(2);
s.pop(); //          
s.peek(); //        ，

1.5 ArrayQueue配列キュー、先進後出(FIFO)
ArrayQueueは配列実装のキューであり,キューの最後からデータを加え,キューヘッダのみがデータを削除し,キューデータをランダムに読み出すことができる.

ArrayQueue q = new ArrayQueue(12);
q.add(1);
q.add(2);
q.get(1);
q.size();、
q.remove(0);

2.Queueキュー、秩序正しく、繰り返し可能
Queueから継承されるキューには、ArrayDeque、LinkedList、PriorityQueueがあります.
2.1 ArrayDeque配列による両端キュー
ArrayDequeはキューですがスタックとしても使えますし、Stackよりも効率的です.両端キューとして、キューの両端に要素を挿入および削除できます.追加要素が容量制限を超えると、両方の容量の新しい配列が作成され、元の配列の内容が新しい配列にコピーされます.

ArrayDeque d = new ArrayDeque();
d.addFirst(11);
d.addLast(22);
d.pollFirst();
d.pollLast(); //          
d.peekLast(); //           
d.peekFirst();
d.push(44);
d.pop();

2.2 LinkedListキューも双方向チェーンテーブル
上記1.2に述べたように、ここでは省略する.ArrayDequeがおすすめです.
2.3 PriorityQueue優先キュー、配列実装のツリー
PriorityQueueは、完全に二叉木で実現される小さなトップスタックである(いずれの非リーフノードの重み値も、その左右のサブノードの重み値より大きくない).

PriorityQueue q = new PriorityQueue();
q.offer(1);
q.offer(2);
q.offer(3); //     
q.peek();   //       
q.poll();   //

住所の詳細:PriorityQueue
3.Mapマッピング/辞書、無秩序、キー値ペア、キー一意
一般的なMap実装は、HashMap、TreeMap、LinkedHashMap
3.1 HashMapハッシュマッピング/辞書
HashMapはkey->valueのキー値対データであり、keyは一意であり、keyとvalueはnullであってもよい.HashMapはHashTableと似ており,HashTableはスレッド同期を実現しており,Objectスーパークラス解析章ではHashTableのデータ格納方式を簡単に紹介している.HashMapは無秩序な辞書で、遍歴時に要素の順序を保証しません.HashMapの作成時にデフォルトで初期容量サイズ(デフォルト16)が設定され、ロードファクタ(デフォルト0.75、拡張容量のバルブ値)が設定されます.ロードファクタ=格納された要素の個数/総容量サイズです.もちろん、この2つの値は手動で設定することもできます.HashMapのデータ格納構造は、次の図のようになっている.HashMapは、1つのデータを挿入する際にkey値に対してhashを行い、得られた値と容器の大きさnを1減らして&を演算してバケツの位置を得る.すなわち、i = (n - 1) & hash、iはバケツの位置である.バケツにエレメントの有無を検索し、直接挿入しないで、ある場合はエレメントkey値が同じかどうかを比較し、同じように新しい値で置き換えます.バケツの位置計算はなぜ(n - 1) & hashですか?まずhash値の計算を見てみましょう.

// hash()         
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash()関数はkeyに値を取った後、整数を返します.また、HashMapの容量nが常に2のべき乗(デフォルトは16)であるため、大きなコラム Javaベース-集合de>n-1のバイナリは常に最上位1であり、他のビットは0の数である.例えば:10...0、この数は整数と&演算するとhash / nの余数が得られ、余数の取値範囲は0~n-1であり、巧みな設計である.関連ソース、ここでは一部を切り取りました.

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    
    //     
    public HashMap(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);
        this.loadFactor = loadFactor;
        
        //      
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    /**
     *     ，   2   
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    //     
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * //          
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            // resize          
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
     
    //   hash 
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }   
}

3.2 TreeMap赤と黒のツリーで実現したkey->valueコンテナ、並べ替え可能
赤黒樹は自己平衡二叉探査樹で、紹介します.詳細:https://www.cnblogs.com/skywang12345/p/3245399.htmlhttps://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html
3.3 LinkedHashMapチェーンテーブルのマッピング/辞書
LinkedHashMapはHashMapから継承されているので、HashMapのすべての特性を持っています.同時に双方向チェーンテーブルの特性を実現し、要素の挿入順序を保持します.

LinkedHashMap l = new LinkedHashMap<>();
l.put("a", 11);
l.put("b", 22);
l.put("c", 33);
l.put("d", 44);
Iterator ita = l.entrySet().iterator();
while (ita.hasNext()) {
    Map.Entry entry = (Map.Entry) ita.next();
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

//   ：
a=11
b=22
c=33
d=44

4.Set集合、繰り返し不可
一般的なSet実装は、HashSet、LinkedHashSet、TreeSet、EnumSetである.
4.1 HashSetハッシュセット
HashSetはHashMap実装の集合に基づいて,HashMapをいくつかパッケージ化した.データの構造は図のようです:HashMapと異なって要素の保存はチェーンテーブルの形式で、データを挿入する時チェーンテーブルを遍歴して同じデータがあるかどうかを調べて、あるならfalseを返して、trueを返していません.

HashSet s = new HashSet();
s.add("aa");
System.out.println(s.add("aa")); // false
System.out.println(s.add("bb")); // true

4.2 LinkedHashSetチェーンテーブルセット
HashSetから継承されるLinkedHashMapと似ており、LinkedHashMapのパッケージです.
4.3 TreeSet赤黒樹集合
TreeMapに似ています.TreeMapのパッケージです.
本文はJavaの中の集合クラスについて簡単に紹介しただけで、詳細な設計はソースコードを見て詳細を理解してください.

1.PostgreSQL-インストールと基本構成(学習ノート)

Java毎日1題10