Javaコレクションフレームワークの詳細な分析

この記事では、java に関する関連知識を提供します。主にコレクション フレームワークに関連する問題を紹介します。Java コレクション フレームワークは、優れたパフォーマンスと使いやすさを備えた一連のインターフェイスとクラスを提供します。 java.util パッケージが皆さんのお役に立てば幸いです。

## 推奨学習: 「

java 学習チュートリアル 」

1. はじめに

1. コレクション フレームワークの概要

Java コレクション フレームワークは、優れたパフォーマンスと使いやすさを備えたインターフェイスとクラスのセットを提供しており、

java.util パッケージにあります。コンテナには主に Collection と Map が含まれます。Collection にはオブジェクトのコレクションが格納され、Map にはキーと値のペア (2 つのオブジェクト) のマッピング テーブルが格納されます。

2. 関連コンテナの概要

2.1 セット関連

• ##TreeSet は赤黒ツリーの実装に基づいており、範囲に基づいた要素の検索などの順序付けされた操作をサポートします。ただし、検索効率は HashSet ほど良くなく、HashSet の検索時間は O(1) であるのに対し、TreeSet の検索時間は O(logN)
  
• HashSet## となります。 # ハッシュ テーブルの実装に基づいて、高速検索をサポートしますが、順序付けされた操作はサポートしません。また、要素の挿入順序情報が失われます。これは、Iterator を使用して HashSet を走査することによって得られる結果が不確実であることを意味します。
  
LinkedHashSet
• HashSet の検索効率を持ち、内部的に二重リンク リストを使用して要素の挿入順序を維持します。
  
2.2 リスト関連

ArrayList
• 動的配列実装に基づいて、ランダム アクセスをサポートします。
  
Vector
• ArrayList に似ていますが、スレッドセーフです。
  
LinkedList
• 二重リンク リストの実装に基づいて、連続的にのみアクセスできますが、要素はリンク リストの途中ですばやく挿入および削除できます。それだけでなく、LinkedList はスタック、キュー、デックとしても使用できます。
  
2.3 キュー関連

LinkedList
• は双方向キューを実装できます。
  
PriorityQueue
• ヒープ構造に基づいて、優先キューを実装するために使用できます。
  
2.4 マップ関連

TreeMap
• 赤黒ツリーの実装に基づいています。
  
HashMap
• ハッシュ テーブルの実装に基づきます。
  
HashTable
• HashMap に似ていますが、スレッドセーフです。つまり、データの不整合を引き起こすことなく、複数のスレッドが同時に HashTable に書き込むことができます。これはレガシー クラスであるため、使用しないでください。 ConcurrentHashMap
  を使用してスレッド セーフをサポートできるようになりました。ConcurrentHashMap はセグメンテーション ロックを導入するため、より効率的になります。 LinkedHashMap
二重リンク リストを使用して、要素の順序を挿入順または最も最近使用された (LRU) 順に維持します
• 3。コレクション フォーカス
  

Collection インターフェイスは、非一意で順序付けされていないオブジェクトのセットを格納します。

List インターフェイスは、非一意で順序付けされたオブジェクトのセットを格納します。

• Set インターフェイスは、順序付けされていない一意のオブジェクトのセットを格納します。
• Map インターフェイスは、キーと値のオブジェクトのセットを格納し、キーから値へのマッピングを提供します。
• ArrayList は、可変長の配列を実装します。 、メモリ内に連続した領域を割り当てます。要素のトラバースと要素へのランダム アクセスがより効率的です
• LinkedList はリンク リスト ストレージを使用します。
• HashSet はハッシュ アルゴリズムを採用して Set を実装しています
• HashSet の最下層は HashMap を使用して実装されており、hashCode が使用されるためクエリ効率が高くなります。要素を直接決定するアルゴリズムを使用 メモリアドレス、高い追加および削除効率
• #2. ArrayList 解析
• 1. ArrayList は

# を使用

##methodboolean add(Object o)リストの最後に順番に要素を追加します。開始インデックス位置は 0index 位置 0 からリスト内の要素数までの値である必要があります取り出した要素はObject型なので、使用前に型変換する必要があります。

Description

#void add(intindex, Object o)

Add指定されたインデックス位置の要素、

int size()戻り値リスト内の要素の数

Object get(int index)

指定されたインデックス位置にある要素を返します。

boolean contains(Object o)Determineリストが指定された要素が存在するかどうか

boolean delete(Object o)

リストから要素を削除します

Object delete(intindex)

リストから指定された位置にある要素を削除します。開始インデックスは 0

から始まります。

2. ArrayList の概要

• ArrayList は動的に拡大および縮小できるインデックス シーケンスであり、配列によって実装された List クラスに基づいています
• このクラスは、動的再配布 Object[] 配列では、各クラス オブジェクトには、カプセル化する Object[] 配列の長さを示す、capacity [capacity] 属性があり、要素が ArrayList に追加されると、属性値は自動的に増加します。 ArrayList に多数の要素を追加する場合は、ensureCapacity メソッドを使用して容量を一度に増やすことができます。これにより、再割り当ての回数が減り、パフォーマンスが向上します。
• ArrayList の使用法は、ArrayList の使用法と似ています。 Vector は古いコレクションであり、多くの欠点があるため、使用することはお勧めできません

さらに、ArrayList と Vector の違いは次のとおりです: ArrayList はスレッド安全ではありません。スレッドが同じ ArrayList コレクションにアクセスする場合、プログラムはコレクションの同期を手動で確保する必要がありますが、Vector はスレッドセーフです。

3. ソースコードの分析

3.1 継承構造と階層関係

public class ArrayList<e> extends AbstractList<e>
        implements List<e>, RandomAccess, Cloneable, java.io.Serializable</e></e></e>

ここでは、いくつかのインターフェイスについて簡単に説明します

• RandomAccess インターフェイス
  これはマークされたインターフェイスです。API ドキュメントを見ると、その機能は高速ランダム アクセスを使用することです。効率の問題に関しては、このインターフェイスが実装されている場合は、通常のArrayList のように for ループを使用してトラバースするとパフォーマンスが高くなります。このインターフェースが実装されていない場合は、linkedList などのパフォーマンスの高い Iterator を使用して反復処理を行ってください。したがって、このマークは、データを取得するためにどの方法を使用した方がパフォーマンスが優れているかを知らせるだけです。
• Clone 可能なインターフェイス
  このインターフェイスを実装した後、Object.Clone() メソッドを使用できます。
• シリアル化可能なインターフェイス
  このシリアル化インターフェイスを実装すると、このクラスがシリアル化できることを示します。シリアル化とは何ですか?簡単に言うと、クラスからバイトストリームへ、そしてバイトストリームから元のクラスへ転送できるということです。

ここでの継承構造は、IDEA の [ナビゲート] > [型階層] から確認できます。

3.2 プロパティ

//版本号
private static final long serialVersionUID = 8683452581122892189L;
//缺省容量
private static final int DEFAULT_CAPACITY = 10;
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储的数组元素
transient Object[] elementData; // non-private to simplify nested class access
//实际元素大小，默认为0
private int size;
//最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3.3 構築方法

/**
 * 构造具有指定初始容量的空列表
 * 如果指定的初始容量为负，则为IllegalArgumentException
 */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);
    }}/**
 * 默认空数组的大小为10
 * ArrayList中储存数据的其实就是一个数组，这个数组就是elementData
 */public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/**
 * 按照集合迭代器返回元素的顺序构造包含指定集合的元素的列表
 */public ArrayList(Collection extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 转换为数组
        //每个集合的toarray()的实现方法不一样，所以需要判断一下，如果不是Object[].class类型，那么久需要使用ArrayList中的方法去改造一下。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 否则就用空数组代替
        this.elementData = EMPTY_ELEMENTDATA;
    }}

3.4 自動拡張

配列に要素を追加するたびに、追加された要素の数が現在の配列の長さを超えないかどうかを確認する必要があります。を超えると、データ追加のニーズを満たすために配列が拡張されます。配列の拡張は、パブリック メソッド ensureCapacity(int minCapacity) を通じて実現されます。 実際に多数の要素を追加する前に、ensureCapacityを使用してArrayListインスタンスの容量を手動で増やし、増分再割り当ての数を減らすこともできます。

配列を拡張すると、古い配列の要素が新しい配列にコピーされ、配列の容量が増加するたびに元の容量の約 1.5 倍になります。 **この操作のコストは非常に高いため、実際の使用ではアレイ容量の拡張を避けるように努める必要があります。保存する要素の数が予測できる場合は、配列の拡張を避けるために ArrayList インスタンスを構築するときにその容量を指定する必要があります。または、実際のニーズに応じて、ensureCapacity メソッド を呼び出して、ArrayList インスタンスの容量を手動で増加します。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //判断初始化的elementData是不是空的数组，也就是没有长度
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //因为如果是空的话，minCapacity=size+1；其实就是等于1，空的数组没有长度就存放不了
        //所以就将minCapacity变成10，也就是默认大小，但是在这里，还没有真正的初始化这个elementData的大小
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否够用
    return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用
    /*第一种情况：由于elementData初始化时是空的数组，那么第一次add的时候，
    minCapacity=size+1；也就minCapacity=1，在上一个方法(确定内部容量ensureCapacityInternal)
    就会判断出是空的数组，就会给将minCapacity=10，到这一步为止，还没有改变elementData的大小。
    第二种情况：elementData不是空的数组了，那么在add的时候，minCapacity=size+1；也就是
    minCapacity代表着elementData中增加之后的实际数据个数，拿着它判断elementData的length
    是否够用，如果length不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。*/ 
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);}//ArrayList核心的方法，能扩展数组大小的真正秘密。private void grow(int minCapacity) {
    //将扩充前的elementData大小给oldCapacity
    int oldCapacity = elementData.length;
    //newCapacity就是1.5倍的oldCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    /*这句话就是适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，
    所以这个判断成立，在这里就是真正的初始化elementData的大小了，就是为10.前面的工作都是准备工作。
    */
    if (newCapacity - minCapacity  0)
        newCapacity = hugeCapacity(minCapacity);
    //新的容量大小已经确定好就copy数组，改变容量大小。
    elementData = Arrays.copyOf(elementData, newCapacity);}//用来赋最大值private static int hugeCapacity(int minCapacity) {
    if (minCapacity  MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;}

3.5 add() メソッド

/**
 * 添加一个特定的元素到list的末尾。
 * 先size+1判断数组容量是否够用，最后加入元素
 */public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;}/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */public void add(int index, E element) {
    //检查index也就是插入的位置是否合理。
    rangeCheckForAdd(index);
    //检查容量是否够用，不够就自动扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这个方法就是用来在插入元素之后，要将index之后的元素都往后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;}

add() メソッドが呼び出されると、実際の関数が呼び出されます:

add→ensureCapacityInternal→ensureExplicitCapacity(→ give→hugeCapacity )

たとえば、空の配列を初期化して値を追加した後、最初に容量が自動的に拡張されます

3.6 TrimToSize()

現在のリストに保存されている実際の要素のサイズに合わせて基になる配列の容量を調整する関数

public void trimToSize() {
    modCount++;
    if (size <h3>3.7 delete() メソッド</h3><p><code>remove( )</code>このメソッドには 2 つのバージョンもあります。1 つは <code>remove(int index)</code>指定された位置にある要素を削除するもので、もう 1 つは <code>remove(Object o)</code> を削除するものです。 <code>o.equals(elementData[index])</code>Elements を満たす最初のもの。削除操作は <code>add()</code> 操作の逆のプロセスであり、削除ポイントの後の要素を 1 つ前に移動する必要があります。 GC が機能するには、最後の位置に明示的に <code>null</code> 値を割り当てる必要があることに注意してください。 </p><pre class="brush:php;toolbar:false">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; //清除该位置的引用，让GC起作用

        return oldValue;
    }

3.8 その他のメソッド

ここでは、コア メソッドについて簡単に説明します。ソース コードを参照すると、他のメソッドをすぐに理解できます。

3.9 フェイルファスト メカニズム

ArrayList の採用 modCount パラメータを記録することにより、高速障害メカニズムが実装されます。同時変更に直面した場合、反復子はすぐに完全に失敗し、ConcurrentModificationException 例外をスローします。将来、不特定の時点で任意の不特定の動作が発生する危険を冒すことはありません。

4. 概要

• ArrayList は null を格納できます
• ArrayList は本質的に elementData 配列です
• ArrayList と array の違いは、要素データを自動的に展開できることです。重要なメソッドは gorw() メソッドです。
• ArrayList のremoveAll(collection c)とclear()の違いは、removeAllは指定された要素をバッチで削除できるのに対し、clearはコレクション内のすべての要素を削除することです
• ArrayList は本質的に配列であるため、データ クエリでは非常に高速ですが、挿入と削除に関してはパフォーマンスが大幅に低下し、目的の効果を得るには大量のデータを移動する必要があります。
• ArrayList は RandomAccess で実装されているため、それを走査するときは for ループを使用することをお勧めします

3. LinkedList 分析

1. LinkedList を使用します

#void addLast(Object o)#要素を末尾に追加しますリストの # Object getFirst()リストの最初の要素を返しますObject getLast()リストの最後の要素を返しますObject RemoveFirst()リストの最初の要素を削除して返します##Object RemoveLast()

2、LinkedList介绍

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue_的类(它是个接口名字)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装

3、源码分析

3.1 继承结构与层次

public class LinkedList<e>
    extends AbstractSequentialList<e>
    implements List<e>, Deque<e>, Cloneable, java.io.Serializable</e></e></e></e>

这里可以发现LinkedList多了一层AbstractSequentialList的抽象类，这是为了减少实现顺序存取（例如LinkedList）这种类的工作。如果自己想实现顺序存取这种特性的类(就是链表形式)，那么就继承 这个AbstractSequentialList抽象类，如果想像数组那样的随机存取的类，那么就去实现AbstracList抽象类。

• List接口
  列表add、set等一些对列表进行操作的方法
• Deque接口
  有队列的各种特性
• Cloneable接口
  能够复制，使用那个copy方法
• Serializable接口
  能够序列化。
• 没有RandomAccess
  推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator

3.2 属性与构造方法

transient关键字修饰，这也意味着在序列化时该域是不会序列化的

//实际元素个数transient int size = 0;
//头结点transient Node<e> first;
//尾结点transient Node<e> last;</e></e>

public LinkedList() {}public LinkedList(Collection extends E> c) {
    this();
    //将集合c中的各个元素构建成LinkedList链表
    addAll(c);}

3.3 内部类Node

//根据前面介绍双向链表就知道这个代表什么了，linkedList的奥秘就在这里private static class Node<e> {
    // 数据域（当前节点的值）
    E item;
    //后继
    Node<e> next;
    //前驱
    Node<e> prev;
    // 构造函数，赋值前驱后继
    Node(Node<e> prev, E element, Node<e> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }}</e></e></e></e></e>

3.4 核心方法add()和addAll()

public boolean add(E e) {
    linkLast(e);
    return true;}void linkLast(E e) {
    //临时节点l(L的小写)保存last，也就是l指向了最后一个节点
    final Node<e> l = last;
    //将e封装为节点，并且e.prev指向了最后一个节点
    final Node<e> newNode = new Node(l, e, null);
    //newNode成为了最后一个节点，所以last指向了它
    last = newNode;
    if (l == null)
        //判断是不是一开始链表中就什么都没有，如果没有，则new Node就成为了第一个结点，first和last都指向它
        first = newNode;
    else
        //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的 最后一个节点，原先的最后一个节点就变成了倒数第二个节点
        l.next = newNode;
    //添加一个节点，size自增
    size++;
    modCount++;}</e></e>

addAll()有两个重载函数，addAll(Collection extends E>)型和addAll(int,Collection extends E>)型，我们平时习惯调用的addAll(Collection<?extends E>)型会转化为addAll(int,Collection extends<e>)</e>型

public boolean addAll(Collection extends E> c) {
    return addAll(size, c);}public boolean addAll(int index, Collection extends E> c) {
    //检查index这个是否为合理
    checkPositionIndex(index);
    //将集合c转换为Object数组
    Object[] a = c.toArray();
    //数组a的长度numNew，也就是由多少个元素
    int numNew = a.length;
    if (numNew == 0)
        //如果空的就什么也不做
        return false;

    Node<e> pred, succ;
    //构造方法中传过来的就是index==size
    //情况一：构造方法创建的一个空的链表，那么size=0，last、和first都为null。linkedList中是空的。
    //什么节点都没有。succ=null、pred=last=null
    //情况二：链表中有节点，size就不是为0，first和last都分别指向第一个节点，和最后一个节点，
    //在最后一个节点之后追加元素，就得记录一下最后一个节点是什么，所以把last保存到pred临时节点中。
    //情况三index！=size，说明不是前面两种情况，而是在链表中间插入元素，那么就得知道index上的节点是谁，
    //保存到succ临时节点中，然后将succ的前一个节点保存到pred中，这样保存了这两个节点，就能够准确的插入节点了
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<e> newNode = new Node(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        /*如果succ==null，说明是情况一或者情况二，
        情况一、构造方法，也就是刚创建的一个空链表，pred已经是newNode了，
        last=newNode，所以linkedList的first、last都指向第一个节点。
        情况二、在最后节后之后追加节点，那么原先的last就应该指向现在的最后一个节点了，
        就是newNode。*/
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;}//根据引下标找到该结点并返回Node<e> node(int index) {
    //判断插入的位置在链表前半段或者是后半段
    if (index > 1)) {
        Node<e> x = first;
        //从头结点开始正向遍历
        for (int i = 0; i  x = last;
        //从尾结点开始反向遍历
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }}</e></e></e></e>

3.5 remove()

/*如果我们要移除的值在链表中存在多个一样的值，那么我们
会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做
*/public boolean remove(Object o) {
    if (o == null) {
        for (Node<e> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<e> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;}不能传一个null值E unlink(Node<e> x) {
    // assert x != null;
    final E element = x.item;
    final Node<e> next = x.next;
    final Node<e> 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的前后指向都为null了，也把item为null，让gc回收它
    x.item = null;
    size--;
    modCount++;
    return element;}</e></e></e></e></e>

3.6 其他方法

**get(index)、indexOf(Object o)**等查看源码即可

3.7 LinkedList的迭代器

在LinkedList中除了有一个Node的内部类外，应该还能看到另外两个内部类，那就是ListItr，还有一个是DescendingIterator内部类

/*这个类，还是调用的ListItr，作用是封装一下Itr中几个方法，让使用者以正常的思维去写代码，
例如，在从后往前遍历的时候，也是跟从前往后遍历一样，使用next等操作，而不用使用特殊的previous。
*/private class DescendingIterator implements Iterator<e> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }}</e>

4、总结

• linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。linkedList能存储null值
• 跟ArrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好，从源码中看，它不存在容量不足的情况
• linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值
• linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口

四、List总结

1、ArrayList和LinkedList区别

• ArrayList底层是用数组实现的顺序表，是随机存取类型，可自动扩增，并且在初始化时，数组的长度是0，只有在增加元素时，长度才会增加。默认是10，不能无限扩增，有上限，在查询操作的时候性能更好
• LinkedList底层是用链表来实现的，是一个双向链表，注意这里不是双向循环链表,顺序存取类型。在源码中，似乎没有元素个数的限制。应该能无限增加下去，直到内存满了在进行删除，增加操作时性能更好。

两个都是线程不安全的，在iterator时，会发生fail-fast：快速失效。

2. ArrayList と Vector の違い

• ArrayList はスレッド セーフではありません。イテレータを使用するとフェイルファストが発生します
• Vector は Synchronized キーを使用するためスレッド セーフです

#3. フェイルファストとフェイルセーフの違いと状況説明

すべてのコレクションはメソッドの前に追加されます。 java.util は失敗します。 -fast、java.util.concurrent で起こることはフェイルセーフです

• fail-fast 高速な失敗などarrayList と同様 イテレータを使用してトラバースする場合、別のスレッドが追加、削除など、arrayList のストレージ配列に変更を加え、構造上の変更が発生したため、イテレータはすぐに
  java.util を報告します。 .ConcurrentModificationExceptionException (同時変更例外)、これは高速失敗です
• fail-safe 安全な失敗、
  java.util.concurrent の下のクラス, すべて これはスレッドセーフなクラスです。反復プロセス中にスレッドが構造を変更しても、例外は報告されませんが、通常どおりに通過されます。これは安全な失敗です。
• なぜ java.util なのか。コンカレント パッケージのコレクションに構造的な変更があった場合、例外は報告されないのでしょうか? 並行コレクション クラスに要素を追加するときは、
  Arrays.copyOf() を使用してコピーをコピーし、そのコピーに要素を追加します。他のスレッドがコレクションの構造を変更した場合、つまり、また、元のコレクションに影響を与えるのではなく、コピーに対する変更も行われます。イテレータは通常どおりトラバースします。トラバースが完了すると、元の参照はコピーを指すように変更されます。つまり、このパッケージの下のクラスが追加または削除すると、コピーが表示されます。したがって、フェイルファストを防ぐことができます。このメカニズムは誤動作しないため、この現象をフェイルセーフと呼びます。
• vector はスレッドセーフでもあります。なぜフェイルファストなのか? フェイルセーフは、追加と削除に対して異なる基礎メカニズムを実装しているためです。前述したように、コピーが存在しますが、arrayList、linekdList、verctor などの最下層は実際の参照に基づいています。操作、それが例外が発生する理由です。
  

4。今 Vector を使用することが推奨されない理由

Vector でスレッド セーフを実現する方法は、ロックを追加することです。これらのロックは必要ありません。実際の開発では、通常、一連の操作をロックすることでスレッド セーフを実現します。つまり、同期する必要があるリソースをまとめてロックして、スレッド セーフを確保します。
• 複数のスレッドがロックされたメソッドを同時に実行する場合、このメソッドには Vector が存在します。Vector
• は独自の実装でロックされているため、ロックして再度ロックすることと同等であり、追加のオーバーヘッドが発生します。
  
Vector にはフェイルファストの問題もあります。つまり、トラバーサルのセキュリティを保証できません。トラバーサル中に追加のロックが必要になり、追加のオーバーヘッドが発生します。arrayList を直接使用してロックすることをお勧めします。

概要: Vector は、スレッド セーフである必要がない場合にもロックし、追加のオーバーヘッドが発生するため、jdk1.5 以降は廃止されました。スレッド セーフなコレクションを使用するには、対応するクラスを次の場所から取得します。

java.util.concurrent パッケージ。

5. HashMap 分析

1. HashMap の概要

1.1 Java8

がキーと値を通じてエントリ オブジェクトにカプセル化される前の HashMap . 次に、キーの値に基づいてエントリのハッシュ値が計算されます。エントリのハッシュ値と配列の長さを使用して、エントリが配列内のどこに配置されるかを計算します。エントリが保存されるたびに、エントリは最初の位置に配置されます。

HashMap は Map インターフェイスを実装します。これにより、

key を持つ要素を null にすることができ、value を ## に挿入することもできます。 #null; の要素は、このクラスが同期を実装していないことを除けば、残りは Hashtable とほぼ同じです。 TreeMap とは異なり、このコンテナは要素の順序を保証せず、コンテナは変更される可能性があります。 -必要に応じて要素をハッシュします。要素の順序も再シャッフルされるため、異なる時点で同じ HashMap を反復する順序は異なる場合があります。競合の処理方法に応じて、ハッシュ テーブルを実装するには 2 つの方法があります。1 つはオープン アドレッシング方式 (オープン アドレッシング)、もう 1 つは競合リンク リスト方式 (リンク リストによる分離チェーン) です。 Java7 HashMap は競合リンク リスト方式を使用します。

1.2 Java8后的HashMap

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode

2、Java8 HashMap源码分析

2.1 继承结构与层次

public class HashMap<k> extends AbstractMap<k>
    implements Map<k>, Cloneable, Serializable</k></k></k>

2.2 属性

//序列号private static final long serialVersionUID = 362498820763181265L;
//默认的初始容量static final int DEFAULT_INITIAL_CAPACITY = 1 [] table;
//存放具体元素的集transient Set<map.entry>> entrySet;
//存放元素的个数，注意这个不等于数组的长度transient int size;
//每次扩容和更改map结构的计数器transient int modCount;
//临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容int threshold;
//填充因子,计算HashMap的实时装载因子的方法为：size/capacityfinal float loadFactor;</map.entry>

2.3 构造方法

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否则报错
    if (initialCapacity  MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //填充因子不能小于或等于0，不能为非数字
    if (loadFactor >> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}/**
 * 自定义初始容量，加载因子为默认
 */public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);}/**
 * 使用默认的加载因子等字段
 */public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(Map extends K, ? extends V> m) {
    //初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //将m中的所有元素添加至HashMap中
    putMapEntries(m, false);}//将m的所有元素存入该实例final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        //判断table是否已经初始化
        if (table == null) { // pre-size
            //未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft  threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        //将m中的所有元素添加至HashMap中
        for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }}

2.4 核心方法

put()方法

先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则查找是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链表尾部，注意JDK1.7中采用的是头插法，即每次都将冲突的键值对放置在链表头，这样最初的那个键值对最终就会成为链尾，而JDK1.8中使用的是尾插法。此外，若table在该处没有元素，则直接保存。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<k>[] tab; Node<k> p; int n, i;
    //第一次put元素时，table数组为空，先调用resize生成一个指定容量的数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //hash值和n-1的与运算结果为桶的位置，如果该位置空就直接放置一个Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果计算出的bucket不空，即发生哈希冲突，就要进一步判断
    else {
        Node<k> e; K k;
        //判断当前Node的key与要put的key是否相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断当前Node是否是红黑树的节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<k>)p).putTreeVal(this, tab, hash, key, value);
        //以上都不是，说明要new一个Node，加入到链表中
        else {
            for (int binCount = 0; ; ++binCount) {
              //在链表尾部插入新节点，注意jdk1.8是在链表尾部插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果当前链表中的元素大于树化的阈值，进行链表转树的操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //在链表中继续判断是否已经存在完全相同的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //走到这里，说明本次put是更新一个已存在的键值对的value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //在hashMap中，afterNodeAccess方法体为空，交给子类去实现
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果当前size超过临界值，就扩容。注意是先插入节点再扩容
    if (++size > threshold)
        resize();
    //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现
    afterNodeInsertion(evict);
    return null;}</k></k></k></k>

resize() 数组扩容

用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移

final Node<k>[] resize() {
    Node<k>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 对应数组扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 将数组大小扩大一倍
        else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)
            // 将阈值扩大一倍
            newThr = oldThr  0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
        newCap = oldThr;
    else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap [] newTab = (Node<k>[])new Node[newCap];
    table = newTab; // 如果是初始化数组，到这里就结束了，返回 newTab 即可

    if (oldTab != null) {
        // 开始遍历原数组，进行数据迁移。
        for (int j = 0; j  e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果该数组位置上只有单个元素，那就简单了，简单迁移这个元素就可以了
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树，具体我们就不展开了
                else if (e instanceof TreeNode)
                    ((TreeNode<k>)e).split(this, newTab, j, oldCap);
                else { 
                    // 这块是处理链表的情况，
                    // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
                    // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表，代码还是比较简单的
                    Node<k> loHead = null, loTail = null;
                    Node<k> hiHead = null, hiTail = null;
                    Node<k> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        // 第一条链表
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 第二条链表的新的位置是 j + oldCap，这个很好理解
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;}</k></k></k></k></k></k></k>

get()过程

public V get(Object key) {
    Node<k> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<k> getNode(int hash, Object key) {
    Node<k>[] tab; Node<k> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个节点是不是就是需要的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 判断是否是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<k>)first).getTreeNode(hash, key);

            // 链表遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;}</k></k></k></k></k>

2.5 其他方法

HashSet是对HashMap的简单包装，其他还有迭代器等

3、总结

关于数组扩容，从putVal源代码中我们可以知道，当插入一个元素的时候size就加1，若size大于threshold的时候，就会进行扩容。假设我们的capacity大小为32，loadFator为0.75，则threshold为24 = 32 * 0.75，此时，插入了25个元素，并且插入的这25个元素都在同一个桶中，桶中的数据结构为红黑树，则还有31个桶是空的，也会进行扩容处理，其实此时，还有31个桶是空的，好像似乎不需要进行扩容处理，但是是需要扩容处理的，因为此时我们的capacity大小可能不适当。我们前面知道，扩容处理会遍历所有的元素，时间复杂度很高；前面我们还知道，经过一次扩容处理后，元素会更加均匀的分布在各个桶中，会提升访问效率。所以说尽量避免进行扩容处理，也就意味着，遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处。

• HashMap在JDK1.8以前是一个链表散列这样一个数据结构，而在JDK1.8以后是一个数组加链表加红黑树的数据结构
• 通过源码的学习，HashMap是一个能快速通过key获取到value值得一个集合，原因是内部使用的是hash查找值得方法

另外LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的形式将所有**entry**连接起来，这样是为保证元素的迭代顺序跟插入顺序相同

六、Collections工具类

1、概述

此类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在 collection 上操作的多态算法，即“包装器”，包装器返回由指定 collection 支持的新 collection，以及少数其他内容。如果为此类的方法所提供的 collection 或类对象为 null，则这些方法都将抛出NullPointerException

2、排序常用方法

//反转列表中元素的顺序
static void reverse(List> list)
//对List集合元素进行随机排序
static void shuffle(List> list)
//根据元素的自然顺序 对指定列表按升序进行排序
static void sort(List<t> list)
//根据指定比较器产生的顺序对指定列表进行排序
static <t> void sort(List<t> list, Comparator super T> c)
//在指定List的指定位置i,j处交换元素
static void swap(List> list, int i, int j)
//当distance为正数时，将List集合的后distance个元素“整体”移到前面；当distance为负数时，将list集合的前distance个元素“整体”移到后边。该方法不会改变集合的长度
static void rotate(List> list, int distance)</t></t></t>

3、查找、替换操作

//使用二分搜索法搜索指定列表，以获得指定对象在List集合中的索引
//注意：此前必须保证List集合中的元素已经处于有序状态
static <t> int binarySearch(List extends Comparable super T>>list, T key)
//根据元素的自然顺序，返回给定collection 的最大元素
static Object max(Collection coll)
//根据指定比较器产生的顺序，返回给定 collection 的最大元素
static Object max(Collection coll,Comparator comp):
//根据元素的自然顺序，返回给定collection 的最小元素
static Object min(Collection coll):
//根据指定比较器产生的顺序，返回给定 collection 的最小元素
static Object min(Collection coll,Comparator comp):
//使用指定元素替换指定列表中的所有元素
static <t> void fill(List super T> list,T obj)
//返回指定co1lection中等于指定对象的出现次数
static int frequency(collection>c,object o)
//返回指定源列表中第一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回-1
static int indexofsubList(List>source, List>target)
//返回指定源列表中最后一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回-1
static int lastIndexofsubList(List>source,List>target)
//使用一个新值替换List对象的所有旧值o1dval
static <t> boolean replaceA1l(list<t> list,T oldval,T newval)</t></t></t></t>

4、同步控制

Collectons提供了多个synchronizedXxx()方法，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。正如前面介绍的HashSet，TreeSet，arrayList，LinkedList，HashMap，TreeMap都是线程不安全的。Collections提供了多个静态方法可以把他们包装成线程同步的集合。

//返回指定 Collection 支持的同步（线程安全的）collection
static <T> Collection<T> synchronizedCollection(Collection<T> c)
//返回指定列表支持的同步（线程安全的）列表
static <T> List<T> synchronizedList(List<T> list)
//返回由指定映射支持的同步（线程安全的）映射
static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
//返回指定 set 支持的同步（线程安全的）set
static <T> Set<T> synchronizedSet(Set<T> s)

5、Collection设置不可变集合

//返回一个空的、不可变的集合对象，此处的集合既可以是List，也可以是Set，还可以是Map。
emptyXxx()
//返回一个只包含指定对象（只有一个或一个元素）的不可变的集合对象，此处的集合可以是：List，Set，Map。
singletonXxx():
//返回指定集合对象的不可变视图，此处的集合可以是：List，Set，Map
unmodifiableXxx()

推荐学习：《java教程》

メソッド名	説明
#void addFirst(Object o)	リストの先頭に要素を追加します
リストの最後の要素を削除して返します

以上がJavaコレクションフレームワークの詳細な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。