1.哈希表

1.哈希表簡(jiǎn)介

哈希表，又叫散列表华烟，是根據(jù)關(guān)鍵值碼值(key value)來(lái)直接訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)，它可以通過(guò)把key值映射到表當(dāng)中的某個(gè)位置來(lái)喂链，來(lái)快速的查找可以值對(duì)應(yīng)的value衩藤，好像有點(diǎn)抽象赏表，舉個(gè)簡(jiǎn)單的例子：某個(gè)學(xué)校有10000個(gè)學(xué)生逢慌，某個(gè)學(xué)生的學(xué)號(hào)是key=10000(散列地址)攻泼，value=小明忙菠，校長(zhǎng)要查找出小明(假設(shè)小明這個(gè)名字是唯一的)同學(xué)，一個(gè)一個(gè)的查找太費(fèi)事傍睹，他可以通過(guò)key=10000拾稳，直接定位到小明所在的班級(jí)照找到小明，效率提高了許多震鹉。

2.哈希表的創(chuàng)建方式

1.直接定值法：
取關(guān)鍵字key的某個(gè)線(xiàn)性函數(shù)為散列地址，如Hash(key) = key 或 Hash(key) = A*key+B泥技；A,B為常數(shù)
2.除留取余法：
關(guān)鍵值除以比散列表長(zhǎng)度小的素?cái)?shù)簸呈，獲得的值作為散列表的地址值蜕便，即Hash(key)=key%p, p是比散列表長(zhǎng)度小的一個(gè)素?cái)?shù).

3.哈希沖突

盡管有這么多的方法，但是不同的key值任然會(huì)出現(xiàn)映射到同一個(gè)散列地址上的情況族壳，這樣就會(huì)造成哈希沖突仿荆。
1、線(xiàn)性探測(cè)：當(dāng)不同的key值通過(guò)哈希函數(shù)映射到同一散列地址上時(shí)令境，檢測(cè)當(dāng)前地址的下一個(gè)地址是否可以插入展父，如果可以的話(huà)，就存在當(dāng)前位置的下一個(gè)地址吕漂，否則惶凝，繼續(xù)向下一個(gè)地址尋找，地址++混滔。

2坯屿、二次探測(cè)：是針對(duì)線(xiàn)性探測(cè)的一個(gè)改進(jìn)乏德，線(xiàn)性探測(cè)后插入的key值太集中喊括，這樣造成key值通過(guò)散列函數(shù)后還是無(wú)法正確的映射到地址上，太集中也會(huì)造成查找蹦误、刪除時(shí)的效率低下强胰。因此，通過(guò)二次探測(cè)的方法玄窝，取當(dāng)前地址加上i^2，可以取到的新的地址就會(huì)稍微分散開(kāi)俩块。

3.當(dāng)用線(xiàn)性探測(cè)和二次探測(cè)時(shí)，總是在一個(gè)有限的哈希表中存儲(chǔ)數(shù)據(jù)，當(dāng)數(shù)據(jù)特別多時(shí)，效率就比較低。因此采用拉鏈法（桶）的方式來(lái)降低哈希沖突.將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線(xiàn)性鏈表中。

4.還有一種情況是，當(dāng)一個(gè)鏈上鏈的數(shù)據(jù)過(guò)多時(shí)拓萌，我們可以采用紅黑樹(shù)的方式來(lái)降低高度，保持平衡且不至于過(guò)載炕倘。

2.HashMap 簡(jiǎn)介

HashMap 主要用來(lái)存放鍵值對(duì)，它基于哈希表的Map接口實(shí)現(xiàn)涨醋，是常用的Java集合之一宪潮。
JDK1.8之前狡相，hashMap的底層是基于數(shù)組+鏈表的檩淋，數(shù)組是HashMap 的主體蟀悦，鏈表是為了解決哈希沖突而存在的，在JDK1.8之后解決哈希沖突有了新的方法浙炼，當(dāng)鏈表長(zhǎng)度大于閾值(鏈表上的數(shù)據(jù)蜗帜，默認(rèn)是8)時(shí)厅缺，鏈表自動(dòng)轉(zhuǎn)換為紅黑樹(shù)，以減少索引時(shí)間窥妇。

1.底層數(shù)據(jù)結(jié)構(gòu)分析

JDK1.8之前

HashMap底層是采用數(shù)組+鏈表的形式結(jié)合的，也就是鏈表散列纱新，HashMap通過(guò)key值的HashCode,經(jīng)過(guò)擾動(dòng)函數(shù)處理之后得到哈希值(hash值)，然后通過(guò)(n-1)&hash判斷當(dāng)前元素的存儲(chǔ)位置簿废。如果當(dāng)前位置沒(méi)值就直接覆蓋，如果當(dāng)前位置有值，就使用拉鏈法解決扫尖。

擾動(dòng)函數(shù)是指HashMap的hash()函數(shù)，
JDK1.8源代碼如下:

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位異或
      // >>>:無(wú)符號(hào)右移沉颂，忽略符號(hào)位钉蒲，空位都以0補(bǔ)齊
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突蜻牢，則將沖突的值加到鏈表中即可。

jdk1.8之前的內(nèi)部結(jié)構(gòu)

]

JDK1.8之后

相比于之前的版本，jdk1.8在解決哈希沖突時(shí)有了較大的變化恳邀，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)乳附，以減少搜索時(shí)間。

JDK1.8之后的HashMap底層數(shù)據(jù)結(jié)構(gòu)

loadFactor加載因子

loadFactor加載因子是控制數(shù)組存放數(shù)據(jù)的疏密程度，loadFactor越趨近于1祭犯，那么 數(shù)組中存放的數(shù)據(jù)(entry)也就越多沃粗，也就越密，也就是會(huì)讓鏈表的長(zhǎng)度增加涡贱，load Factor越小，也就是趨近于0，

loadFactor太大導(dǎo)致查找元素效率低垄分，太小導(dǎo)致數(shù)組的利用率低，存放的數(shù)據(jù)會(huì)很分散嘿般。loadFactor的默認(rèn)值為0.75f是官方給出的一個(gè)比較好的臨界值。 　

threshold

threshold = capacity * loadFactor涯冠，當(dāng)Size>=threshold的時(shí)候炉奴，那么就要考慮對(duì)數(shù)組的擴(kuò)增了，也就是說(shuō)蛇更，這個(gè)的意思就是 衡量數(shù)組是否需要擴(kuò)增的一個(gè)標(biāo)準(zhǔn)。

3.hashMap源碼分析

1.構(gòu)造函數(shù)

圖片.png

// 默認(rèn)構(gòu)造函數(shù)派任。
    public More ...HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
     }
     
     // 包含另一個(gè)“Map”的構(gòu)造函數(shù)
     public More ...HashMap(Map<? extends K, ? extends V> m) {
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);//下面會(huì)分析到這個(gè)方法
     }
     
     // 指定“容量大小”的構(gòu)造函數(shù)
     public More ...HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }
     
     // 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
     public More ...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.put方法

HashMap只提供了put用于添加元素砸逊，putVal方法只是給put方法調(diào)用的一個(gè)方法，并沒(méi)有提供給用戶(hù)使用掌逛。

對(duì)putVal方法添加元素的分析如下：

①如果定位到的數(shù)組位置沒(méi)有元素 就直接插入师逸。
②如果定位到的數(shù)組位置有元素就和要插入的key比較，如果key相同就直接覆蓋豆混，如果key不相同篓像，就判斷p是否是一個(gè)樹(shù)節(jié)點(diǎn)动知，如果是就調(diào)用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)將元素添加進(jìn)入。如果不是就遍歷鏈表插入员辩。

4.LinkedList

LinkedList是一個(gè)實(shí)現(xiàn)了List接口與Deque接口的雙向鏈表類(lèi)盒粮，LinkedList的層是鏈表，所以可以快速的實(shí)現(xiàn)插入與刪除操作奠滑。另外它實(shí)現(xiàn)了Deque接口丹皱，使得LinkedList類(lèi)也具有隊(duì)列的特性; LinkedLIst不是想線(xiàn)程安全的，如果要讓他變成線(xiàn)程安全的宋税，可以使用Collections的synchronizedList方法Collections.synchronizedList(linkedList);

Collection與Collections的區(qū)別
Collection是java.util下的接口摊崭，是所有集合類(lèi)的頂層父類(lèi)(Map除外)
Collections是java.util下的類(lèi)，他包含各種有關(guān)集合操作 的靜態(tài)方法杰赛。

圖片.png

LinkedList源碼分析

構(gòu)造方法

空構(gòu)造方法：

    public LinkedList() {
    }

用已有的集合創(chuàng)建鏈表的構(gòu)造方法：

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

add方法

add(E e) 方法：將元素添加到鏈表尾部

public boolean add(E e) {
        linkLast(e);//這里就只調(diào)用了這一個(gè)方法
        return true;
    }

   /**
     * 鏈接使e作為最后一個(gè)元素爽室。
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;//新建節(jié)點(diǎn)
        if (l == null)
            first = newNode;
        else
            l.next = newNode;//指向后繼元素也就是指向下一個(gè)元素
        size++;
        modCount++;
    }

add(int index,E e)：在指定位置添加元素

public void add(int index, E element) {
        checkPositionIndex(index); //檢查索引是否處于[0-size]之間

        if (index == size)//添加在鏈表尾部
            linkLast(element);
        else//添加在鏈表中間
            linkBefore(element, node(index));
    }

linkBefore方法需要給定兩個(gè)參數(shù)，一個(gè)插入節(jié)點(diǎn)的值淆攻，一個(gè)指定的node，所以我們又調(diào)用了Node(index)去找到index對(duì)應(yīng)的node

addAll(Collection c )：將集合插入到鏈表尾部

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

addAll(int index, Collection c)： 將集合從指定位置開(kāi)始插入

public boolean addAll(int index, Collection<? extends E> c) {
        //1:檢查index范圍是否在size之內(nèi)
        checkPositionIndex(index);

        //2:toArray()方法把集合的數(shù)據(jù)存到對(duì)象數(shù)組中
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        //3：得到插入位置的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)
        Node<E> pred, succ;
        //如果插入位置為尾部嘿架，前驅(qū)節(jié)點(diǎn)為last瓶珊，后繼節(jié)點(diǎn)為null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //否則，調(diào)用node()方法得到后繼節(jié)點(diǎn)耸彪，再得到前驅(qū)節(jié)點(diǎn)
        else {
            succ = node(index);
            pred = succ.prev;
        }

        // 4：遍歷數(shù)據(jù)將數(shù)據(jù)插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //創(chuàng)建新節(jié)點(diǎn)
            Node<E> newNode = new Node<>(pred, e, null);
            //如果插入位置在鏈表頭部
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        //如果插入位置在尾部伞芹，重置last節(jié)點(diǎn)
        if (succ == null) {
            last = pred;
        }
        //否則，將插入的鏈表與先前鏈表連接起來(lái)
        else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }    

上面可以看出addAll方法通常包括下面四個(gè)步驟：

1. 檢查index范圍是否在size之內(nèi)
2. toArray()方法把集合的數(shù)據(jù)存到對(duì)象數(shù)組中
3. 得到插入位置的前驅(qū)和后繼節(jié)點(diǎn)
4. 遍歷數(shù)據(jù)蝉娜，將數(shù)據(jù)插入到指定位置

addFirst(E e)： 將元素添加到鏈表頭部

 public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//新建節(jié)點(diǎn)唱较，以頭節(jié)點(diǎn)為后繼節(jié)點(diǎn)
        first = newNode;
        //如果鏈表為空，last節(jié)點(diǎn)也指向該節(jié)點(diǎn)
        if (f == null)
            last = newNode;
        //否則召川，將頭節(jié)點(diǎn)的前驅(qū)指針指向新節(jié)點(diǎn)南缓，也就是指向前一個(gè)元素
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

addLast(E e)： 將元素添加到鏈表尾部，與 add(E e) 方法一樣

public void addLast(E e) {
        linkLast(e);
    }

根據(jù)位置取數(shù)據(jù)的方法

get(int index)：：根據(jù)指定索引返回?cái)?shù)據(jù)

public E get(int index) {
        //檢查index范圍是否在size之內(nèi)
        checkElementIndex(index);
        //調(diào)用Node(index)去找到index對(duì)應(yīng)的node然后返回它的值
        return node(index).item;
    }

獲取頭節(jié)點(diǎn)（index=0）數(shù)據(jù)方法:

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
public E element() {
        return getFirst();
    }
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

區(qū)別： getFirst(),element(),peek(),peekFirst() 這四個(gè)獲取頭結(jié)點(diǎn)方法的區(qū)別在于對(duì)鏈表為空時(shí)的處理荧呐，是拋出異常還是返回null汉形，其中getFirst() 和element() 方法將會(huì)在鏈表為空時(shí)，拋出異常

element()方法的內(nèi)部就是使用getFirst()實(shí)現(xiàn)的倍阐。它們會(huì)在鏈表為空時(shí)概疆，拋出NoSuchElementException 獲取尾節(jié)點(diǎn)（index=-1）數(shù)據(jù)方法:

 public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
 public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

兩者區(qū)別： getLast() 方法在鏈表為空時(shí)，會(huì)拋出NoSuchElementException峰搪，而peekLast() 則不會(huì)岔冀，只是會(huì)返回 null。

根據(jù)對(duì)象得到索引的方法

int indexOf(Object o)： 從頭遍歷找

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            //從頭遍歷
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            //從頭遍歷
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

int lastIndexOf(Object o)： 從尾遍歷找

public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            //從尾遍歷
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            //從尾遍歷
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

檢查鏈表是否包含某對(duì)象的方法：

contains(Object o)： 檢查對(duì)象o是否存在于鏈表中

 public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

刪除方法 remove() ,removeFirst(),pop(): 刪除頭節(jié)點(diǎn)

public E pop() {
        return removeFirst();
    }
public E remove() {
        return removeFirst();
    }
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

removeLast(),pollLast(): 刪除尾節(jié)點(diǎn)

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

區(qū)別： removeLast()在鏈表為空時(shí)將拋出NoSuchElementException概耻，而pollLast()方法返回null使套。

remove(Object o): 刪除指定元素

public boolean remove(Object o) {
        //如果刪除對(duì)象為null
        if (o == null) {
            //從頭開(kāi)始遍歷
            for (Node<E> x = first; x != null; x = x.next) {
                //找到元素
                if (x.item == null) {
                   //從鏈表中移除找到的元素
                    unlink(x);
                    return true;
                }
            }
        } else {
            //從頭開(kāi)始遍歷
            for (Node<E> x = first; x != null; x = x.next) {
                //找到元素
                if (o.equals(x.item)) {
                    //從鏈表中移除找到的元素
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

當(dāng)刪除指定對(duì)象時(shí)罐呼，只需調(diào)用remove(Object o)即可，不過(guò)該方法一次只會(huì)刪除一個(gè)匹配的對(duì)象童漩，如果刪除了匹配對(duì)象弄贿，返回true，否則false矫膨。

unlink(Node x) 方法：

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;//得到后繼節(jié)點(diǎn)
        final Node<E> prev = x.prev;//得到前驅(qū)節(jié)點(diǎn)

        //刪除前驅(qū)指針
        if (prev == null) {
            first = next;如果刪除的節(jié)點(diǎn)是頭節(jié)點(diǎn),令頭節(jié)點(diǎn)指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)
        } else {
            prev.next = next;//將前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向后繼節(jié)點(diǎn)
            x.prev = null;
        }

        //刪除后繼指針
        if (next == null) {
            last = prev;//如果刪除的節(jié)點(diǎn)是尾節(jié)點(diǎn),令尾節(jié)點(diǎn)指向該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

remove(int index)：刪除指定位置的元素

public E remove(int index) {
        //檢查index范圍
        checkElementIndex(index);
        //將節(jié)點(diǎn)刪除
        return unlink(node(index));
    }

LinkedList類(lèi)常用方法測(cè)試

package list;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] srgs) {
        //創(chuàng)建存放int類(lèi)型的linkedList
        LinkedList<Integer> linkedList = new LinkedList<>();
        /************************** linkedList的基本操作 ************************/
        linkedList.addFirst(0); // 添加元素到列表開(kāi)頭
        linkedList.add(1); // 在列表結(jié)尾添加元素
        linkedList.add(2, 2); // 在指定位置添加元素
        linkedList.addLast(3); // 添加元素到列表結(jié)尾
        
        System.out.println("LinkedList（直接輸出的）: " + linkedList);

        System.out.println("getFirst()獲得第一個(gè)元素: " + linkedList.getFirst()); // 返回此列表的第一個(gè)元素
        System.out.println("getLast()獲得第最后一個(gè)元素: " + linkedList.getLast()); // 返回此列表的最后一個(gè)元素
        System.out.println("removeFirst()刪除第一個(gè)元素并返回: " + linkedList.removeFirst()); // 移除并返回此列表的第一個(gè)元素
        System.out.println("removeLast()刪除最后一個(gè)元素并返回: " + linkedList.removeLast()); // 移除并返回此列表的最后一個(gè)元素
        System.out.println("After remove:" + linkedList);
        System.out.println("contains()方法判斷列表是否包含1這個(gè)元素:" + linkedList.contains(1)); // 判斷此列表包含指定元素差凹，如果是，則返回true
        System.out.println("該linkedList的大小 : " + linkedList.size()); // 返回此列表的元素個(gè)數(shù)

        /************************** 位置訪(fǎng)問(wèn)操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.set(1, 3); // 將此列表中指定位置的元素替換為指定的元素
        System.out.println("After set(1, 3):" + linkedList);
        System.out.println("get(1)獲得指定位置（這里為1）的元素: " + linkedList.get(1)); // 返回此列表中指定位置處的元素

        /************************** Search操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.add(3);
        System.out.println("indexOf(3): " + linkedList.indexOf(3)); // 返回此列表中首次出現(xiàn)的指定元素的索引
        System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));// 返回此列表中最后出現(xiàn)的指定元素的索引

        /************************** Queue操作 ************************/
        System.out.println("-----------------------------------------");
        System.out.println("peek(): " + linkedList.peek()); // 獲取但不移除此列表的頭
        System.out.println("element(): " + linkedList.element()); // 獲取但不移除此列表的頭
        linkedList.poll(); // 獲取并移除此列表的頭
        System.out.println("After poll():" + linkedList);
        linkedList.remove();
        System.out.println("After remove():" + linkedList); // 獲取并移除此列表的頭
        linkedList.offer(4);
        System.out.println("After offer(4):" + linkedList); // 將指定元素添加到此列表的末尾

        /************************** Deque操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.offerFirst(2); // 在此列表的開(kāi)頭插入指定的元素
        System.out.println("After offerFirst(2):" + linkedList);
        linkedList.offerLast(5); // 在此列表末尾插入指定的元素
        System.out.println("After offerLast(5):" + linkedList);
        System.out.println("peekFirst(): " + linkedList.peekFirst()); // 獲取但不移除此列表的第一個(gè)元素
        System.out.println("peekLast(): " + linkedList.peekLast()); // 獲取但不移除此列表的第一個(gè)元素
        linkedList.pollFirst(); // 獲取并移除此列表的第一個(gè)元素
        System.out.println("After pollFirst():" + linkedList);
        linkedList.pollLast(); // 獲取并移除此列表的最后一個(gè)元素
        System.out.println("After pollLast():" + linkedList);
        linkedList.push(2); // 將元素推入此列表所表示的堆棧（插入到列表的頭）
        System.out.println("After push(2):" + linkedList);
        linkedList.pop(); // 從此列表所表示的堆棧處彈出一個(gè)元素（獲取并移除列表第一個(gè)元素）
        System.out.println("After pop():" + linkedList);
        linkedList.add(3);
        linkedList.removeFirstOccurrence(3); // 從此列表中移除第一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表）
        System.out.println("After removeFirstOccurrence(3):" + linkedList);
        linkedList.removeLastOccurrence(3); // 從此列表中移除最后一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表）
        System.out.println("After removeFirstOccurrence(3):" + linkedList);

        /************************** 遍歷操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.clear();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        // 迭代器遍歷
        long start = System.currentTimeMillis();
        Iterator<Integer> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        long end = System.currentTimeMillis();
        System.out.println("Iterator：" + (end - start) + " ms");

        // 順序遍歷(隨機(jī)遍歷)
        start = System.currentTimeMillis();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("for：" + (end - start) + " ms");

        // 另一種for循環(huán)遍歷
        start = System.currentTimeMillis();
        for (Integer i : linkedList)
            ;
        end = System.currentTimeMillis();
        System.out.println("for2：" + (end - start) + " ms");

        // 通過(guò)pollFirst()或pollLast()來(lái)遍歷LinkedList
        LinkedList<Integer> temp1 = new LinkedList<>();
        temp1.addAll(linkedList);
        start = System.currentTimeMillis();
        while (temp1.size() != 0) {
            temp1.pollFirst();
        }
        end = System.currentTimeMillis();
        System.out.println("pollFirst()或pollLast()：" + (end - start) + " ms");

        // 通過(guò)removeFirst()或removeLast()來(lái)遍歷LinkedList
        LinkedList<Integer> temp2 = new LinkedList<>();
        temp2.addAll(linkedList);
        start = System.currentTimeMillis();
        while (temp2.size() != 0) {
            temp2.removeFirst();
        }
        end = System.currentTimeMillis();
        System.out.println("removeFirst()或removeLast()：" + (end - start) + " ms");
    }
}

5.ArrayList

ArrayList底層是數(shù)組隊(duì)列侧馅，相當(dāng)于動(dòng)態(tài)數(shù)組危尿，與java當(dāng)中的普通數(shù)組相比，他的容量可以動(dòng)態(tài)的增長(zhǎng)馁痴，在添加大量元素前谊娇，應(yīng)用程序可以使用ensureCapacity操作來(lái)增加 ArrayList 實(shí)例的容量。這可以減少遞增式再分配的數(shù)量罗晕。
它繼承于 AbstractList济欢，實(shí)現(xiàn)了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口。
ArrayList實(shí)現(xiàn)了RandomAccess接口小渊，這個(gè)接口在java當(dāng)中專(zhuān)門(mén)用來(lái)被List接口實(shí)現(xiàn)法褥，他的作用是實(shí)現(xiàn)集合的快速訪(fǎng)問(wèn)，
　　ArrayList 實(shí)現(xiàn)了Cloneable 接口酬屉，即覆蓋了函數(shù) clone()半等，能被克隆。
　　ArrayList 實(shí)現(xiàn)java.io.Serializable 接口呐萨，這意味著ArrayList支持序列化杀饵，能通過(guò)序列化去傳輸。
和 Vector 不同谬擦，ArrayList 中的操作不是線(xiàn)程安全的切距！所以，建議在單線(xiàn)程中才使用 ArrayList惨远，而在多線(xiàn)程中可以選擇 Vector 或者 CopyOnWriteArrayList蔚舀。

(一).ArrayList核心源碼

   /**
     * 默認(rèn)初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默認(rèn)構(gòu)造函數(shù)，使用初始容量10構(gòu)造一個(gè)空列表(無(wú)參數(shù)構(gòu)造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 帶初始容量參數(shù)的構(gòu)造函數(shù)锨络。（用戶(hù)自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //創(chuàng)建initialCapacity大小的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0赌躺，拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *構(gòu)造包含指定collection元素的列表，這些元素利用該集合的迭代器按順序返回
    *如果指定的集合為null羡儿，throws NullPointerException礼患。 
    */
     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;
        }
    }

以無(wú)參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時(shí)，實(shí)際上初始化賦值的是一個(gè)空數(shù)組。當(dāng)真正對(duì)數(shù)組進(jìn)行添加元素操作時(shí)缅叠，才真正分配容量悄泥。即向數(shù)組中添加第一個(gè)元素時(shí)，數(shù)組容量擴(kuò)為10肤粱。

1. 先來(lái)看 add 方法

    /**
     * 將指定的元素追加到此列表的末尾弹囚。 
     */
    public boolean add(E e) {
   //添加元素之前，先調(diào)用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值
        elementData[size++] = e;
        return true;
    }

2. 再來(lái)看看 ensureCapacityInternal() 方法

可以看到 add 方法 首先調(diào)用了ensureCapacityInternal(size + 1)

   //得到最小擴(kuò)容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

當(dāng) 要 add 進(jìn)第1個(gè)元素時(shí)领曼，minCapacity為1鸥鹉，在Math.max()方法比較后，minCapacity 為10庶骄。

3. ensureExplicitCapacity() 方法

如果調(diào)用 ensureCapacityInternal() 方法就一定會(huì)進(jìn)過(guò)（執(zhí)行）這個(gè)方法毁渗，下面我們來(lái)研究一下這個(gè)方法的源碼！

  //判斷是否需要擴(kuò)容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //調(diào)用grow方法進(jìn)行擴(kuò)容单刁，調(diào)用此方法代表已經(jīng)開(kāi)始擴(kuò)容了
            grow(minCapacity);
    }

我們來(lái)仔細(xì)分析一下：

* 當(dāng)我們要 add 進(jìn)第1個(gè)元素到 ArrayList 時(shí)灸异，elementData.length 為0 （因?yàn)檫€是一個(gè)空的 list），因?yàn)閳?zhí)行了 ensureCapacityInternal() 方法 羔飞，所以 minCapacity 此時(shí)為10肺樟。此時(shí)，minCapacity - elementData.length > 0 成立逻淌，所以會(huì)進(jìn)入 grow(minCapacity) 方法么伯。

* 當(dāng)add第2個(gè)元素時(shí)，minCapacity 為2恍风，此時(shí)e lementData.length(容量)在添加第一個(gè)元素后擴(kuò)容成 10 了。此時(shí)誓篱，minCapacity - elementData.length > 0 不成立朋贬，所以不會(huì)進(jìn)入 （執(zhí)行）grow(minCapacity) 方法。

* 添加第3窜骄、4···到第10個(gè)元素時(shí)锦募，依然不會(huì)執(zhí)行g(shù)row方法，數(shù)組容量都為10邻遏，直到添加第11個(gè)元素糠亩，minCapacity(為11)比elementData.length（為10）要大。進(jìn)入grow方法進(jìn)行擴(kuò)容准验。

4. grow() 方法

/**
 * 要分配的最大數(shù)組大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * ArrayList擴(kuò)容的核心方法赎线。
 */
private void grow(int minCapacity) {
    // oldCapacity為舊容量，newCapacity為新容量
    int oldCapacity = elementData.length;
    //將oldCapacity 右移一位糊饱，其效果相當(dāng)于oldCapacity /2垂寥，
    //我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算，整句運(yùn)算式的結(jié)果就是將新容量更新為舊容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后檢查新容量是否大于最小需要容量滞项，若還是小于最小需要容量狭归，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
   // 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) `hugeCapacity()` 方法來(lái)比較 minCapacity 和 MAX_ARRAY_SIZE文判，
   //如果minCapacity大于最大容量过椎，則新容量則為`Integer.MAX_VALUE`，否則戏仓，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`疚宇。
    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);
}

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉?lái)的 1.5 倍！ 記清楚了柜去！不是網(wǎng)上很多人說(shuō)的 1.5 倍+1灰嫉！

">>"（移位運(yùn)算符）：>>1 右移一位相當(dāng)于除2，右移n位相當(dāng)于除以 2 的 n 次方嗓奢。這里 oldCapacity 明顯右移了1位所以相當(dāng)于oldCapacity /2讼撒。對(duì)于大數(shù)據(jù)的2進(jìn)制運(yùn)算,位移運(yùn)算符比那些普通運(yùn)算符的運(yùn)算要快很多,因?yàn)槌绦騼H僅移動(dòng)一下而已,不去計(jì)算,這樣提高了效率,節(jié)省了資源 　

我們?cè)賮?lái)通過(guò)例子探究一下grow() 方法 ：

當(dāng)add第1個(gè)元素時(shí)，oldCapacity 為0股耽，經(jīng)比較后第一個(gè)if判斷成立根盒，newCapacity = minCapacity(為10)。但是第二個(gè)if判斷不會(huì)成立物蝙，即newCapacity 不比 MAX_ARRAY_SIZE大炎滞，則不會(huì)進(jìn)入 hugeCapacity 方法。數(shù)組容量為10诬乞，add方法中 return true,size增為1册赛。
當(dāng)add第11個(gè)元素進(jìn)入grow方法時(shí)，newCapacity為15震嫉，比minCapacity（為11）大森瘪，第一個(gè)if判斷不成立。新容量沒(méi)有大于數(shù)組最大size票堵，不會(huì)進(jìn)入hugeCapacity方法扼睬。數(shù)組容量擴(kuò)為15，add方法中return true,size增為11悴势。
以此類(lèi)推······

這里補(bǔ)充一點(diǎn)比較重要窗宇，但是容易被忽視掉的知識(shí)點(diǎn)：

java 中的 length 屬性是針對(duì)數(shù)組說(shuō)的,比如說(shuō)你聲明了一個(gè)數(shù)組,想知道這個(gè)數(shù)組的長(zhǎng)度則用到了 length 這個(gè)屬性.
java 中的 length() 方法是針對(duì)字符串說(shuō)的,如果想看這個(gè)字符串的長(zhǎng)度則用到 length() 這個(gè)方法.
java 中的 size() 方法是針對(duì)泛型集合說(shuō)的,如果想看這個(gè)泛型有多少個(gè)元素,就調(diào)用此方法來(lái)查看!

5. hugeCapacity() 方法。

從上面 grow() 方法源碼我們知道： 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) hugeCapacity() 方法來(lái)比較 minCapacity 和 MAX_ARRAY_SIZE特纤，如果minCapacity大于最大容量军俊，則新容量則為Integer.MAX_VALUE，否則捧存，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8蝇完。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //對(duì)minCapacity和MAX_ARRAY_SIZE進(jìn)行比較
    //若minCapacity大官硝，將Integer.MAX_VALUE作為新數(shù)組的大小
    //若MAX_ARRAY_SIZE大，將MAX_ARRAY_SIZE作為新數(shù)組的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

(二)System.arraycopy() 和 Arrays.copyOf()方法

兩者聯(lián)系和區(qū)別

聯(lián)系：

看兩者源代碼可以發(fā)現(xiàn) copyOf() 內(nèi)部實(shí)際調(diào)用了 System.arraycopy() 方法

區(qū)別：

arraycopy() 需要目標(biāo)數(shù)組短蜕，將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組氢架，而且可以選擇拷貝的起點(diǎn)和長(zhǎng)度以及放入新數(shù)組中的位置 ，copyOf() 是系統(tǒng)自動(dòng)在內(nèi)部新建一個(gè)數(shù)組朋魔，并返回該數(shù)組岖研。Array.copyOf() 用于復(fù)制指定的數(shù)組內(nèi)容以達(dá)到擴(kuò)容的目的，該方法對(duì)不同的基本數(shù)據(jù)類(lèi)型都有對(duì)應(yīng)的重載方法
arraycopy()會(huì)報(bào)數(shù)組越界異常警检，copyof()不會(huì)報(bào)數(shù)組越界異常孙援，因?yàn)槭切陆ㄒ粋€(gè)數(shù)組，copyOf()是系統(tǒng)自動(dòng)在內(nèi)部新建一個(gè)數(shù)組扇雕，并返回該數(shù)組拓售。

arrayCopy( arr1, 2, arr2, 5, 10);意思是將arr1數(shù)組里從索引為2的元素開(kāi)始, 復(fù)制到數(shù)組arr2里的索引為5的位置, 復(fù)制的元素個(gè)數(shù)為10個(gè).

package com.xd.map;

import java.util.LinkedList;

public class Test7 {    

   public static void main(String[] args) {
       
       int [] arr= {1,2,3,4,5};
       int [] arr1= {6,7,8,9};
       /**
        * 將數(shù)組arr從索引0處開(kāi)始賦值到數(shù)組arr1里面的索引0處，賦值的長(zhǎng)度是3個(gè)
        * 注意是替換镶奉，輸出:1,2,3,9
        */
       System.arraycopy(arr, 0, arr1, 0, 3);
       for(int i:arr1) {
           System.out.println(i);
       }
   }
}

Arrays的copyOf()方法傳回的數(shù)組是新的數(shù)組對(duì)象础淤，所以您改變傳回?cái)?shù)組中的元素值，也不會(huì)影響原來(lái)的數(shù)組哨苛，Array.CopyOf(arr,newLength),第一個(gè)參數(shù)是要復(fù)制的數(shù)組鸽凶，第二個(gè)參數(shù)是要?jiǎng)?chuàng)建的數(shù)組的長(zhǎng)度，

package com.xd.map;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
public class Test7 {    
   public static void main(String[] args) {
       
       int [] arr= {1,2,3,4,5};
       int [] arr1= Arrays.copyOf(arr, 10);
       System.out.println(arr1.length);
       for(int i:arr1) {
           //輸出1,2,3,4,5,0,0,0,0,0
           System.out.println(i);
       }
       int [] arr2=Arrays.copyOf(arr, 2);
       for(int i:arr2) {
           //輸出1,2
           System.out.println(i);
       }
   }   
}

（三）ensureCapacity方法

ArrayList 源碼中有一個(gè) ensureCapacity 方法不知道大家注意到?jīng)]有建峭，這個(gè)方法 ArrayList 內(nèi)部沒(méi)有被調(diào)用過(guò)玻侥，所以很顯然是提供給用戶(hù)調(diào)用的，那么這個(gè)方法有什么作用呢亿蒸？

    /**
     *  如有必要凑兰，增加此 ArrayList 實(shí)例的容量，以確保它至少可以容納由minimum capacity參數(shù)指定的元素?cái)?shù)边锁。
     *
     *  @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

最好在 add 大量元素之前用 ensureCapacity 方法姑食，以減少增量從新分配的次數(shù),減少操作的時(shí)間。

package com.xd.map;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
public class Test7 {    

   public static void main(String[] args) {
       
      ArrayList arrayList=new ArrayList<>();
      Long start=System.currentTimeMillis();
      for(int i=0;i<10000000;i++) {
          arrayList.add(i);
      }
      Long end=System.currentTimeMillis();
      //使用動(dòng)態(tài)擴(kuò)容花費(fèi)的時(shí)間5408s
      System.out.println("使用動(dòng)態(tài)擴(kuò)容花費(fèi)的時(shí)間"+(end-start)+"s");
      System.out.println("********************************************************");
      start=System.currentTimeMillis();
      //如果要添加大量的元素最好提前指定容量的大小砚蓬，盡量減少增量重新分配的次數(shù)
      arrayList.ensureCapacity(10000000);
      for(int i=0;i<10000000;i++) {
          arrayList.add(i);
      }
      end=System.currentTimeMillis();
      //使用ensureCapacity花費(fèi)的時(shí)間2122s
      System.out.println("使用ensureCapacity花費(fèi)的時(shí)間"+(end-start)+"s");
   }
}

通過(guò)運(yùn)行結(jié)果矢门，我們可以很明顯的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法盆色，以減少增量從新分配的次數(shù)

(三)toArray()方法

將集合轉(zhuǎn)換為灰蛙，注意通過(guò)toArray()方法調(diào)用了 System.arraycopy(elementData, 0, result, 0, size);有參數(shù)的toArray()方法在內(nèi)部利用反射，根據(jù)參數(shù)數(shù)據(jù)的類(lèi)型隔躲，創(chuàng)造了一個(gè)與參數(shù)數(shù)組一致的摩梧，大小為ArrayList的size()的數(shù)組，雖然返回值任然是Object []的宣旱，但是由于參數(shù)類(lèi)型與要轉(zhuǎn)換的參數(shù)類(lèi)型一致仅父，所以不會(huì)報(bào)異常。

ArrayList的兩個(gè)toArray()方法的源代碼：

public Object[] toArray() {
    Object[] result = new Object[size];
    System.arraycopy(elementData, 0, result, 0, size);
    return result;
}


public Object[] toArray(Object a[]) {
    if (a.length < size)
        a = (Object[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

如果要把一個(gè)List直接轉(zhuǎn)化為Object數(shù)組，則可以直接使用Object[] o = list.toArray();

如果要轉(zhuǎn)化為String數(shù)組笙纤，則有以下兩種方式：

方法一耗溜、String[]  arr = new String[list.size];  list.toArray(arr);//此時(shí)arr就有了list中的值了

方法二、String[] arr = (String[])list.toArray(new String[0]);

注意為什么String[] arr = (String[])list.toArray()會(huì)報(bào)錯(cuò)呢省容？抖拴，這是因?yàn)樵趶?qiáng)制轉(zhuǎn)換的時(shí)候，此處是將多個(gè)對(duì)象同時(shí)轉(zhuǎn)換為了String腥椒，但是在java當(dāng)中只有一個(gè)一個(gè)對(duì)象的轉(zhuǎn)換阿宅，故報(bào)錯(cuò)，可以使用如下的方法一個(gè)一個(gè)的轉(zhuǎn)換

ArrayList list = new ArrayList();
list.add(new Person());
list.add(new Person());
list.add(new Person());
//這里不需要轉(zhuǎn)型笼蛛，也不能使用轉(zhuǎn)型
Object[] ss = list.toArray();
//這里可以進(jìn)行轉(zhuǎn)型洒放，取出原ArrayList里面存放的對(duì)象
for (int i = 0; i < ss.length; i++){
Person person= (Person) ss[i];
System.out.println(person);
}

ArrayList常用方法demo

package com.xd.map;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Test7 {    

   public static void main(String[] args) {
       
      List<Integer> list=new ArrayList<>();
      
      System.out.println("添加元素之前的數(shù)組大小是:"+list.size());
      list.add(1);
      list.add(3);
      list.add(5);
      list.add(7);
      list.add(9);
      System.err.println(list);
      System.out.println("添加元素之后的數(shù)組大小是:"+list.size());
      /********************************遍歷數(shù)組**********************************/
      Iterator<Integer> iterator=list.iterator();
      while(iterator.hasNext()) {
          System.out.println(iterator.next());
      }
      System.out.println("-----------------------------------------------");
      for(Integer it:list) {
          System.out.println(it);
      }
      System.out.println("--------------------------------------------------");
      for(int i=0;i<list.size();i++) {
          System.out.println(list.get(i));
      }
      
      
      System.out.println("***************************集合轉(zhuǎn)換為數(shù)組***********************************");
      
      //將list集合copy一份復(fù)制給it數(shù)組
      Integer [] it=list.toArray(new Integer[0]);
      //方法二
      Integer [] it1=new Integer[list.size()];
      list.toArray(it1);
      
      // 在指定位置添加元素
      list.add(2,2);
      System.out.println(list);
      // 刪除指定位置上的元素
      list.remove(1);
      System.out.println(list);
      // 刪除指定元素
      list.remove((Object)9);
      System.out.println(list);
      // 判斷arrayList是否包含5
      System.out.println("ArrayList contains 5 is: " + list.contains(5));

      // 清空ArrayList
      list.clear();
      // 判斷ArrayList是否為空
      System.out.println("ArrayList is empty: " + list.isEmpty());
   }
}