Java的集合類（collection接口和Map）
一、集合概述
- 集合：集合是java中提供的一種容器，可以用來存儲多個資料。
集合和數組既然都是容器，它們有啥差別呢？
- 數組的長度是固定的。集合的長度是可變的。
- 數組中存儲的是同一類型的元素，可以存儲基本資料類型值。集合存儲的都是對象。而且對象的類型可以不一緻。在開發中一般當對象多的時候，使用集合進行存儲。
Java的集合類是一些非常實用的工具類，主要用于存儲和裝載資料 (包括對象)，是以，Java的集合類也被成為容器。在Java中，所有的集合類都位于java.util包下，這些集合類主要是基于兩個根接口派生而來，它們就是 Collection和 Map。
首先我要說明的是Map不屬于Collection接口。
List、Set和Map差別：
List 和 Set 是存儲單列資料的集合，Map 是存儲鍵和值這樣的雙列資料的集合；List 中存儲的資料是有順序，并
且允許重複；Map 中存儲的資料是沒有順序的，其鍵是不能重複的，它的值是可以有重複的，Set 中存儲的資料是無
序的，且不允許有重複，但元素在集合中的位置由元素的 hashcode 決定，位置是固定的（Set 集合根據 hashcode 來進行資料的存儲，是以位置是固定的，但是位置不是使用者可以控制的，是以對于使用者來說 set 中的元素還是無序的）；
二、Collection接口
Collection集合架構圖如下：
（圖檔摘自：https://www.cnblogs.com/janson071/p/9663569.html）
Collection派生出三個子接口，Set代表不可重複的無序集合、List代表可重複的有序集合、Queue是java提供的隊列實作，通過它們不斷的擴充出很多的集合類。
2.1、Collection 常用功能
Collection是所有單列集合的父接口，是以在Collection中定義了單列集合(List和Set)通用的一些方法，這些方法可用于操作所有的單列集合。方法如下：
-
public boolean add(E e)
-
public void clear()
-
public boolean remove(E e)
-
public boolean contains(E e)
-
public boolean isEmpty()
-
public int size()
-
public Object[] toArray()
-
public Iterator<E> iterator()
還有一些操作整個集合的方法：
boolean containsAll(Collection<?> c)
是否包含指定集合 c 的全部元素
boolean addAll(Collection<? extends E> c)
添加集合 c 中所有的元素到本集合中，如果集合有改變就傳回 true
boolean removeAll(Collection<?> c)
删除本集合中和 c 集合中一緻的元素，如果集合有改變就傳回 true
boolean retainAll(Collection<?> c)
保留本集合中 c 集合中兩者共有的，如果集合有改變就傳回 true
void clear()
删除所有元素
方法示範：
import java.util.ArrayList;
import java.util.Collection;
public class Demo1Collection {
public static void main(String[] args) {
// 建立集合對象
// 使用多态形式
Collection<String> coll = new ArrayList<String>();
// 使用方法
// 添加功能 boolean add(String s)
coll.add("小李廣");
coll.add("掃地僧");
coll.add("石破天");
System.out.println(coll);
// boolean contains(E e) 判斷o是否在集合中存在
System.out.println("判斷 掃地僧 是否在集合中"+coll.contains("掃地僧"));
//boolean remove(E e) 删除在集合中的o元素
System.out.println("删除石破天："+coll.remove("石破天"));
System.out.println("操作之後集合中元素:"+coll);
// size() 集合中有幾個元素
System.out.println("集合中有"+coll.size()+"個元素");
// Object[] toArray()轉換成一個Object數組
Object[] objects = coll.toArray();
// 周遊數組
for (int i = 0; i < objects.length; i++) {
System.out.println(objects[i]);
}
// void clear() 清空集合
coll.clear();
System.out.println("集合中内容為："+coll);
// boolean isEmpty() 判斷是否為空
System.out.println(coll.isEmpty());
}
}
2.2、List接口
2.2.1、概述
List是單列集合的一個重要f分支，習慣性地會将實作了List接口的對象稱為List集合。
2.2.1.1、List集合特點：
- 它是一個元素存取有序的集合，即元素的存入順序和取出順序一緻。
- 它是一個帶有索引的集合，通過索引就可以精确的操作集合中的元素（與數組的索引是一個道理）。
- 集合中可以有重複的元素，通過元素的equals方法，來比較是否為重複的元素。
2.2.1.2、List接口方法
List作為Collection集合的子接口，不但繼承了Collection接口中的全部方法，而且還增加了一些根據元素索引來操作集合的特有方法，如下：
-
public void add(int index, E element)
-
public E get(int index)
-
public E remove(int index)
-
public E set(int index, E element)
public class ListDemo {
public static void main(String[] args) {
// 建立List集合對象
List<String> list = new ArrayList<String>();
// 往 尾部添加 指定元素
list.add("圖圖");
list.add("小美");
list.add("不高興");
System.out.println(list);
// add(int index,String s) 往指定位置添加
list.add(1,"沒頭腦");
System.out.println(list);
// String remove(int index) 删除指定位置元素 傳回被删除元素
// 删除索引位置為2的元素
System.out.println("删除索引位置為2的元素");
System.out.println(list.remove(2));
System.out.println(list);
// String set(int index,String s)
// 在指定位置 進行 元素替代（改）
// 修改指定位置元素
list.set(0, "三毛");
System.out.println(list);
// String get(int index) 擷取指定位置元素
// 跟size() 方法一起用 來 周遊的
for(int i = 0;i<list.size();i++){
System.out.println(list.get(i));
}
//還可以使用增強for
for (String string : list) {
System.out.println(string);
}
}
}
2.2.1.3、List的三個子類的特點
- ArrayList 底層結構是數組,底層查詢快,增删慢。
- LinkedList 底層結構是連結清單型的,增删快,查詢慢。
- voctor 底層結構是數組 線程安全的,增删慢,查詢慢。
2.2.2、ArrayList集合類
ArrayList 底層結構是數組,底層查詢快,增删慢。
java.util.ArrayList
集合資料存儲的結構是數組結構。元素增删慢，查找快，由于日常開發中使用最多的功能為查詢資料、周遊資料，是以
ArrayList
是最常用的集合。
ArrayList是List接口的實作類，一種大小可變數組，随着元素的增多，容量會自動擴充，預設初始容量值是10，也可以自己指定初始容量
（1）采用的資料結構：數組
（線性表：數組、連結清單、隊列、棧
非線性表：二叉樹、堆、圖等）
（2）ArrayList特點：
- ArrayList底層使用了Object的數組作為容器去存儲資料
- ArrayList 提供了使用索引的随意通路資料
- ArrayList 是線程非安全的，效率較高，查詢速度高
（3）ArrayList優點：
查詢速度快
ArrayList缺點：
新增和删除元素比較慢
（4）查詢速度快的原因：
ArrayList底層是數組實作的，根據下标查詢，不需要比較，查詢方式為，首位址+（元素長度＊下标），基于這個位置讀取相應的位元組數，是以非常快；
（5）新增和删除慢的原因：
增删會帶來元素的移動，增加資料會向後移動，删除資料會向前移動，是以影響效率
（6）适用場景：
如果應用程式對資料有較多的随機通路使用ArrayList較好
（7）左父右子
List a=new ArrayList()和 ArrayList a =new ArrayList()的差別？
List list = new ArrayList();這句建立了一個 ArrayList 的對象後把上溯到了 List。此時它是一個 List 對象了，有些
ArrayList 有但是 List 沒有的屬性和方法，它就不能再用了。而 ArrayList list=new ArrayList();建立一對象則保留了
ArrayList 的所有屬性。 是以需要用到 ArrayList 獨有的方法的時候不能用前者。執行個體代碼如下：
List list = new ArrayList();
ArrayList arrayList = new ArrayList();
list.trimToSize(); //錯誤，沒有該方法。
arrayList.trimToSize(); //ArrayList 裡有該方法。
（8）數組擴容
這是對ArrayList效率影響比較大的一個因素。
每當執行Add、AddRange、Insert、InsertRange等添加元素的方法，都會檢查内部數組的容量是否不夠了，如果是，它就會以目前容量的兩倍來重新建構一個數組，将舊元素Copy到新數組中，然後丢棄舊數組，在這個臨界點的擴容操作，應該來說是比較影響效率的。
例1：比如，一個可能有200個元素的資料動态添加到一個以預設16個元素大小建立的ArrayList中，将會經過：
162222 = 256
四次的擴容才會滿足最終的要求，那麼如果一開始就以：
ArrayList List = new ArrayList( 210 );
的方式建立ArrayList，不僅會減少4次數組建立和Copy的操作，還會減少記憶體使用。
例2：預計有30個元素而建立了一個ArrayList：
ArrayList List = new ArrayList(30);
在執行過程中，加入了31個元素，那麼數組會擴充到60個元素的大小，而這時候不會有新的元素再增加進來，而且有沒有調用TrimSize方法，那麼就有1次擴容的操作，并且浪費了29個元素大小的空間。如果這時候，用：
ArrayList List = new ArrayList(40);
那麼一切都解決了。
是以說，正确的預估可能的元素，并且在适當的時候調用TrimSize方法是提高ArrayList使用效率的重要途徑。
（9）為什麼說ArryList是線性不安全的
我們首先看看這類所有的部分屬性字段:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 清單元素集合數組
* 如果建立ArrayList對象時沒有指定大小，那麼會将EMPTY_ELEMENTDATA指派給elementData，
* 并在第一次添加元素時，将清單容量設定為DEFAULT_CAPACITY
*/
transient Object[] elementData;
/**
* 清單大小，elementData中存儲的元素個數
*/
private int size;
}
通過這兩個字段我們可以看出，ArrayList的實作主要就是用了一個Object的數組，用來儲存所有的元素，以及一個size變量用來儲存目前數組中已經添加了多少元素。
接着我們看下最重要的add操作時的源代碼：
public boolean add(E e) {
/**
* 添加一個元素時，做了如下兩步操作
* 1.判斷清單的capacity容量是否足夠，是否需要擴容
* 2.真正将元素放在清單的元素數組裡面
*/
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal()這個方法的詳細代碼我們可以暫時不看，它的作用就是判斷如果将目前的新元素加到清單後面，清單的elementData數組的大小是否滿足，如果size + 1的這個需求長度大于了elementData這個數組的長度，那麼就要對這個數組進行擴容。
由此看到add元素時，實際做了兩個大的步驟：
- 判斷elementData數組容量是否滿足需求
- 在elementData對應位置上設定值
這樣也就出現了第一個導緻線程不安全的隐患，在多個線程進行add操作時可能會導緻elementData數組越界。具體邏輯如下：
- 清單大小為9，即size=9
- 線程A開始進入add方法，這時它擷取到size的值為9，調用ensureCapacityInternal方法進行容量判斷。
- 線程B此時也進入add方法，它擷取到size的值也為9，也開始調用ensureCapacityInternal方法。
- 線程A發現需求大小為10，而elementData的大小就為10，可以容納。于是它不再擴容，傳回。
- 線程B也發現需求大小為10，也可以容納，傳回。
- 線程A開始進行設定值操作， elementData[size++] = e 操作。此時size變為10。
- 線程B也開始進行設定值操作，它嘗試設定elementData[10] = e，而elementData沒有進行過擴容，它的下标最大為9。于是此時會報出一個數組越界的異常ArrayIndexOutOfBoundsException.
另外第二步 elementData[size++] = e 設定值的操作同樣會導緻線程不安全。從這兒可以看出，這步操作也不是一個原子操作，它由如下兩步操作構成：
- elementData[size] = e;
- size = size + 1;
在單線程執行這兩條代碼時沒有任何問題，但是當多線程環境下執行時，可能就會發生一個線程的值覆寫另一個線程添加的值，具體邏輯如下：
- 清單大小為0，即size=0
- 線程A開始添加一個元素，值為A。此時它執行第一條操作，将A放在了elementData下标為0的位置上。
- 接着線程B剛好也要開始添加一個值為B的元素，且走到了第一步操作。此時線程B擷取到size的值依然為0，于是它将B也放在了elementData下标為0的位置上。
- 線程A開始将size的值增加為1
- 線程B開始将size的值增加為2
這樣線程AB執行完畢後，理想中情況為size為2，elementData下标0的位置為A，下标1的位置為B。而實際情況變成了size為2，elementData下标為0的位置變成了B，下标1的位置上什麼都沒有。并且後續除非使用set方法修改此位置的值，否則将一直為null，因為size為2，添加元素時會從下标為2的位置上開始。
2.2.3、LinkedList集合類
LinkedList 底層結構是連結清單型的,增删快,查詢慢。
java.util.LinkedList
集合資料存儲的結構是連結清單結構。友善元素添加、删除的集合。
實際開發中對一個集合元素的添加與删除經常涉及到首尾操作，而LinkedList提供了大量首尾操作的方法。這些方法我們作為了解即可：
-
public void addFirst(E e)
-
public void addLast(E e)
-
public E getFirst()
-
public E getLast()
-
public E removeFirst()
-
public E removeLast()
-
public E pop()
-
public void push(E e)
-
public boolean isEmpty()
LinkedList是List的子類，List中的方法LinkedList都是可以使用，這裡就不做詳細介紹，我們隻需要了解LinkedList的特有方法即可。在開發時，LinkedList集合也可以作為堆棧，隊列的結構使用。（了解即可）
方法示範：
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
//添加元素
link.addFirst("abc1");
link.addFirst("abc2");
link.addFirst("abc3");
System.out.println(link);
// 擷取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
// 删除元素
System.out.println(link.removeFirst());
System.out.println(link.removeLast());
while (!link.isEmpty()) { //判斷集合是否為空
System.out.println(link.pop()); //彈出集合中的棧頂元素
}
System.out.println(link);
}
}
其他1、ArrayList 和 Linkedlist 差別：
ArrayList 和 Vector 使用了數組的實作，可以認為 ArrayList 或者 Vector 封裝了對内部數組的操作，比如向數組
中添加，删除，插入新的元素或者資料的擴充和重定向。
LinkedList 使用了循環雙向連結清單資料結構。與基于數組的 ArrayList 相比，這是兩種截然不同的實作技術，這也決
定了它們将适用于完全不同的工作場景。
LinkedList 連結清單由一系清單項連接配接而成。一個表項總是包含 3 個部分：元素内容，前驅表和後驅表，如圖所示：
在下圖展示了一個包含 3 個元素的 LinkedList 的各個表項間的連接配接關系。在 JDK 的實作中，無論 LikedList 是否
為空，連結清單内部都有一個 header 表項，它既表示連結清單的開始，也表示連結清單的結尾。表項 header 的後驅表項便是連結清單
中第一個元素，表項 header 的前驅表項便是連結清單中最後一個元素。
其他2、要對集合更新操作時，ArrayList 和 LinkedList 哪個更适合
ArrayList 和 LinkedList 在性能上各有優缺點，都有各自所适用的地方，總的說來可以描述如下：
1．對 ArrayList 和 LinkedList 而言，在清單末尾增加一個元素所花的開銷都是固定的。對 ArrayList 而言，主要是在内部數組中增加一項，指向所添加的元素，偶 爾可能會導緻對數組重新進行配置設定；而對 LinkedList 而言，這個開銷是統一的，配置設定一個内部 Entry 對象。
2．在 ArrayList 的中間插入或删除一個元素意味着這個清單中剩餘的元素都會被移動；而在 LinkedList 的中間插入或删除一個元素的開銷是固定的。
3．LinkedList 不支援高效的随機元素通路。
4．ArrayList 的空間浪費主要展現在在 list 清單的結尾預留一定的容量空間，而 LinkedList 的空間花費則展現在它的每一個元素都需要消耗相當的空間
可以這樣說：當操作是在一列資料的後面添加資料而不是在前面或中間,并且需要随機地通路其中的元素時,使用ArrayList 會提供比較好的性能；當你的操作是在一列資料的前面或中間添加或删除資料,并且按照順序通路其中的元 素時,就應該使用 LinkedList 了。
2.2.4、Vector
voctor 底層結構是數組 線程安全的,增删慢,查詢慢。
Vector非常類似ArrayList，但是Vector是同步的，效率相對比較低
Vector實作了Serializable接口，支援序列化，實作了Cloneable接口，能被克隆，實作了RandomAccess接口，支援快速随機通路。
Vector的底層結構也是數組，但是它們對數組的擴容方式不同
當Vector或ArrayList中的元素超過它的初始大小時,Vector會将它的容量翻倍,而ArrayList隻增加50%的大小，這樣ArrayList就有利于節約記憶體空間。即Vector增長原來的一倍，ArrayList增加原來的0.5倍。
Stack棧繼承于Vector，棧的存儲特點是後進先出，它基于動态數組實作的一個線程安全的棧，是以棧是線程安全的
java.util.vector提供了向量類(vector)以實作類似動态數組的功能。在Java語言中沒有指針的概念，但如果正确靈活地使用指針又确實可以大大提高程式的品質。比如在c,c++中所謂的“動态數組”一般都由指針來實作。為了彌補這個缺點，Java提供了豐富的類庫來友善程式設計者使用，vector類便是其中之一。事實上，靈活使用數組也可以完成向量類的功能，但向量類中提供大量的方法大大友善了使用者的使用。
建立了一個向量類的對象後，可以往其中随意插入不同類的對象，即不需顧及類型也不需預先標明向量的容量，并可以友善地進行查找。對于預先不知或者不願預先定義數組大小，并且需要頻繁地進行查找，插入，删除工作的情況。可以考慮使用向量類。
Vector與ArrayList的差別：
- Vector是線程安全的, ArrayList不是線程安全的, 這是最主要的
- Vector類中的方法很多有synchronized進行修飾，這樣就導緻了Vector效率低，不能與ArrayList相比。
- 兩者都是采用線性連續空間存儲元素，當空間不足時，兩者的擴容方式不同。ArrayList不可以設定擴充的容量, 預設1.5倍; Vector可以設定, 預設2倍
- ArrayList無參構造函數中初始量為0; Vector的無參構造函數初始容量為10
向量類提供了三種構造方法：
public vector()
public vector(int initialcapacity,int capacityIncrement)
public vector(int initialcapacity)
使用第一種方法系統會自動對向量進行管理，若使用後兩種方法。則系統将根據參數，initialcapacity設定向量對象的容量（即向量對象可存儲資料的大小），當真正存放的資料個數超過容量時。系統會擴充向量對象存儲容量。
參數capacityincrement給定了每次擴充的擴充值。當capacityincrement為0的時候，則沒次擴充一倍，利用這個功能可以優化存儲。
在Vector類中提供了各種方法友善使用者的使用：
很多方法都加入了synchronized同步語句，來保證線程安全。
插入功能：
（1）public final synchronized void adddElement(Object obj)
将obj插入向量的尾部。obj可以是任何類型的對象。對同一個向量對象，亦可以在其中插入不同類的對象。但插入的應是對象而不是數值，是以插入數值時要注意将數組轉換成相應的對象。
例如：要插入整數1時，不要直接調用v1.addElement(1),正确的方法為： Vector v1 = new Vector();
Integer integer1 = new Integer(1); v1.addElement(integer1);
(2)public final synchronized void setElementAt(Object obj,int index)
将index處的對象設定成obj，原來的對象将被覆寫。
(3)public final synchronized void insertElementAt(Object obj,int
index) 在index指定的位置插入obj，原來對象以及此後的對象依次往後順延。
删除功能：
(1)public final synchronized void removeElement(Object obj)
從向量中删除obj,若有多個存在，則從向量頭開始試，删除找到的第一個與obj相同的向量成員。 (2)public final
synchronized void removeAllElement(); 删除向量所有的對象 (3)public fianl
synchronized void removeElementAt(int index) 删除index所指的地方的對象
查詢搜尋功能：
(1)public final int indexOf(Object obj)
從向量頭開始搜尋obj,傳回所遇到的第一個obj對應的下标，若不存在此obj,傳回-1.
(2)public final synchronized int indexOf(Object obj,int index)
從index所表示的下标處開始搜尋obj.
(3)public final int lastindexOf(Object obj) 從向量尾部開始逆向搜尋obj.
(4)public final synchornized int lastIndex(Object obj,int index)
從index所表示的下标處由尾至頭逆向搜尋obj.
(5)public final synchornized firstElement() 擷取向量對象中的首個obj
(6)public final synchornized Object lastElement() 擷取向量對象的最後一個obj
2.3、Set接口
2.3.1、概述
存儲的資料是無序的，且不允許有重複，但元素在集合中的位置由元素的 hashcode 決定，位置是固定的（Set 集合根據 hashcode 來進行資料的存儲，是以位置是固定的，但是位置不是使用者可以控制的，是以對于使用者來說 set 中的元素還是無序的）；
它與
Collection
接口中的方法基本一緻，并沒有對
Collection
接口進行功能上的擴充，隻是比
Collection
接口更加嚴格了。與
List
接口不同的是，
Set
接口中元素無序，并且都會以某種規則保證存入的元素不出現重複。
HashSet
是根據對象的哈希值來确定元素在集合中的存儲位置，是以具有良好的存取和查找性能。保證元素唯一性（== 或 eqauls）的方式依賴于：
hashCode
與
equals
方法。
Set集合取出元素的方式可以采用：疊代器、增強for。
Set 接口有兩個實作類（HashSet：底層是由 HashMap 實作，不允許集合中有重複的值，使用該方式時需要重寫 equals()和 hashCode()方法；LinkedHashSet：繼承于 HashSet，同時又基于 LinkedHashMap 來進行實作，底層使用的是 LinkedHashMap）。
2.3.2、List和Set的差別
List , Set 都是繼承自 Collection 接口
List 特點：元素有放入順序，元素可重複 ，
Set 特點：元素無放入順序，元素不可重複，重複元素會覆寫掉，（元素雖然無放入順序，但是元素在set中的位置是由該元素HashCode 決定的，其位置其實是固定的，加入Set 的 Object 必須定義 equals ()方法 ，另外list 支援for循環，也就是通過下标來周遊，也可以用疊代器，但是set隻能用疊代，因為他無序，無法用下标來取得想 要的值。） Set和List對比 Set：檢索元素效率低下，删除和插入效率高，插入和删除不會引起元素位置改變。 List：和數組類似，List可以動态增長，查找元素效率高，插入删除元素效率低，因為會引起其他元素位置改變
補充：關于疊代器
Java集合架構的集合類，我們有時候稱之為容器。容器的種類有很多種，比如ArrayList、LinkedList、HashSet…，每種容器都有自己的特點，ArrayList底層維護的是一個數組；LinkedList是連結清單結構的；HashSet依賴的是哈希表，每種容器都有自己特有的資料結構。
因為容器的内部結構不同，很多時候可能不知道該怎樣去周遊一個容器中的元素。是以為了使對容器内元素的操作更為簡單，Java引入了疊代器模式！
把通路邏輯從不同類型的集合類中抽取出來，進而避免向外部暴露集合的内部結構。
對于數組：
//for循環
int array[] = new int[3];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
對于ArrayList：
//for循環
List<String> list = new ArrayList<String>();
for(int i = 0 ; i < list.size() ; i++){
String string = list.get(i);
}
對于這兩種方式，我們總是都知道它的内部結構，通路代碼和集合本身是緊密耦合的，無法将通路邏輯從集合類和用戶端代碼中分離出來。不同的集合會對應不同的周遊方法，用戶端代碼無法複用。在實際應用中如何将上面兩個集合整合是相當麻煩的。是以才有Iterator，它總是用同一種邏輯來周遊集合。使得用戶端自身不需要來維護集合的内部結構，所有的内部狀态都由Iterator來維護。用戶端不用直接和集合進行打交道，而是控制Iterator向它發送向前向後的指令，就可以周遊集合。
對于Set：
package sun.rain.amazing.traversal;
import java.util.*;
public class TraversalSet {
public static void main(String args[]){
List<String> list = new ArrayList<>(
Arrays.asList("tom","cat","Jane","jerry"));
Set<String> set = new HashSet<>();
set.addAll(list);
//方法1 集合類的通用周遊方式, 從很早的版本就有, 用疊代器疊代
Iterator it1 = set.iterator();
while(it1.hasNext()){
System.out.println(it1.next());
}
//方法2 集合類的通用周遊方式, 從很早的版本就有, 用疊代器疊代
for(Iterator it2 = set.iterator();it2.hasNext();){
System.out.println(it2.next());
}
//方法3 增強型for循環周遊
for(String value: set){
System.out.println(value);
}
}
}
2.3.3、HashSet類
HashSet資料結構：哈希表（數組+連結清單）
什麼是哈希表呢？
哈希表底層使用的也是數組機制，數組中也存放對象，而這些對象往數組中存放時的位置比較特殊，當需要把這些對象給數組中存放時，那麼會根據這些對象的特有資料結合相應的算法，計算出這個對象在數組中的位置，然後把這個對象存放在數組中。而這樣的數組就稱為哈希數組，即就是哈希表。
在JDK1.8之前，哈希表底層采用數組+連結清單實作，即使用連結清單處理沖突，同一hash值的連結清單都存儲在一個連結清單裡。但是當位于一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。而JDK1.8中，哈希表存儲采用數組+連結清單+紅黑樹實作，當連結清單長度超過門檻值（8）時，将連結清單轉換為紅黑樹，這樣大大減少了查找時間。
簡單的來說，哈希表是由數組+連結清單+紅黑樹（JDK1.8增加了紅黑樹部分）實作的，如下圖所示。
看到這張圖就有人要問了，這個是怎麼存儲的呢？
為了友善大家的了解我們結合一個存儲流程圖來說明一下：
即哈希表存放的是哈希值，HashSet存取元素的順序并不是按照存入時的順序（和List顯然不同），而是按照哈希值來存取的。元素的哈希值通過元素的hashcode方法來擷取。擷取hashcode之後，接下來就有三種情況：1、如果哈希值不一樣，直接插入。2、hashcode一樣，就進一步用equals方法比較其中的值，如果為false，則在同樣的哈希值下順延，進行連結清單插入（如果連結清單長度大于門檻值，就轉化為紅黑樹）（可以認為哈希值相同的元素放在一個哈希桶中）。3、equals方法也是true，則判斷為同一個元素，不插入。
總而言之，JDK1.8引入紅黑樹大程度優化了HashMap的性能，那麼對于我們來講保證HashSet集合元素的唯一，其實就是根據對象的hashCode和equals方法來決定的。如果我們往集合中存放自定義的對象，那麼保證其唯一，就必須複寫hashCode和equals方法建立屬于目前對象的比較方式。
給HashSet中存放自定義類型元素時，需要重寫對象中的hashCode和equals方法，建立自己的比較方式，才能保證HashSet集合中的對象唯一
建立自定義Student類
public class Student {
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
public class HashSetDemo2 {
public static void main(String[] args) {
//建立集合對象 該集合中存儲 Student類型對象
HashSet<Student> stuSet = new HashSet<Student>();
//存儲
Student stu = new Student("于謙", 43);
stuSet.add(stu);
stuSet.add(new Student("郭德綱", 44));
stuSet.add(new Student("于謙", 43));
stuSet.add(new Student("郭麒麟", 23));
stuSet.add(stu);
for (Student stu2 : stuSet) {
System.out.println(stu2);
}
}
}
執行結果：
Student [name=郭德綱, age=44]
Student [name=于謙, age=43]
Student [name=郭麒麟, age=23]
2.3.4、LinkedHashSet類
我們知道HashSet保證元素唯一，可是元素存放進去是沒有順序的，那麼我們要保證有序，怎麼辦呢？
在HashSet下面有一個子類
java.util.LinkedHashSet
，它是連結清單和哈希表組合的一個資料存儲結構。
示範代碼如下:
public class LinkedHashSetDemo {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<String>();
set.add("bbb");
set.add("aaa");
set.add("abc");
set.add("bbc");
Iterator<String> it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
結果：
bbb
aaa
abc
bbc
特點：
- 具有set集合不重複的特點，同時具有可預測的疊代順序，也就是我們插入的順序。
- 是一個非線程安全的集合。如果有多個線程同時通路目前linkedhashset集合容器，并且有一個線程對目前容器中的元素做了修改，那麼必須要在外部實作同步保證資料的冥等性。
- LinkedHashSet集合同樣是根據元素的hashCode值來決定元素的存儲位置，但是它同時使用連結清單維護元素的次序。這樣使得元素看起來像是以插入順序儲存的，也就是說，當周遊該集合時候，LinkedHashSet将會以元素的添加順序通路集合的元素。
- LinkedHashSet在疊代通路Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。
2.3.5、TreeSet類
底層是用二叉樹來實作
TreeSet是SortedSet接口的唯一實作類，TreeSet可以確定集合元素處于排序狀态。
TreeSet并不是根據元素的插入順序進行排序,而是根據元素實際值來進行排序.(可以確定元素唯一并且元素排序) TreeSet采用紅黑樹的資料結構對元素進行排序.
TreeSet支援兩種排序方式，自然排序 和定制排序，其中自然排序為預設的排序方式(Integer類型元素自然升序)。向TreeSet中加入的應該是同一個類的對象。
TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法傳回false，或者通過CompareTo方法比較沒有傳回0
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法來比較元素之間大小關系，然後将元素按照升序排列。
Java提供了一個Comparable接口，該接口裡定義了一個compareTo(Object obj)方法，該方法傳回一個整數值，實作了該接口的對象就可以比較大小。
obj1.compareTo(obj2)方法如果傳回0，則說明被比較的兩個對象相等，如果傳回一個正數，則表明obj1大于obj2，如果是 負數，則表明obj1小于obj2。
如果我們将兩個對象的equals方法總是傳回true，則這兩個對象的compareTo方法傳回應該傳回0
定制排序
自然排序是根據集合元素的大小，以升序排列，如果要定制排序，應該使用Comparator接口，實作 int compare(T o1,T o2)方法
2.4、Queue
本節轉自：https://www.cnblogs.com/lemon-flm/p/7877898.html
Queue： 基本上，一個隊列就是一個先入先出（FIFO）的資料結構
Queue接口與List、Set同一級别，都是繼承了Collection接口。LinkedList實作了Queue接 口。Queue接口窄化了對LinkedList的方法的通路權限（即在方法中的參數類型如果是Queue時，就完全隻能通路Queue接口所定義的方法 了，而不能直接通路 LinkedList的非Queue的方法），以使得隻有恰當的方法才可以使用。BlockingQueue 繼承了Queue接口。
隊列是一種資料結構．它有兩個基本操作：在隊列尾部加人一個元素，和從隊列頭部移除一個元素就是說，隊列以一種先進先出的方式管理資料，如果你試圖向一個 已經滿了的阻塞隊列中添加一個元素或者是從一個空的阻塞隊列中移除一個元索，将導緻線程阻塞．在多線程進行合作時，阻塞隊列是很有用的工具。工作者線程可 以定期地把中間結果存到阻塞隊列中而其他工作者線線程把中間結果取出并在将來修改它們。隊列會自動平衡負載。如果第一個線程集運作得比第二個慢，則第二個 線程集在等待結果時就會阻塞。如果第一個線程集運作得快，那麼它将等待第二個線程集趕上來。
Queue的實作
1、沒有實作的阻塞接口的LinkedList： 實作了java.util.Queue接口和java.util.AbstractQueue接口
内置的不阻塞隊列： PriorityQueue 和 ConcurrentLinkedQueue
PriorityQueue 和 ConcurrentLinkedQueue 類在 Collection Framework 中加入兩個具體集合實作。
PriorityQueue 類實質上維護了一個有序清單。加入到 Queue 中的元素根據它們的天然排序（通過其 java.util.Comparable 實作）或者根據傳遞給構造函數的 java.util.Comparator 實作來定位。
ConcurrentLinkedQueue 是基于連結節點的、線程安全的隊列。并發通路不需要同步。因為它在隊列的尾部添加元素并從頭部删除它們，是以隻要不需要知道隊列的大 小， ConcurrentLinkedQueue 對公共集合的共享通路就可以工作得很好。收集關于隊列大小的資訊會很慢，需要周遊隊列。
2)實作阻塞接口的：
java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質上就是一種帶有一點扭曲的 FIFO 資料結構。不是立即從隊列中添加或者删除元素，線程執行操作阻塞，直到有空間或者元素可用。
五個隊列所提供的各有不同：
* ArrayBlockingQueue ：一個由數組支援的有界隊列。
* LinkedBlockingQueue ：一個由連結節點支援的可選有界隊列。
* PriorityBlockingQueue ：一個由優先級堆支援的無界優先級隊列。
* DelayQueue ：一個由優先級堆支援的、基于時間的排程隊列。
* SynchronousQueue ：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制。
下表顯示了jdk1.5中的阻塞隊列的操作：
add 增加一個元索 如果隊列已滿，則抛出一個IIIegaISlabEepeplian異常
remove 移除并傳回隊列頭部的元素 如果隊列為空，則抛出一個NoSuchElementException異常
element 傳回隊列頭部的元素 如果隊列為空，則抛出一個NoSuchElementException異常
offer 添加一個元素并傳回true 如果隊列已滿，則傳回false
poll 移除并返問隊列頭部的元素 如果隊列為空，則傳回null
peek 傳回隊列頭部的元素 如果隊列為空，則傳回null
put 添加一個元素 如果隊列滿，則阻塞
take 移除并傳回隊列頭部的元素 如果隊列為空，則阻塞
remove、element、offer 、poll、peek 其實是屬于Queue接口。
阻塞隊列的操作可以根據它們的響應方式分為以下三類：aad、removee和element操作在你試圖為一個已滿的隊列增加元素或從空隊列取得元素時 抛出異常。當然，在多線程程式中，隊列在任何時間都可能變成滿的或空的，是以你可能想使用offer、poll、peek方法。這些方法在無法完成任務時 隻是給出一個出錯示而不會抛出異常。
注意：poll和peek方法出錯進傳回null。是以，向隊列中插入null值是不合法的
最後，我們有阻塞操作put和take。put方法在隊列滿時阻塞，take方法在隊列空時阻塞。
ArrayBlockingQueue在構造時需要指定容量， 并可以選擇是否需要公平性，如果公平參數被設定true，等待時間最長的線程會優先得到處理（其實就是通過将ReentrantLock設定為true來 達到這種公平性的：即等待時間最長的線程會先操作）。通常，公平性會使你在性能上付出代價，隻有在的确非常需要的時候再使用它。它是基于數組的阻塞循環隊 列，此隊列按 FIFO（先進先出）原則對元素進行排序。
PriorityBlockingQueue是一個帶優先級的 隊列，而不是先進先出隊列。元素按優先級順序被移除，該隊列也沒有上限（看了一下源碼，PriorityBlockingQueue是對 PriorityQueue的再次包裝，是基于堆資料結構的，而PriorityQueue是沒有容量限制的，與ArrayList一樣，是以在優先阻塞 隊列上put時是不會受阻的。雖然此隊列邏輯上是無界的，但是由于資源被耗盡，是以試圖執行添加操作可能會導緻 OutOfMemoryError），但是如果隊列為空，那麼取元素的操作take就會阻塞，是以它的檢索操作take是受阻的。另外，往入該隊列中的元 素要具有比較能力。
DelayQueue（基于PriorityQueue來實作的）是一個存放Delayed 元素的無界阻塞隊列，隻有在延遲期滿時才能從中提取元素。該隊列的頭部是延遲期滿後儲存時間最長的 Delayed 元素。如果延遲都還沒有期滿，則隊列沒有頭部，并且poll将傳回null。當一個元素的 getDelay(TimeUnit.NANOSECONDS) 方法傳回一個小于或等于零的值時，則出現期滿，poll就以移除這個元素了。此隊列不允許使用 null 元素。
三、Map
3.1、關于Map
3.1.1、概述
Map 中存儲的資料是沒有順序的，其鍵是不能重複的，它的值是可以有重複的
現實生活中，我們常會看到這樣的一種集合：IP位址與主機名，身份證号與個人，系統使用者名與系統使用者對象等，這種一一對應的關系，就叫做映射。Java提供了專門的集合類用來存放這種對象關系的對象，即
java.util.Map
接口。
我們通過檢視
Map
接口描述，發現
Map
接口下的集合與
Collection
接口下的集合，它們存儲資料的形式不同，如下圖。
-
Collection
-
Map
-
Collection
Map
- 需要注意的是，
Map
3.1.2、常用子類
HashMap
存儲資料采用的哈希表結構，元素的存取順序不能保證一緻。由于要保證鍵的唯一、不重複，需要重寫鍵的hashCode()方法、equals()方法。它是最常用的Map,它根據鍵的HashCode 值存儲資料,根據鍵可以直接擷取它的值，具有很快的通路速度。HashMap最多隻允許一條記錄的鍵為Null(多條會覆寫);允許多條記錄的值為 Null。非同步的。
LinkedHashMap
HashMap下有個子類LinkedHashMap，存儲資料采用的哈希表結構+連結清單結構。通過連結清單結構可以保證元素的存取順序一緻；通過哈希表結構可以保證的鍵的唯一、不重複，需要重寫鍵的hashCode()方法、equals()方法。儲存了記錄的插入順序，在用Iterator周遊LinkedHashMap時，先得到的記錄肯定是先插入的.在周遊的時候會比HashMap慢。key和value均允許為空，非同步的。
TreeMap
能夠把它儲存的記錄根據鍵(key)排序,預設是按升序排序，也可以指定排序的比較器，當用Iterator 周遊TreeMap時，得到的記錄是排過序的。TreeMap不允許key的值為null。非同步的。
Hashtable
與 HashMap類似,不同的是:key和value的值均不允許為null;它支援線程的同步，即任一時刻隻有一個線程能寫Hashtable,是以也導緻了Hashtale在寫入時會比較慢。
3.1.3、常用方法
Map接口中定義了很多方法，常用的如下：
-
public V put(K key, V value)
-
public V remove(Object key)
-
public V get(Object key)
-
boolean containsKey(Object key)
-
public Set<K> keySet()
-
public Set<Map.Entry<K,V>> entrySet()
Map接口的方法示範
public class MapDemo {
public static void main(String[] args) {
//建立 map對象
HashMap<String, String> map = new HashMap<String, String>();
//添加元素到集合
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("鄧超", "孫俪");
System.out.println(map);
//String remove(String key)
System.out.println(map.remove("鄧超"));
System.out.println(map);
// 想要檢視 黃曉明的媳婦 是誰
System.out.println(map.get("黃曉明"));
System.out.println(map.get("鄧超"));
}
}
tips:
使用put方法時，若指定的鍵(key)在集合中沒有，則沒有這個鍵對應的值，傳回null，并把指定的鍵值添加到集合中；
若指定的鍵(key)在集合中存在，則傳回值為集合中鍵對應的值（該值為替換前的值），并把指定鍵所對應的值，替換成指定的新值。
3.1.4、Map周遊
3.1.4.1、初始化資料
Map<String, String> map = ``new` `HashMap<String, String>();
map.put(``"key1"``, ``"value1"``);
map.put(``"key2"``, ``"value2"``);
3.1.4.2、增強for循環周遊
（1）使用keySet()周遊
for (String key : map.keySet()) {
System.out.println(key + " ：" + map.get(key));
}
也叫周遊鍵找值方式：即通過元素中的鍵，擷取鍵所對應的值
分析步驟：
- 擷取Map中所有的鍵，由于鍵是唯一的，是以傳回一個Set集合存儲所有的鍵。方法提示:
keyset()
- 周遊鍵的Set集合，得到每一個鍵。
- 根據鍵，擷取鍵所對應的值。方法提示:
get(K key)
代碼示範：
public class MapDemo01 {
public static void main(String[] args) {
//建立Map集合對象
HashMap<String, String> map = new HashMap<String,String>();
//添加元素到集合
map.put("胡歌", "霍建華");
map.put("郭德綱", "于謙");
map.put("薛之謙", "大張偉");
//擷取所有的鍵 擷取鍵集
Set<String> keys = map.keySet();
// 周遊鍵集 得到 每一個鍵
for (String key : keys) {
//key 就是鍵
//擷取對應值
String value = map.get(key);
System.out.println(key+"的CP是："+value);
}
}
}
周遊圖解：
（2）使用entrySet()周遊
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + " ：" + entry.getValue());
}
1）Entry鍵值對對象
我們已經知道，
Map
中存放的是兩種對象，一種稱為key(鍵)，一種稱為value(值)，它們在
Map
中是一一對應關系，這一對對象又稱做
Map
中的一個
Entry(項)
。
Entry
将鍵值對的對應關系封裝成了對象。即鍵值對對象，這樣我們在周遊
Map
集合時，就可以從每一個鍵值對（
Entry
）對象中擷取對應的鍵與對應的值。
既然Entry表示了一對鍵和值，那麼也同樣提供了擷取對應鍵和對應值得方法：
-
public K getKey()
-
public V getValue()
在Map集合中也提供了擷取所有Entry對象的方法：
-
public Set<Map.Entry<K,V>> entrySet()
2）周遊鍵值對方式
鍵值對方式：即通過集合中每個鍵值對(Entry)對象，擷取鍵值對(Entry)對象中的鍵與值。
操作步驟與圖解：
- 擷取Map集合中，所有的鍵值對(Entry)對象，以Set集合形式傳回。方法提示:
entrySet()
- 周遊包含鍵值對(Entry)對象的Set集合，得到每一個鍵值對(Entry)對象。
- 通過鍵值對(Entry)對象，擷取Entry對象中的鍵與值。 方法提示:
getkey() getValue()
public class MapDemo02 {
public static void main(String[] args) {
// 建立Map集合對象
HashMap<String, String> map = new HashMap<String,String>();
// 添加元素到集合
map.put("胡歌", "霍建華");
map.put("郭德綱", "于謙");
map.put("薛之謙", "大張偉");
// 擷取 所有的 entry對象 entrySet
Set<Entry<String,String>> entrySet = map.entrySet();
// 周遊得到每一個entry對象
for (Entry<String, String> entry : entrySet) {
// 解析
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key+"的CP是:"+value);
}
}
}
周遊圖解：
tips：Map集合不能直接使用疊代器或者foreach進行周遊。但是轉成Set之後就可以使用了。
3.1.4.3、疊代器周遊
使用keySet()周遊
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
String key = iterator.next();
System.out.println(key + " ：" + map.get(key));
}
使用entrySet()周遊
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
System.out.println(entry.getKey() + " ：" + entry.getValue());
}
3.1.4.4、HashMap周遊方式對比：
- 增強for循環使用友善，但性能較差，不适合處理超大量級的資料。
- 疊代器的周遊速度要比增強for循環快很多，是增強for循環的2倍左右。
- 使用entrySet周遊的速度要比keySet快很多，是keySet的1.5倍左右。
3.2、HashMap
3.2.1、HashMap的資料結構
數組+單連結清單（數組中的每個元素都是單連結清單的頭節點）
使用連結清單的原因是解決哈希沖突的（即不同的key映射到了數組的同一位置處，就将其放入單連結清單中）
哈希沖突
如果兩個不同的元素，通過哈希函數得出的實際存儲位址相同怎麼辦？也就是說，當我們對某個元素進行哈希運算，得到一個存儲位址，然後要進行插入的時候，發現已經被其他元素占用了，其實這就是所謂的哈希沖突，也叫哈希碰撞。前面我們提到過，哈希函數的設計至關重要，好的哈希函數會盡可能地保證 計算簡單和散列位址分布均勻,但是，我們需要清楚的是，數組是一塊連續的固定長度的記憶體空間，再好的哈希函數也不能保證得到的存儲位址絕對不發生沖突。那麼哈希沖突如何解決呢？哈希沖突的解決方案有多種:開放定址法（發生沖突，繼續尋找下一塊未被占用的存儲位址），再散列函數法，鍊位址法，而HashMap即是采用了鍊位址法，也就是數組+連結清單的方式。
HashMap 繼承于AbstractMap，實作了Map、Cloneable、java.io.Serializable接口。
HashMap 的實作不是同步的，這意味着它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。
HashMap中的key-value都是存儲在Entry數組中的。
Entry 實際上就是一個單向連結清單。這也是為什麼我們說HashMap是通過拉鍊法解決哈希沖突的。
Entry 實作了Map.Entry 接口，即實作getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數。這些都是基本的讀取/修改key、value值的函數。
簡單來說，HashMap由數組+連結清單組成的，數組是HashMap的主體，連結清單則是主要為了解決哈希沖突而存在的，如果定位到的數組位置不含連結清單（目前entry的next指向null）,那麼查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含連結清單，對于添加操作，其時間複雜度為O(n)，首先周遊連結清單，存在即覆寫，否則新增；對于查找操作來講，仍需周遊連結清單，然後通過key對象的equals方法逐一比對查找。是以，性能考慮，HashMap中的連結清單出現越少，性能才會越好。
在Java8中，如果連結清單中的元素個數超過了8，則會将連結清單轉化為紅黑樹
3.2.2、HashMap的構造函數
// 預設構造函數。
HashMap()
// 指定“容量大小”的構造函數
HashMap(int capacity)
// 指定“容量大小”和“加載因子”的構造函數
HashMap(int capacity, float loadFactor)
// 包含“子Map”的構造函數
HashMap(Map<? extends K, ? extends V> map)
3.2.3、主要方法
clear()：清空HashMap
containsKey() ：判斷HashMap是否包含key。
containsValue() 的作用是判斷HashMap是否包含“值為value”的元素。
entrySet()的作用是傳回“HashMap中所有Entry的集合”，它是一個集合
get() 的作用是擷取key對應的value
put() 的作用是對外提供接口，讓HashMap對象可以通過put()将“key-value”添加到HashMap中。
putAll() 的作用是将"m"的全部元素都添加到HashMap中
remove() 的作用是删除“鍵為key”元素
3.2.4、線程安全問題
不是線程安全的；
如果有兩個線程A和B，都進行插入資料，剛好這兩條不同的資料經過哈希計算後得到的哈希碼是一樣的，且該位 置還沒有其他的資料。是以這兩個線程都會進入我在上面标記為1的代碼中。假設一種情況，線程A通過if判斷，該 位置沒有哈希沖突，進入了if語句，還沒有進行資料插入，這時候 CPU 就把資源讓給了線程B，線程A停在了if語句 裡面，線程B判斷該位置沒有哈希沖突（線程A的資料還沒插入），也進入了if語句，線程B執行完後，輪到線程A執 行，現線上程A直接在該位置插入而不用再判斷。這時候，你會發現線程A把線程B插入的資料給覆寫了。發生了線 程不安全情況。本來在 HashMap 中，發生哈希沖突是可以用連結清單法或者紅黑樹來解決的，但是在多線程中，可能 就直接給覆寫了。
上面所說的是一個圖來解釋可能更加直覺。如下面所示，兩個線程在同一個位置添加資料，後面添加的資料就覆寫 住了前面添加的。
如果上述插入是插入到連結清單上，如兩個線程都在周遊到最後一個節點，都要在最後添加一個資料，那麼後面添加數 據的線程就會把前面添加的資料給覆寫住。則
3.2.5、HashMap 的擴容過程
當向容器添加元素的時候，會判斷目前容器的元素個數，如果大于等于門檻值—即目前數組的長度乘以加載因子的值的時候，就要自動擴容啦。HashMap的數組長度一定是2的次幂
擴容( resize )就是重新計算容量，向 HashMap 對象裡不停的添加元素，而 HashMap 對象内部的數組無法裝載更 多的元素時，對象就需要擴大數組的長度，以便能裝入更多的元素。當然 Java 裡的數組是無法自動擴容的，方法 是使用一個新的數組代替已有的容量小的數組，就像我們用一個小桶裝水，如果想裝更多的水，就得換大水桶。
HashMap hashMap=new HashMap(cap);
cap =3， hashMap 的容量為4；
cap =4， hashMap 的容量為4；
cap =5， hashMap 的容量為8；
cap =9， hashMap 的容量為16；
如果 cap 是2的n次方，則容量為 cap ，否則為大于 cap 的第一個2的n次方的數。
3.2.6、HashMap1.7和1.8的差別
在 JDK1.7 及之前的版本中， HashMap 又叫散列連結清單：基于一個數組以及多個連結清單的實作，hash值沖突的時候， 就将對應節點以連結清單的形式存儲。
JDK1.8 中，當同一個hash值（ Table 上元素）的連結清單節點數不小于8時，将不再以單連結清單的形式存儲了，會被 調整成一顆紅黑樹。這就是 JDK7 與 JDK8 中 HashMap 實作的最大差別。
其下基于 JDK1.7.0_80 與 JDK1.8.0_66 做的分析
JDK1.7中
使用一個 Entry 數組來存儲資料，用key的 hashcode 取模來決定key會被放到數組裡的位置，如果 hashcode 相 同，或者 hashcode 取模後的結果相同（ hash collision ），那麼這些 key 會被定位到 Entry 數組的同一個 格子裡，這些 key 會形成一個連結清單。
在 hashcode 特别差的情況下，比方說所有key的 hashcode 都相同，這個連結清單可能會很長，那麼 put/get 操作 都可能需要周遊這個連結清單，也就是說時間複雜度在最差情況下會退化到 O(n)
JDK1.8中
使用一個 Node 數組來存儲資料，但這個 Node 可能是連結清單結構，也可能是紅黑樹結構
如果插入的 key 的 hashcode 相同，那麼這些key也會被定位到 Node 數組的同一個格子裡。
如果同一個格子裡的key不超過8個，使用連結清單結構存儲。
如果超過了8個，那麼會調用 treeifyBin 函數，将連結清單轉換為紅黑樹。
那麼即使 hashcode 完全相同，由于紅黑樹的特點，查找某個特定元素，也隻需要O(log n)的開銷
也就是說put/get的操作的時間複雜度最差隻有 O(log n)
聽起來挺不錯，但是真正想要利用 JDK1.8 的好處，有一個限制：
key的對象，必須正确的實作了 Compare 接口
如果沒有實作 Compare 接口，或者實作得不正确（比方說所有 Compare 方法都傳回0）
那 JDK1.8 的 HashMap 其實還是慢于 JDK1.7 的
3.3、HashTable
HashTable和HashMap功能類似，都是用來儲存鍵值對，但兩者之間又有差別
差別：
1.HashTable中不允許儲存null的，而HashMap可以儲存空的key和value
2…HashTable是同步的，是以它是線程安全的
HashMap線程不安全
3.Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類。但二者都實作了Map接口
使用舉例：
package ThreeWeek;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class HashTableTest {
public static void main(String args[]){
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
//[1]添加元素
table.put("zhangsan", 22);
table.put("lisi", 33);
table.put("wangwu", 44);
//[2]toString()方式列印
System.out.println(table.toString());
//[3]Iterator周遊方式1--鍵值對周遊entrySet()
Iterator<Entry<String, Integer>> iter = table.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>)iter.next();
String key = entry.getKey();
int value = entry.getValue();
System.out.println("entrySet:"+key+" "+value);
}
System.out.println("====================================");
//[4]Iterator周遊方式2--key鍵的周遊
Iterator<String> iterator = table.keySet().iterator();
while(iterator.hasNext()){
String key = (String)iterator.next();
int value = table.get(key);
System.out.println("keySet:"+key+" "+value);
}
System.out.println("====================================");
//[5]通過Enumeration來周遊Hashtable
Enumeration<String> enu = table.keys();
while(enu.hasMoreElements()) {
System.out.println("Enumeration:"+table.keys()+" "+enu.nextElement());
}
}
}
{zhangsan=22, lisi=33, wangwu=44}
entrySet:zhangsan 22
entrySet:lisi 33
entrySet:wangwu 44
====================================
keySet:zhangsan 22
keySet:lisi 33
keySet:wangwu 44
====================================
Enumeration:[email protected] zhangsan
Enumeration:[email protected] lisi
Enumeration:[email protected] wangwu
Hashtable 是遺留類，很多映射的常用功能與HashMap 類似，不同的是它承自Dictionary 類，并且是線程安全的，任一時間隻有一個線程能寫Hashtable，并發性不如ConcurrentHashMap，因為ConcurrentHashMap 引入了分段鎖。Hashtable 不建議在新代碼中使用，不需要線程安全的場合可以用HashMap 替換，需要線程安全的場合可以用ConcurrentHashMap 替換。
3.4、LinkedHashMap
多數情況下，隻要不涉及線程安全問題，Map基本都可以使用HashMap，不過HashMap有一個問題，就是疊代HashMap的順序并不是HashMap放置的順序，也就是無序。HashMap的這一缺點往往會帶來困擾，因為有些場景，我們期待一個有序的Map。
這個時候，LinkedHashMap就閃亮登場了，它雖然增加了時間和空間上的開銷，但是通過維護一個運作于所有條目的雙向連結清單，LinkedHashMap保證了元素疊代的順序。該疊代順序可以是插入順序或者是通路順序。
| 關 注 點 | 結 論 |
|---|---|
| LinkedHashMap是否允許空 | Key和Value都允許空 |
| LinkedHashMap是否允許重複資料 | Key重複會覆寫、Value允許重複 |
| LinkedHashMap是否有序 | 有序 |
| LinkedHashMap是否線程安全 | 非線程安全 |
關于LinkedHashMap：
1、LinkedHashMap可以認為是HashMap+LinkedList，即它既使用HashMap操作資料結構，又使用LinkedList維護插入元素的先後順序。
2、LinkedHashMap的基本實作思想就是----多态。可以說，了解多态，再去了解LinkedHashMap原理會事半功倍；反之也是，對于LinkedHashMap原理的學習，也可以促進和加深對于多态的了解。
3.5、TreeMap
TreeMap 是一個有序的key-value集合，它是通過紅黑樹實作的。
TreeMap 繼承于AbstractMap，是以它是一個Map，即一個key-value集合。
TreeMap 實作了NavigableMap接口，意味着它支援一系列的導航方法。比如傳回有序的key集合。
TreeMap 實作了Cloneable接口，意味着它能被克隆。
TreeMap 實作了java.io.Serializable接口，意味着它支援序列化。
TreeMap基于紅黑樹（Red-Black tree）實作。該映射根據其鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的時間複雜度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法傳回的疊代器是fail-fastl的。
與Map關系：
從圖中可以看出：
(01) TreeMap實作繼承于AbstractMap，并且實作了NavigableMap接口。
(02) TreeMap的本質是R-B Tree(紅黑樹)，它包含幾個重要的成員變量： root, size, comparator。
root 是紅黑數的根節點。它是Entry類型，Entry是紅黑數的節點，它包含了紅黑數的6個基本組成成分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節點)、color(顔色)。Entry節點根據key進行排序，Entry節點包含的内容為value。
紅黑數排序時，根據Entry中的key進行排序；Entry中的key比較大小是根據比較器comparator來進行判斷的。
size是紅黑數中節點的個數。
3.6、差別比較
3.6.1、HashMap和HashSet差別 Collection集合類和Map接口各實作類詳解一、集合概述二、Collection接口三、Map四、Collections五、常考點
3.6.2、HashMap 和 HashTable 差別?
（1）基類不同：HashTable基于Dictionary類，而HashMap是基于AbstractMap。Dictionary是什麼？它是任何可将鍵映射到相應值的類的抽象父類，而AbstractMap是基于Map接口的骨幹實作，它以最大限度地減少實作此接口所需的工作。
（2）null不同：HashMap可以允許存在一個為null的key和任意個為null的value，但是HashTable中的key和value都不允許為null。
（3）線程安全：HashMap時單線程安全的，Hashtable是多線程安全的。由于非線程安全,HashMap 的效率要較 HashTable 的效率高一些.
（4）周遊不同：HashMap僅支援Iterator的周遊方式，Hashtable支援Iterator和Enumeration兩種周遊方式。
（5）實作同步：HashTable 是 sychronize,多個線程通路時不需要自己為它的方法實作同步,而 HashMap 在被多個線程通路的時
候需要自己為它的方法實作同步;
3.6.3、Linkedhashmap 與 hashmap 的差別
- LinkedHashMap 是 HashMap 的子類
-
LinkedHashMap 中的 Entry 增加了兩個指針 before 和 after，它們分别用于維護
雙向連結清單。
-
在 put 操作上，雖然 LinkedHashMap 完全繼承了 HashMap 的 put 操作，但是在細
節上還是做了一定的調整，比如，在 LinkedHashMap 中向哈希表中插入新 Entry 的同時，還會通過 Entry 的 addBefore 方法将其鍊入到雙向連結清單中。
- 在擴容操作上，雖然 LinkedHashMap 完全繼承了 HashMap 的 resize 操作，但是 鑒于性能和 LinkedHashMap 自身特點的考量，LinkedHashMap 對其中的重哈希過 程(transfer 方法)進行了重寫
- 在讀取操作上，LinkedHashMap 中重寫了 HashMap 中的 get 方法，通過 HashMap 中的 getEntry 方法擷取 Entry 對象。在此基礎上，進一步擷取指定鍵對應的值。
四、Collections
4.1 常用功能
-
java.utils.Collections
-
public static <T> boolean addAll(Collection<T> c, T... elements)
-
public static void shuffle(List<?> list) 打亂順序
-
public static <T> void sort(List<T> list)
-
public static <T> void sort(List<T> list，Comparator<? super T> )
代碼示範：
public class CollectionsDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
//原來寫法
//list.add(12);
//list.add(14);
//list.add(15);
//list.add(1000);
//采用工具類 完成 往集合中添加元素
Collections.addAll(list, 5, 222, 1，2);
System.out.println(list);
//排序方法
Collections.sort(list);
System.out.println(list);
}
}
結果：
[5, 222, 1, 2]
[1, 2, 5, 222]
代碼示範之後 ，發現我們的集合按照順序進行了排列，可是這樣的順序是采用預設的順序，如果想要指定順序那該怎麼辦呢？
我們發現還有個方法沒有講，
public static <T> void sort(List<T> list，Comparator<? super T> )
:将集合中元素按照指定規則排序。接下來講解一下指定規則的排列。
4.2 Comparator比較器
我們還是先研究這個方法
public static <T> void sort(List<T> list)
:将集合中元素按照預設規則排序。
不過這次存儲的是字元串類型。
public class CollectionsDemo2 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法
Collections.sort(list);
System.out.println(list);
}
}
結果：
[aba, cba, nba, sba]
我們使用的是預設的規則完成字元串的排序，那麼預設規則是怎麼定義出來的呢？
說到排序了，簡單的說就是兩個對象之間比較大小，那麼在JAVA中提供了兩種比較實作的方式，一種是比較死闆的采用
java.lang.Comparable
接口去實作，一種是靈活的當我需要做排序的時候在去選擇的
java.util.Comparator
接口完成。
那麼我們采用的
public static <T> void sort(List<T> list)
這個方法完成的排序，實際上要求了被排序的類型需要實作Comparable接口完成比較的功能，在String類型上如下：
String類實作了這個接口，并完成了比較規則的定義，但是這樣就把這種規則寫死了，那比如我想要字元串按照第一個字元降序排列，那麼這樣就要修改String的源代碼，這是不可能的了，那麼這個時候我們可以使用
public static <T> void sort(List<T> list，Comparator<? super T> )
方法靈活的完成，這個裡面就涉及到了Comparator這個接口，位于位于java.util包下，排序是comparator能實作的功能之一,該接口代表一個比較器，比較器具有可比性！顧名思義就是做排序的，通俗地講需要比較兩個對象誰排在前誰排在後，那麼比較的方法就是：
-
public int compare(String o1, String o2)
兩個對象比較的結果有三種：大于，等于，小于。
如果要按照升序排序，
則o1 小于o2，傳回（負數），相等傳回0，01大于02傳回（正數）
如果要按照降序排序
則o1 小于o2，傳回（正數），相等傳回0，01大于02傳回（負數）
操作如下:
public class CollectionsDemo3 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法 按照第一個單詞的降序
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.charAt(0) - o1.charAt(0);
}
});
System.out.println(list);
}
}
結果如下：
[sba, nba, cba, aba]
4.3 簡述Comparable和Comparator兩個接口的差別。
Comparable：強行對實作它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的compareTo方法被稱為它的自然比較方法。隻能在類中實作compareTo()一次，不能經常修改類的代碼實作自己想要的排序。實作此接口的對象清單（和數組）可以通過Collections.sort（和Arrays.sort）進行自動排序，對象可以用作有序映射中的鍵或有序集合中的元素，無需指定比較器。
Comparator強行對某個對象進行整體排序。可以将Comparator 傳遞給sort方法（如Collections.sort或 Arrays.sort），進而允許在排序順序上實作精确控制。還可以使用Comparator來控制某些資料結構（如有序set或有序映射）的順序，或者為那些沒有自然順序的對象collection提供排序。
4.4 練習
建立一個學生類，存儲到ArrayList集合中完成指定排序操作。
Student 初始類
public class Student{
private String name;
private int age;
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
測試類：
public class Demo {
public static void main(String[] args) {
// 建立四個學生對象 存儲到集合中
ArrayList<Student> list = new ArrayList<Student>();
list.add(new Student("rose",18));
list.add(new Student("jack",16));
list.add(new Student("abc",16));
list.add(new Student("ace",17));
list.add(new Student("mark",16));
/*
讓學生 按照年齡排序 升序
*/
// Collections.sort(list);//要求 該list中元素類型 必須實作比較器Comparable接口
for (Student student : list) {
System.out.println(student);
}
}
}
發現，當我們調用Collections.sort()方法的時候 程式報錯了。
原因：如果想要集合中的元素完成排序，那麼必須要實作比較器Comparable接口。
于是我們就完成了Student類的一個實作，如下：
public class Student implements Comparable<Student>{
....
@Override
public int compareTo(Student o) {
return this.age-o.age;//升序
}
}
再次測試，代碼就OK 了效果如下：
Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', age=16}
Student{name='ace', age=17}
Student{name='rose', age=18}
4.5 擴充
如果在使用的時候，想要獨立的定義規則去使用 可以采用Collections.sort(List list,Comparetor c)方式，自己定義規則：
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();//以學生的年齡降序
}
});
效果：
Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', age=16}
如果想要規則更多一些，可以參考下面代碼：
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// 年齡降序
int result = o2.getAge()-o1.getAge();//年齡降序
if(result==0){//第一個規則判斷完了 下一個規則 姓名的首字母 升序
result = o1.getName().charAt(0)-o2.getName().charAt(0);
}
return result;
}
});
效果如下：
Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='abc', age=16}
Student{name='jack', age=16}
Student{name='mark', age=16}
五、常考點
1、Collection
（1）List
- 存儲單列資料
- 有序、允許重複
- 帶有索引，可以通過索引精确操作元素
1）ArrayList
- 有序、允許重複
- 底層結構是Object數組，查詢快，增删慢，getter和setter方法快；
- 線程不安全；
- 當容量不夠時，ArrayList是目前容量x1.5+1
- 無參構造中初始量為0
2）LinkedList
- 有序，允許重複
- 底層結構是雙向循環連結清單型，增删快，查詢慢，add和remove速度快
- 線程不安全
3）Vector
- 有序、允許重複
- 底層結構是數組，增删慢、查詢慢
- 線程安全，效率低
- 當容量不夠時，預設*2擴充為兩倍
- 無參構造函數初始容量為10（ArrayList初始量為0）
（2）Set
- 存儲單列資料
- 無序、不允許重複（List是有序且允許重複）
- Set周遊隻能通過疊代器，因為他是無序的，不能用下标來擷取想要的值（List還可以用for循環來周遊）
1）HashSet
- 無序、不允許重複
- 底層結構是哈希表（數組+連結清單 ），JDK1.8增加了紅黑樹部分，當連結清單長度超過門檻值（8）時，将連結清單變為紅黑樹
- 内部是HashMap
- 存取速度快
2）TreeSet
- 無序、不允許重複
- 底層采用二叉樹實作
- 排序存儲，不是根據插入順序，而是根據元素實際值來進行排序（是以說是無序的）
- 内部是TreeMap的SortSet
3）LinkedHashSet
- 不允許重複，具有可預測的疊代順序，也就是我們插入的順序
- 根據元素的HashCode值來決定元素的存儲位置，但是它同時使用連結清單維護元素的次序，這樣使得元素看起來像是以插入順序儲存到，也就是說，當周遊該集合的時候會以元素添加的順序通路集合的元素
- 采用哈希表存儲，并用雙向連結清單記錄插入順序
- 内部是LinkedHashMap
- LinkedHashSet在疊代通路Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。
（3）Queue
在兩端出入的List，是以也可以用數組或連結清單來實作
2、Map
- 存儲雙列資料
- 資料沒有順序
- 鍵不能重複，其值可以重複
（1）HashMap
- 鍵不可重複，值可重複
- 底層哈希表
- 線程不安全
- 允許key值為null（最多一條為null，多條會覆寫），value也可以為null
- 由于要保證鍵的唯一、不重複，需要重寫鍵的hashcode()方法、equals()方法
（2）HashTable
- 鍵不可重複，值可重複
- 底層哈希表
- 線程安全，是以寫入較慢
- key和value都不允許為null
（3）TreeMap
- 鍵不可重複，值可重複
- 底層二叉樹
- 記錄根據鍵排序，預設升序排序
（4）LinkedHashMap
多數情況下，隻要不涉及線程安全問題，Map基本都可以使用HashMap，不過HashMap有一個問題，就是疊代HashMap的順序并不是HashMap放置的順序，也就是無序。HashMap的這一缺點往往會帶來困擾，因為有些場景，我們期待一個有序的Map。
這個時候，LinkedHashMap就閃亮登場了，它雖然增加了時間和空間上的開銷，但是通過維護一個運作于所有條目的雙向連結清單，LinkedHashMap保證了元素疊代的順序。該疊代順序可以是插入順序或者是通路順序。
- 鍵不可重複，值可重複
- key和value都允許為null
- 有序，疊代順序可以是插入順序或者是通路順序
- 非線程安全
- 可以看成是HashMap+LinkedList，既可以使用HashMap操作資料結果，又可以使用LinkedList維護元素的小先後順序
（5）TreeMap
- 有序
- 底層是紅黑樹
- 非線性安全
3、其他
（1）線程安全的類
- vector：就比arraylist多了個同步化機制（線程安全），因為效率較低，現在已經不太建議使用。
- statck：堆棧類，先進後出
- hashtable：就比hashmap多了個線程安全
- enumeration：枚舉，相當于疊代器
除了這些之外，其他的都是非線程安全的類和接口。
記憶：線程同步：喂，SHE
喂（Vector）S（Stack）H（hashtable）E（enumeration）
（2）Lish、Set、Map
- 單列資料or雙列資料：List和Set存儲的是單列資料，Map存儲的是雙列資料
- 是否有序：List是有序的，Set和Map是無序的（LinkedHashSet、LinkedHashMap、TreeMap的疊代順序會按照插入的順序，TreeSet插入時按照元素大小通過二叉樹排序插入）
- 是否允許重複：List允許重複，Set不允許重複，Map鍵不允許重複、值可以重複
（3）Vector與ArrayList的差別：
- Vector是線程安全的, ArrayList不是線程安全的, 這是最主要的
- Vector類中的方法很多有synchronized進行修飾，這樣就導緻了Vector效率低，不能與ArrayList相比。
- 兩者都是采用線性連續空間存儲元素，當空間不足時，兩者的擴容方式不同。ArrayList不可以設定擴充的容量, 預設1.5倍; Vector可以設定, 預設2倍
- ArrayList無參構造函數中初始量為0; Vector的無參構造函數初始容量為10
（4）哈希沖突
如果兩個不同的元素，通過哈希函數得出的實際存儲位址相同怎麼辦？也就是說，當我們對某個元素進行哈希運算，得到一個存儲位址，然後要進行插入的時候，發現已經被其他元素占用了，其實這就是所謂的哈希沖突，也叫哈希碰撞。前面我們提到過，哈希函數的設計至關重要，好的哈希函數會盡可能地保證 計算簡單和散列位址分布均勻,但是，我們需要清楚的是，數組是一塊連續的固定長度的記憶體空間，再好的哈希函數也不能保證得到的存儲位址絕對不發生沖突。那麼哈希沖突如何解決呢？哈希沖突的解決方案有多種:開放定址法（發生沖突，繼續尋找下一塊未被占用的存儲位址），再散列函數法，鍊位址法，而HashMap即是采用了鍊位址法，也就是數組+連結清單的方式。
（5）HashMap 和 HashTable 差別
（1）基類不同：HashTable基于Dictionary類，而HashMap是基于AbstractMap。Dictionary是什麼？它是任何可将鍵映射到相應值的類的抽象父類，而AbstractMap是基于Map接口的骨幹實作，它以最大限度地減少實作此接口所需的工作。
（2）null不同：HashMap可以允許存在一個為null的key和任意個為null的value，但是HashTable中的key和value都不允許為null。
（3）線程安全：HashMap時單線程安全的，Hashtable是多線程安全的。由于非線程安全,HashMap 的效率要較 HashTable 的效率高一些.
（4）周遊不同：HashMap僅支援Iterator的周遊方式，Hashtable支援Iterator和Enumeration兩種周遊方式。
（5）實作同步：HashTable 是 sychronize,多個線程通路時不需要自己為它的方法實作同步,而 HashMap 在被多個線程通路的時候需要自己為它的方法實作同步;
補充：
（6）Linkedhashmap 與 hashmap 的差別
- LinkedHashMap 是 HashMap 的子類
-
LinkedHashMap 中的 Entry 增加了兩個指針 before 和 after，它們分别用于維護
雙向連結清單。
-
在 put 操作上，雖然 LinkedHashMap 完全繼承了 HashMap 的 put 操作，但是在細
節上還是做了一定的調整，比如，在 LinkedHashMap 中向哈希表中插入新 Entry 的同時，還會通過 Entry 的 addBefore 方法将其鍊入到雙向連結清單中。
- 在擴容操作上，雖然 LinkedHashMap 完全繼承了 HashMap 的 resize 操作，但是 鑒于性能和 LinkedHashMap 自身特點的考量，LinkedHashMap 對其中的重哈希過 程(transfer 方法)進行了重寫
- 在讀取操作上，LinkedHashMap 中重寫了 HashMap 中的 get 方法，通過 HashMap 中的 getEntry 方法擷取 Entry 對象。在此基礎上，進一步擷取指定鍵對應的值。
（7）數組和連結清單
記憶體中的存儲形式可以分為連續存儲和離散存儲兩種。是以，資料的實體存儲結構就有連續存儲和離
散存儲兩種，它們對應了我們通常所說的數組和連結清單。
1）數組：
是将元素在記憶體中連續存儲的，是以在查找資料的時候效率比較高。但缺點是在存儲之前，就需要申請一塊連續的記憶體空間，并且編譯時就必須确定他的空間大小，在運作的時候空間的大小無法随着需要變化。當資料量大的時候會越界，小的時候會導緻浪費記憶體空間，增删改的效率比較低。适合資料量比較少，經常查找的應用場景。
2）連結清單：
是動态申請記憶體空間，不需要像數組那樣提前申請記憶體大小，隻需在用的時候申請，根據需要動态申請和删除記憶體空間，增删比較靈活，修改、查詢效率比較低。适用于對線性表的長度或者規模難以估摸；頻繁做插入删除操作。建構動态性比較強的線性表。
參考：
（8）hashcode()和equals()方法
hashcode()和equals()方法詳解