ロックスクリーン面接問題百日百刷-java大工場八股文(day 3)

面接に向けた准备をするために、毎日各所で収集した面接试験の中からいくつかの経典の面接问题を选んで分かち合い、参考にして答えを出します.答えの中でテーマに関する拡張をし、思考のために一定の问题を投げ出す可能性があります.これらのテーマには、具体的な会社、求人タイプ、面接段階を表示します.これらの面接問題は、ロックスクリーン面接問題appとウィジェットに収録されます.その他の面接問題は毎日更新中で、使用とサポートに感謝します.公式サイトの住所:https://www.demosoftware.cc/#/introductionPage、次は今日の面接問題です.
====ArrayListとLinkedListの実現原理と前者の拡張メカニズム?アリ雲[一面]以下の内容はjdk 1である.8説明:ArrayList実現原理:Arraylist下位層は一つのObject配列elementDataでデータを保存する:transient Object[]elementData;//non-private to simplify nested class access ArrayListの作成から見ると、一般的にnewによって関数を構築することによってArrayListのソースコードを見ることができます.

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_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);
        }
}
public ArrayList(Collection extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

単純に、無パラメトリック構造では空の配列しか作成されず、初期化配列サイズのコンストラクタでは容量を知っているArrayListが作成され、別のArrayListで新しいArrayListのコンストラクタが初期化されます.ArrayListの操作を見てください:1)追加:

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);
}

ここでmodCountは,ArrayListに対してサイズを変更するたびに自己増分操作を行う変数であり,修正回数を記録する.コアの一般的な質問の1つの方法はこのgrow()方法であり,これはArrayList中の要素の配列(上述したデータを格納する)elementData容量が足りない場合の拡張動作である.ここでは、空のパラメトリックコンストラクタでArrayListを作成するときに、初めてArrayListに要素を追加するときに拡張操作を行います.容量が十分かどうかを判断するのは、if(minCapacity-elementData.length>0)がgrowで、コアの一部がint newCapacity=oldCapacity+(oldCapacity>>1)です.新しい容量は古い容量の1.5倍(oldCapacity>>1は実際にはoldCapacityで2を除く操作)です.ここで拡張トリガ条件は、無パラメトリックコンストラクタを使用して初めて要素を追加し、要素を追加したときに配列の長さが足りないと判断した場合です.2)削除:

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;
  }

コードを見るのは簡単です.配列のコピーをして、削除する場所の要素の後ろの要素を移動し、古い配列をnullにしてゴミ回収をします.remove(Object O)を指定する方法も、まず対応する要素の下付きを探して、上のコードとあまり差のない操作をします.興味があればソースコードを見てもいいです.クエリーは何も言うことはありません.最下位は配列ストレージで、クエリーは簡単です.ソースコードは自分で見ることができます.LinkedList実装原理:LinkedListストレージは双方向チェーンテーブルによって実現される:

transient Node first;
transient Node last;
private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
 }

その空のパラメトリック構造は何もしないで、パラメトリック構造LinkedList(Collection extends E>c)も要素を追加する操作に重点を置いているので、直接そのいくつかの操作を話して、ここではチェーンテーブルの削除変更の操作を理解する必要があります.LinkedListのこれらの操作はこれらに基づいているからです.資料を探して理解してほしいです.ここは幅が限られていて、説明しません.1)追加:ヘッダーの追加:

public void addFirst(E e) {
        linkFirst(e);
 }
private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
}

上のLinkedListについて最初に述べたように、LinkedListメンバー変数にはfirstとlastが保存されていることがわかります.ここでは頭から挿入するのと尾から挿入するのは基本的に動作が一致していますが、保存位置が異なるだけで、コードを見ると分かりやすく、チェーンテーブルの操作です.add()の方法は尾に新しい要素を挿入することです.2)removeFirst()とremoveLast()およびremove()(removeとremoveFirst()の操作が一致している)を削除するのは、簡単にチェーンテーブルのヘッダーやテーブルの末尾を取り除く操作で、自分でソースコードを見ることができ、チェーンテーブルの操作に詳しい学生は簡単に理解でき、余計なことを言わない.remove(int index):

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
 }
Node node(int index) {
        // assert isElementIndex(index);
//               
//   index    。    
        //  index <        1/2,       ;    
        //   ，      。
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
  }
E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
}

ここではまずindexに基づいてLinkedListに格納されているノードを見つけ、上図node()メソッドを参照してから要素削除操作を開始し、unlink()メソッドを参照してチェーンテーブルの削除操作を熟知しているので、分かりやすく、削除した要素がヘッダー後表の末尾であるかどうかを判断し、そうであれば簡単に値を付けておけばよく、そうでなければ対応する削除操作を行う.Remove(Object o)このメソッドも、このlistにこの要素があるかどうかを先に見つけて、検索してからunlink()メソッドを呼び出して削除します.3)LinkedList検索操作上の削除操作では、削除する手順で既に説明している(上のnodeメソッド)を先に検索し、自分でソースコードと照合して検索操作を確認してください.