今天來給大家談談集合。

集合類是用來存放某類對象的。集合類有一個共同特點，就是它們只容納對象（實際上是對象名，即指向地址的指針）。這一點和數組不同，數組可以容納對象和簡單數據。如果在集合類中既想使用簡單數據類型，又想利用集合類的靈活性，就可以把簡單數據類型數據變成該數據類型類的對象，然後放入集合中處理，但這樣執行效率會降低。
集合類容納的對象都是Object類的實例，一旦把一個對象置入集合類中，它的類信息將丟失，也就是說，集合類中容納的都是指向Object類對象的指針。這樣的設計是為了使集合類具有通用性，因為Object類是所有類的祖先，所以可以在這些集合中存放任何類而不受限制。當然這也帶來了不便，這令使用集合成員之前必須對它重新造型。
集合類是Java數據結構的實現。在編寫程序時，經常需要和各種數據打交道，為了處理這些數據而選用數據結構對於程序的運行效率是非常重要的。

集合原理圖

從這個圖可以得出結論

1.所有集合類都位於java.util包下。Java的集合類主要由兩個接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，這兩個接口又包含了一些子接口或實現類。

2. 集合接口：6個接口（短虛線表示），表示不同集合類型，是集合框架的基礎。

3. 抽象類：5個抽象類（長虛線表示），對集合接口的部分實現。可擴展為自定義集合類。

4. 實現類：8個實現類（實線表示），對接口的具體實現。

5. Collection 接口是一組允許重複的對象。

6. Set 接口繼承 Collection，集合元素不重複。

7. List 接口繼承 Collection，允許重複，維護元素插入順序。

8. Map接口是鍵－值對象，與Collection接口沒有什麼關係。

9.Set、List和Map可以看做集合的三大類：

List集合是有序集合，集合中的元素可以重複，訪問集合中的元素可以根據元素的索引來訪問。

Set集合是無序集合，集合中的元素不可以重複，訪問集合中的元素只能根據元素本身來訪問（也是集合裡元素不允許重複的原因）。

Map集合中保存Key-value對形式的元素，訪問時只能根據每項元素的key來訪問其value。

純手寫List框架

List集合代表一個有序集合，集合中每個元素都有其對應的順序索引。List集合允許使用重複元素，可以通過索引來訪問指定位置的集合元素。

List接口繼承於Collection接口，它可以定義一個允許重複的有序集合。因為List中的元素是有序的，所以我們可以通過使用索引（元素在List中的位置，類似於數組下標）來訪問List中的元素，這類似於Java的數組。

List接口為Collection直接接口。List所代表的是有序的Collection，即它用某種特定的插入順序來維護元素順序。用戶可以對列表中每個元素的插入位置進行精確地控制，同時可以根據元素的整數索引（在列表中的位置）訪問元素，並搜索列表中的元素。實現List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

ArrayList底層實現原理

1. Arraylist底層基於數組實現

private Object[] elementData;

2. Arraylist底層默認數組初始化大小為10個object數組

public ExtArraylist() throws Exception {

this(10);

}

public ExtArraylist(int initialCapacity) throws Exception {

if (initialCapacity < 0) {

throw new IllegalArgumentException("初始容量不能小於0 " + initialCapacity);

}

elementData = new Object[initialCapacity];

}

3. 添加元素後大於當前數組的長度，則進行擴容,將數組的長度增加原來數組的一半。

// 增大數組空間

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1); // 在原來容量的基礎上加上

// oldCapacity/2

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity; // 最少保證容量和minCapacity一樣

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity); // 最多不能超過最大容量

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

（3）Vector可以設置capacityIncrement，而ArrayList不可以，從字面理解就是capacity容量，Increment增加，容量增長的參數。

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

//擴充的空間增加原來的50%（即是原來的1.5倍）

if (newCapacity - minCapacity < 0)

//如果容器擴容之後還是不夠，那麼幹脆直接將minCapacity設為容器的大小

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

//如果擴充的容器太大了的話，那麼就執行hugeCapacity

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

/**

* 自定List接口

*/

public interface ExtList {

public void add(E object);

public Object remove(int index);

public boolean remove(E object);

public int getSize();

public Object get(int index);

}

public class ExtArrayList implements ExtList {

// 保存ArrayList中數據的數組

private transient Object[] elementData;

// ArrayList實際數量

private int size;

public ExtArrayList() {

// 默認初始容量為10

this(10);

}

public ExtArrayList(int initialCapacity) {

if (initialCapacity < 0) {

throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);

}

// 初始化數組容量

elementData = new Object[initialCapacity];

}

// 添加方法實現

public void add(Object object) {

ensureExplicitCapacity(size + 1);

elementData[size++] = object;

}

public void add(int index, Object object) {

rangeCheck(index);

ensureExplicitCapacity(size + 1);

System.arraycopy(elementData, index, elementData, index + 1, size - index);

elementData[index] = object;

size++;

}

public void ensureExplicitCapacity(int minCapacity) {

// 如果存入的數據,超出了默認數組初始容量 就開始實現擴容

if (size == elementData.length) {

// 獲取原來數組的長度 2

int oldCapacity = elementData.length;

// oldCapacity >> 1 理解成 oldCapacity/2 新數組的長度是原來長度1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1); // 3

if (newCapacity < minCapacity) {

// 最小容量比新容量要小的,則採用初始容量minCapacity

newCapacity = minCapacity;

}

elementData = Arrays.copyOf(elementData, newCapacity);

}

}

// 獲取數據

public Object get(int index) {

rangeCheck(index);

return elementData[index];

}

//刪除指定下標數據數據

public Object remove(int index) {

Object object = get(index);

int numMoved = elementData.length - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index + 1, elementData, index, numMoved);

elementData[--size] = null;

return object;

}

public boolean remove(E object) {

for (int i = 0; i < elementData.length; i++) {

Object element = elementData[i];

if (element.equals(object)) {

remove(i);

return true;

}

}

return false;

}

private void rangeCheck(int index) {

if (index >= size) {

throw new IndexOutOfBoundsException("數組越界啦!");

}

}

return size;

}

}

LinkeList原理

LinkedList 和 ArrayList 一樣，都實現了 List 接口，但其內部的數據結構有本質的不同。LinkedList 是基於鏈表實現的（通過名字也能區分開來），所以它的插入和刪除操作比 ArrayList 更加高效。但也是由於其為基於鏈表的，所以隨機訪問的效率要比 ArrayList 差。

LinkedList數據結構原理

LinkedList底層的數據結構是基於雙向循環鏈表的，且頭結點中不存放數據,如下：

既然是雙向鏈表，那麼必定存在一種數據結構——我們可以稱之為節點，節點實例保存業務數據，前一個節點的位置信息和後一個節點位置信息，如下圖所示：

數組和鏈表結構對比

數組　是將元素在內存中連續存放，由於每個元素佔用內存相同，可以通過下標迅速訪問數組中任何元素。但是如果要在數組中增加一個元素，需要移動大量元素，在內存中空出一個元素的空間，然後將要增加的元素放在其中。同樣的道理，如果想刪除一個元素，同樣需要移動大量元素去填掉被移動的元素。如果應用需要快速訪問數據，很少插入和刪除元素，就應該用數組。

鏈表中的元素在內存中不是順序存儲的，而是通過存在元素中的指針聯繫到一起，每個結點包括兩個部分：一個是存儲 數據元素 的　數據域，另一個是存儲下一個結點地址的 指針。

　如果要訪問鏈表中一個元素，需要從第一個元素開始，一直找到需要的元素位置。但是增加和刪除一個元素對於鏈表數據結構就非常簡單了，只要修改元素中的指針就可以了。如果應用需要經常插入和刪除元素你就需要用鏈表。

內存存儲區別

數組從棧中分配空間, 對於程序員方便快速,但自由度小。

鏈表從堆中分配空間, 自由度大但申請管理比較麻煩.　

邏輯結構區別

數組必須事先定義固定的長度（元素個數），不能適應數據動態地增減的情況。當數據增加時，可能超出原先定義的元素個數；當數據減少時，造成內存浪費。　

鏈表動態地進行存儲分配，可以適應數據動態地增減的情況，且可以方便地插入、刪除數據項。（數組中插入、刪除數據項時，需要移動其它數據項）　

對比

1、存取方式上，數組可以順序存取或者隨機存取，而鏈表只能順序存取；　

2、存儲位置上，數組邏輯上相鄰的元素在物理存儲位置上也相鄰，而鏈表不一定；　

3、存儲空間上，鏈表由於帶有指針域，存儲密度不如數組大；　

4、按序號查找時，數組可以隨機訪問，時間複雜度為O(1)，而鏈表不支持隨機訪問，平均需要O(n)；　

5、按值查找時，若數組無序，數組和鏈表時間複雜度均為O(1)，但是當數組有序時，可以採用折半查找將時間複雜度降為O(logn)；　

6、插入和刪除時，數組平均需要移動n/2個元素，而鏈表只需修改指針即可；　

7、空間分配方面：

　　數組在靜態存儲分配情形下，存儲元素數量受限制，動態存儲分配情形下，雖然存儲空間可以擴充，但需要移動大量元素，導致操作效率降低，而且如果內存中沒有更大塊連續存儲空間將導致分配失敗；

鏈表存儲的節點空間只在需要的時候申請分配，只要內存中有空間就可以分配，操作比較靈活高效；

LinkeList相關代碼

public class LinkeList {

// 第一個元素

private Node first;

// 最後一個元素

private Node last;

// 實際存放在長度

private int size;

class Node {

// 上一個節點

Node prev;

// 節點內容

Object object;

// 下一個節點

Node next;

}

public void add(E e) {

// 創建新的節點

Node node = new Node();

// 節點內容

node.object = e;

if (first == null) {

// // 上一個節點

// node.prev = null;

// // 下一個節點

// node.next = null;

// 第一個元素和最後一個元素都是為node

first = node;

} else {

// 存放上一個節點內容

node.prev = last;

// 設置上一個節點的next為當前節點

last.next = node;

}

last = node;

size++;

}

public void add(int index, E e) {

// 1.循環遍歷到當前index位置Node

// 2.新增當前節點

Node newNode = new Node();

newNode.object = e;

// 獲取原來的節點

LinkeList.Node olNode = getNode(index);

// 獲取原來上一個節點

LinkeList.Node olNodePrev = olNode.prev;

// 4.新增節點的上一個還是當前Node節點的 上一個節點,下一個就是原來的節點

// 原來上一個節點變為當前節點

olNode.prev = newNode;

if (olNodePrev == null)

first = newNode;

else

// 原來上一個節點的下一個節點變為當前節點

olNodePrev.next = newNode;

// 新節點的下一個節點為原來節點

newNode.next = olNode;

size++;

}

public E get(int index) {

LinkeList.Node node = getNode(index);

return (E) node.object;

}

public Node getNode(

Node node = null;

if (first != null) {

node = first;

for (int i = 0; i < index; i++) {

node = node.next;

}

}

return node;

}

public void remove(int index) {

checkElementIndex(index);

LinkeList.Node node = getNode(index);

LinkeList.Node prevNode = node.prev;

LinkeList.Node nextNode = node.next;

// 設置上一個節點的next為當前刪除節點的next

if (prevNode != null) {

prevNode.next = nextNode;

}

// 判斷是否是最後一個節點

if (nextNode != null) {

nextNode.prev = prevNode;

}

}

size--;

}

}

return index >= 0 && index < size;

}

private void checkElementIndex(int index) {

if (!isElementIndex(index))

throw new IndexOutOfBoundsException("越界啦!");

}

}

純手寫Map框架

HashMap的介紹

HashMap的實現原理

從底層結構、put和get方法、hash數組索引、擴容機制等幾個方面來分析HashMap的實現原理：

底層結構

HashMap的底層結構是由數組+鏈表構成的。

數組（紫色）：hash數組（桶），數組元素是每個鏈表的頭節點

鏈表（綠色）：解決hash衝突，不同的key映射到了數組的同一索引處，則形成鏈表。

put和get方法

put()方法大概過程如下：

如果添加的key值為null，那麼將該鍵值對添加到數組索引為0的鏈表中，不一定是鏈表的首節點。

如果添加的key不為null，則根據key計算數組索引的位置：

數組索引處存在鏈表，則遍歷該鏈表，如果發現key已經存在，那麼將新的value值替換舊的value值

數組索引處不存在鏈表，將該key-value添加到此處，成為頭節點

get()方法的大概過程：

1. 如果key為null，那麼在數組索引table[0]處的鏈表中遍歷查找key為null的value

2. 如果key不為null，根據key找到數組索引位置處的鏈表，遍歷查找key的value，找到返回value，若沒找到則返回null

擴容機制

先看一個例子，創建一個HashMap，初始容量默認為16，負載因子默認為0.75，那麼什麼時候它會擴容呢？來看以下公式：

實際容量 = 初始容量 × 負載因子

1

計算可知，16×0.75=12，也就是當實際容量超過12時，這個HashMap就會擴容。

初始容量

當構造一個hashmap時，初始容量設為不小於指定容量的2的次方的一個數（new HashMap(5)， 指定容量為5，那麼實際初始容量為8，2^3=8>5），且最大值不能超過2的30次方。

負載因子

負載因子是哈希數組在其容量自動增加之前可以達到多滿的一種尺度。（時間與空間的折衷） 當哈希數組中的條目數超出了加載因子與初始容量的乘積時，則要對該哈希數組進行擴容操作（即resize）。

特點：

1*16=16

0.75*16=12 0.5*16=8 負載因子越小， 容易擴容—容易擴容的時候 產生新的空數組位置

三次擴容

負載因子1 負載因子0.75 負載因子0.5

1.16*2=32 16 1.16*2=32 12 16*2=32 8

2.32*2=64 32 2.32*2=64 24 32*2=64 16

2.64*2=128 64 3.64*2=128 48 64*2=128 32

存放數據10000萬個 >13毫秒

存放數據10000萬個 13毫秒

存放數據10000萬個 21毫秒

存放數據10000萬個 76左右毫秒

存放數據10000萬個 77左右毫秒

負載因子越小，容易擴容，浪費空間，但查找效率高 鏈表特別短 減少hash衝突

擴容過程

HashMap在擴容時，新數組的容量將是原來的2倍，由於容量發生變化，原有的每個元素需要重新計算數組索引Index，再存放到新數組中去，這就是所謂的rehash。

eqauls方法和hashCode方法

1 如果兩個對象相同，那麼它們的hashCode值一定要相同。也告訴我們重寫equals方法，一定要重寫hashCode方法，也就是說hashCode值要和類中的成員變量掛上鉤，對象相同–>成員變量相同—->hashCode值一定相同。

2 如果兩個對象的hashCode相同，它們並不一定相同，這裡的對象相同指的是用eqauls方法比較。

基於Linkedlist實現Map

代碼實現方式

/**

@decptions:.純手寫HasMap集合 完全採用Arraylist實現 缺點效率低

* @auther YC

* */

public class ExtArrayListMap {

List<entry>> tables = new ArrayList<entry>>();/<entry>/<entry>

public void put(Key key, Value value) {

// 判斷key是否已經重複

Entry existEntry = getEntry(key);

if (existEntry != null) {

existEntry.value = value;

return;

}

Entry entry = new Entry(key, value);

tables.add(entry);

}

public Value get(String key) {

for (Entry entry : tables) {

if (entry.key.equals(key)) {

return entry.value;

}

}

return null;

}

public void remove(Key key) {

Entry existEntry = getEntry(key);

if (existEntry != null) {

tables.remove(existEntry);

}

}

public Entry getEntry(Key key) {

for (Entry entry : tables) {

if (entry.key.equals(key)) {

return entry;

}

}

return null;

}

}

class Entry {

public Entry(Key key, Value value) {

this.key = key;

this.value = value;

}

Key key;

Value value;

}

public Entry(Object key, Object value) {

<code>this.key = key;/<code>

<code>this.value = value;/<code>

<code>}/<code>

<code>Object key;/<code>

<code>Object value/<code> 

<code>}/<code>

基於JDK1.7版本實現HashMap

創建Map接口

<code>/**/<code>

<code> * @decptions 純手寫Map集合/<code>

<code> * @author YC/<code>

<code> * @date 2020/3/5/<code>

<code> *//<code>

<code>public interface ExtMap {/<code>

<code> /<code>

<code>// 向集合中插入數據/<code>

<code>public V put(K k, V v);/<code>

<code>// 根據k 從Map集合中查詢元素/<code>

<code>public V get(K k);/<code>

<code>// 獲取集合元素個數/<code>

<code>public int size();/<code>

<code>interface Entry {/<code>

<code>K getKey();/<code>

<code>V getValue() /<code>

<code>V setValue(V value);/<code>

<code>}/<code>

<code>}/<code>

創建HashMap實現

<code>public class ExtHashMap implements ExtMap {/<code>

<code>// 1.定義table 存放HasMap 數組元素 默認是沒有初始化容器 懶加載/<code>

<code>Node[] table = null;/<code>

<code>// 2. 實際用到table 存儲容量 大小/<code>

<code>int size;/<code>

<code>// 3.HashMap默認負載因子，負載因子越小，hash衝突機率越低， 根據每個鏈表的個數/<code>

<code>float DEFAULT_LOAD_FACTOR = 0.75f;/<code>

<code>// 4.table默認初始大小 16/<code> 

<code>static int DEFAULT_INITIAL_CAPACITY = 16; // 16/<code>

<code>public V put(K key, V value) {/<code>

<code> /<code>

<code>// 1.判斷table 數組大小是否為空（如果為空的情況下 ，做初始化操作）/<code>

<code>if (table == null) {/<code>

<code>table = new Node[DEFAULT_INITIAL_CAPACITY];/<code>

<code>}/<code>

<code>// 2.判斷數組是否需要擴容 實際存儲容量=負載因子0.75*初始容量16 =12 相當於如果長度大於12的時候就需要開始數組擴容/<code>

<code>if (size >= (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)) {/<code>

<code>System.out.println("開始擴容啦！！！！");/<code>

<code>resize();/<code>

<code>}/<code>

<code>// 3.計算hash值指定下標位置/<code>

<code>int index = getIndex(key, DEFAULT_INITIAL_CAPACITY);/<code>

<code>Node node = table[index];/<code>

<code>if (node == null) {/<code>

<code>// 沒有發生hash衝突問題/<code>

<code>node = new Node(key, value, null);/<code>

<code>size++;/<code>

<code>} else {/<code>

<code>Node newNode = node;/<code>

<code>while (newNode != null) {/<code>

<code>// // 已經發生hash衝突問題key 直接添加(衝突node)到前面了 不是往後面加/<code>

<code>if (newNode.getKey().equals(key) || newNode.getKey() == key) {/<code>

<code>// hashCodoe 相同，而且equals 相等情況 說明是同一個對象 修改值/<code>

<code>// node.value = value;/<code>

<code>return newNode.setValue(value);/<code>

<code>} else {/<code>

<code>// 繼續添加，排在前面 hascode 取模餘數相同 index 存放在鏈表 或者hashCode 相同但是對象不同/<code>

<code>// 新的node 的next 原來的node/<code>

<code>if (newNode.next == null) {/<code>

<code>node = new Node(key, value, node);/<code>

<code>size++;/<code>

<code>}/<code>

<code>}/<code>

<code>newNode = newNode.next;/<code>

<code>}/<code>

<code>}/<code>

<code>table[index] = node;/<code>

<code>return null;/<code>

<code>}/<code>

<code> /<code>

<code>// hashMap數組擴容機制/<code>

<code>private void resize() {/<code>

<code>// 1.定義新的數組元素/<code>

<code>Node[] newTables = new Node[DEFAULT_INITIAL_CAPACITY << 1];/<code>

<code>// 2. 將老的table的key index重新計算下標/<code>

<code>for (int i = 0; i < table.length; i++) {/<code>

<code>// 老的Node節點/<code>

<code>Node oldNode = table[i];/<code>

<code>while (oldNode != null) {/<code>

<code>table[i] = null;/<code>

<code>// 重新計算index 索引下標位置/<code>

<code>K oldKey = oldNode.key;/<code>

<code>int index = getIndex(oldKey, newTables.length);/<code>

<code>// 老的next/<code>

<code>Node oldnext = oldNode.next;/<code>

<code>// 判斷newTables數組中,是否存在下標相同，如果下標相同則存放在原來的.next/<code>

<code>oldNode.next = newTables[index];/<code>

<code>// 將原來的node賦值給新的node/<code>

<code>newTables[index] = oldNode;/<code>

<code>// 獲取下一個節點,判斷是否繼續循環/<code>

<code>oldNode = oldnext;/<code>

<code>}/<code>

<code>}/<code>

<code>// 3.將newTable賦值給table;/<code>

<code>table = newTables;/<code>

<code>DEFAULT_INITIAL_CAPACITY = newTables.length;/<code>

<code>newTables = null;// 將 對象變為不可達對象/<code>

<code>}/<code>

<code>}/<code>

<code>} /<code>

<code>}/<code>

<code> /<code>

<code>public int getIndex(K k, int length) {/<code>

<code>// System.out.println("k:" + k + ",hashCode=" + hashCode);/<code>

<code>int index = k == null ? 0 : k.hashCode() % length;/<code>

<code>return index;/<code>

<code>}/<code>

<code>public V get(K k) {/<code>

<code>Node node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);/<code> 

<code>return node == null ? null : node.value;/<code>

<code>}/<code>

<code>public Node getNode(Node node, K k) {/<code>

<code>while (node != null) {/<code>

<code>if (node.getKey().equals(k)) {/<code>

<code>return node;/<code>

<code>}/<code>

<code>node = node.next;/<code>

<code>}/<code>

<code>return null;/<code>

<code>}/<code>

<code>public int size() {/<code>

<code>return size;/<code>

<code>}/<code>

<code>// 定義節點/<code>

<code>class Node implements Entry {/<code>

<code>// 存放Map 集合 key/<code>

<code>private K key;/<code>

<code>// 存放Map 集合 value/<code>

<code>private V value;/<code>

<code>// 下一個節點Node/<code>

<code>private Node next;/<code>

<code>public Node(K key, V value, Node next) {/<code>

<code>super();/<code>

<code>this.key = key;/<code>

<code>this.value = value;/<code>

<code>this.next = next;/<code>

<code>}/<code>

<code>public K getKey() {/<code>

<code>return this.key;/<code>

<code>}/<code>

<code>public V getValue() {/<code>

<code>return this.value;/<code>

<code>}/<code>

<code>public V setValue(V value) {/<code>

<code>// 設置新值的返回老的 值/<code>

<code>V oldValue = this.value;/<code>

<code>this.value = value;/<code>

<code>return oldValue;/<code>

<code>}/<code>

<code>} /<code>

<code>}/<code>

HashMap 核心源碼部分的分析

1. HashMap只允許一個為null的key。

2. HashMap的擴容：當前table數組的兩倍

3. HashMap實際能存儲的元素個數： capacity * loadFactor

4. HashMap在擴容的時候，會重新計算hash值，並對hash的位置進行重新排列， 因此，為了效率，儘量給HashMap指定合適的容量，避免多次擴容。

是不是很簡單呢，感謝大家的關注和支持，喜歡記得點贊轉發，您的支持就是我的動力！！！

閱讀更多 程序員小楊 的文章

關鍵字: 數據結構 0verflow 設計