ArayListに精通しています.ArayListについて知りたいことは全部あります.

8920 ワード

目次
  • アラーリストに精通し、アラーリストについて知りたいことは全部
  • 前言
  • ArayList内部構造と一般的な方法で実現
  • 実用化方法
  • 元素addの追加方法
  • get()方法
  • 元素除去
  • どのように拡大しているのか
  • 序列化の問題
  • スレッド安全問題
  • ArayListに精通しています.ArayListについて知りたいことは全部あります.ArrayList 前言
    Javaの開発において、ArayListは最も一般的なデータ構造の一つであり、データリストを格納するためにそれを使用する.ArayListオブジェクトを初期化してから、挿入、指定位置挿入、一括挿入、取得、削除、非空判定、保存量取得など多くの方法が利用できます.
    私たちは使いこなしていますが、ARrayListはどのように私のadd()のデータを保存していますか?私がnewのArayListオブジェクトがある時、彼はどれぐらいの容量がありますか?容量10のArayListを初期化しましたが、11の要素を挿入できます.どのように拡大していますか?次はArayListソースからこれらの問題を見ます.
    ArayList内部構造と一般的な方法で実現した.
    ArayListは配列記憶に基づいている.ArayListのソースコードを開くと、変数が表示されます.
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData;
    変数のコメントは、この配列はArayList要素を格納するためのものであり、配列の長さはArayListの容量であるということです.空のArayListのelement Dataは空の配列であり、初めてデータを追加するとDEFALT_に容量が拡張されます.CAPACITY(つまり10)です.
    実用化の方法
    ArayListには二つの例示的な方法があり、構造関数とも呼ばれています.無参加の実用化方法コードは以下の通りです.
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    
        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    この実用化方法は簡単です.つまり、記憶要素の配列element Dataに値を割り当てます.つまり、空白のObject配列です.
    参考の実用化方法は以下の通りである.
    private static final Object[] EMPTY_ELEMENTDATA = {};    
    public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    本方法はパラメータinitial Capacityを初期化したelement Dataの長さを受信します.もしこの数が0投げ異常より小さいなら、0に等しいと無参画構造関数と同じです.
    要素add()を追加する方法
    追加方法は二つあります.一つは普通の挿入、一つは指定された位置の挿入です.一般的な方法コードは以下の通りです.
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    方法の第一行は容量と関連しており、以下で詳細に分析する.ここでは主に2行目を見て、要素を追加するということは、ターゲット要素eを配列elementaのsizeの下に入れるということです.同時にsizeに1を加えます.指定された位置を見て挿入します.
    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++;
        }
    方法は2つのパラメータを受信します.index--挿入位置、element--ターゲット要素です.最初の行は挿入位置が合理的かどうかをチェックします.
    リストにA,B,C,D,E 5文字が格納されていると仮定して、add(3,「F」)を呼び出し、Fを挿入する.System.arraycopyを呼び出してシフトした後、以下のように示す.
    A
    B
    C
    D
    E
    A
    B
    C
    D
    E
    その後、elemenentData[3]=Fを実行し、全体的なプロセスは、元のA 124124; B 124124124124124124124124124; C 124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124;;;;;;;;;;;;;;;124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124124 A 124 B 124 C 124124 F 124124 124 124; E 124を挿入する.
    ゲット()方法
        public E get(int index) {
            rangeCheck(index);
            return elementData(index);
        }
        E elementData(int index) {
            return (E) elementData[index];
        }
    get方法の最初の行はindexが合法かどうかを確認します.例えば、あなたは確かにget(-1)ができません.そして、elementa配列のindexの下にある要素を取り出します.
    要素を削除
        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;
        }
    remove方法は、elementaのindexの要素を除去し、この要素を返します.numMovedは、シフトが必要な要素の個数です.その後、シフトを呼び出します.最後の要素を削除します.
    どのように拡大しますか
    上にadd()の方法にはensureCapacityInternal()の方法があります.この方法は実際に拡張操作が完了しました.拡張操作は2つの部分に分けられています.1、最小容量の値を決定します.
    この最小容量値はminCapacity変数です.現在のelement Data配列が空なら、minCapacity=10です.さもなければ、minCapacity=size+1です.
    ミニCapacityが10未満の場合は10を取ります.ミニCapacityがelementaの長さより大きい場合は、grow()方法を呼び出して拡大します.
    2、grow()の呼び出し方法、grow()の方法は以下の通りです.
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5 
            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:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    この方法では、elementa配列の新しい容量を決定し、Arays.co pyOfを呼び出して拡張を完了します.この3つの数値に基づいて、新しい容量を決定します.
  • 最小容量(size+1)ミニCapacity
  • 現在の容量の1.5倍のelement Data.lengt 1.5倍
  • 許容される最大容量
  • new ArayList()を呼び出し、初期化すると、elementaは空です.初めてadd()を呼び出すと、10に拡張されます.11番目の要素を追加すると、拡張値は15です.10+(10>>1)=15です.16番目の要素を追加すると、15+(15>1)=22に拡張されます.
    したがって、拡大が必要とされる度に1.5倍に拡大され、最大でInteger.MAXUVALEを超えないと大まかに理解できます.
    序文化の問題
    前に述べたように、ArayListは配列に基づいています.データはその配列タイプのメンバー変数に格納されています.つまり、これです.
        transient Object[] elementData; 
    この変数はtranientで修飾されています.tranientのキーワードの役割はこう定義されています.
    tranientでインスタンス変数を宣言すると、オブジェクトが格納されているときの値は維持されません.つまり、tranientキーでマークされているメンバー変数は、プログレッシブプロセスに参加しません.
    配列要素は序列化に参加しないのですか?私が苦労して追加したデータがなくなったのではないですか?
    ArayListはwriteObject()とreadObject()の方法を実現し、プログレッシブとアンチプログレッシブをカスタマイズしたものに相当します.element Data変数はtranientで修飾されていますが、実際にはelementa Dataの要素はプログレッシブ時に書き込まれています.方法は以下の通りです.
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out size as capacity for behavioural compatibility with clone()
            s.writeInt(size);
    
            // Write out all elements in the proper order.
            for (int i=0; i
    なぜこのようにしますか?私たちは先に述べたように、ArayListはダイナミックな拡充をしています.だから、arrayListが10容量を持っている時、実際には一つの要素しか保存されていないかもしれません.つまり、size=1で、element Data.length=10です.この時、プログレッシブelementaは何をしますか?後ろは全部空の値です.
    スレッドの安全問題
    ArayListはスレッドが安全でないため、マルチスレッド環境ではエラーが発生しやすい.以下の例では20スレッドを起動し、共有するArayListに各スレッドを20要素挿入し、最終的にはArayListの長さを出力する.ArayListがスレッドが安全であれば、最終的な結果は200.
    public class Test {
    
        public static void main(String[] args)throws Exception {
            ArrayList list = new ArrayList<>();
            final CyclicBarrier cb=new CyclicBarrier(20);
            final CountDownLatch latch=new CountDownLatch(20);
            for(int i=0;i<20;i++){
                Thread t1 = new Thread(()->{
                    try{
                        long cur = System.nanoTime();
                        Thread.sleep(100);
                        System.out.println(cur+"    ");
                        cb.await();
                        for(int j=0;j<20;j++){
                            list.add(j);
                        }
                        System.out.println(cur+"    ");
                        latch.countDown();
                    }catch (InterruptedException |BrokenBarrierException e){
                        e.printStackTrace();
                    }
                });
                t1.start();
            }
            latch.await();
            System.out.println("    :"+list.size());
        }
    }
    私は一回勝手に実行して、次のような結果を得ました.
    33927850979931は33927850899613の準備ができました.33927850816171は33927850686322の準備ができました.33927850595294は33927850751470の準備ができました.33927851787878787878789628は339278787878787878787878787878787878787878787878787878787878786の準備ができました.33927852038799の準備ができました.33927851433286は33927852370336の準備ができました.33927852448424の準備ができました.33927852126703は33927852215500の準備ができました.339278521986の実行が完了しました.33927850751470の実行が完了しました.339278511680の実行が完了しました.33927851821046の実行が完了しました.33927852373336の実行が完了しました.339278513286の実行が完了しました.ラインオーバー33927852448424実行済み配列サイズ:397
    明らかな結果とは違って、何回か実行すると、新聞配列が境界を越えていることが分かります.だから、ArayListはスレッドが安全ではありません.