這篇文章將為大家詳細講解有關Java中集合的底層實現原理是什么，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

我們一直強調網站設計、成都網站設計對于企業的重要性,如果您也覺得重要,那么就需要我們慎重對待,選擇一個安全靠譜的網站建設公司,企業網站我們建議是要么不做，要么就做好,讓網站能真正成為企業發展過程中的有力推手。專業網站制作公司不一定是大公司,創新互聯公司作為專業的網絡公司選擇我們就是放心。

Java集合類實現原理

1.Iterable接口

• 定義了迭代集合的迭代方法

iterator()
forEach() 對1.8的Lambda表達式提供了支持

2. Collection接口

• 定義了集合添加的通用方法

int size();
boolean isEmpty();
boolean contains();
boolean add()
boolean addAll()
boolean remove()
    	removeAll()
Object[] toArray()

3.List接口

• 元素被添加到集合中以后，取出的時候是按照放入順序。

• List可以重復。

• 存在下標，可以直接依靠下標取值

E get()
E set()
E indexOf()
int lastIndexOf()
ListIterator listIterator()

3.1 ArrayList類

• 底層是一個Object數組。

transient Object[] elementData; // non-private to simplify nested class access

• 初始容量為10

private static final int DEFAULT_CAPACITY = 10;

• 當數組容量不夠是自動擴容為以前的1.5倍

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);

• 數組最大容量為Integer.MAX_VALUE-8

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 線程不安全

3.2.Vector類（不常用）

• 底層是一個Object數組

protected Object[] elementData;

• 初始容量為10

public Vector() {
        this(10);
    }

• 數組容量不夠的時候自動擴容為原來的一倍

int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);

• 數組最大容量為

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 線程安全

3.3 LinkedList

• 底層是一個列表

/**
     * Pointer to first node.
     */
    transient Node first;

    /**
     * Pointer to last node.
     */
    transient Node last;

• 存放節點個數

transient int size = 0;

• 默認構造方法增加元素實現原理

//當默認構造的時候,創建集合的時候
public LinkedList() {
    }
//使用添加方法,直接將元素添加到末尾
public boolean add(E e) {
        linkLast(e);
        return true;
    }
//給尾部添加元素
void linkLast(E e) {
    	//獲取最后一個元素
        final Node l = last;
    	//新創建一個界面，其尾結點為null
        final Node newNode = new Node<>(l, e, null);
    	//將數組中存儲最后一個界面的元素復制
        last = newNode;
    	//如果此時集合為null，則另第一個節點也為該元素，否則就將這個元素的下一個節點設置為該元素節點
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    //節點數量增加
        size++;
        modCount++;
    }

• 指定下標增加元素實現原理

//LinkedList支持指定的索引出增加節點
public void add(int index, E element) {
    	//檢查傳入的索引是否符合要求
        checkPositionIndex(index);
		//如果這個索引是最后一個節點，則直接添加
        if (index == size)
            linkLast(element);
        else
            //否則
            linkBefore(element, node(index));
    }
//返回了指定下標的Node
Node node(int index) {
        // assert isElementIndex(index);
		//如果此時的下標小于節點的一半，相當于一個二分查找的方法，
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    //將需要插入的元素進行插入
void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

> 實現的思想可以歸結為：每一次的插入或者移除，都是通過node()方法獲取指定的Node節點，然后通過linkBefore或者linkLast這些方法來具體進行鏈表的操作。

4.Set接口

• 插入無序

• 元素不能重復

• 底層均為Map集合實現

4.1 TreeSet類

先來瞅一眼這個類的繼承關系吧

• 實現了AbstractSet擁有了Set的屬性和方法

• 實現了NavigableSet，支持一系列導航方法，可以進行精確查找

剖析一下這個類的源碼

• 底層實現TreeMap結構

public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable
{
    /**
     * 存放生成的TreeMap集合
     */
    private transient NavigableMap m;

    // 作為值添加到TreeMap中，即每一個Entry的鍵不同但值相同，都是一個對象的地址
    private static final Object PRESENT = new Object();
    
    
    public TreeSet() {
        this(new TreeMap<>());
    }
    
    TreeSet(NavigableMap m) {
        this.m = m;
    }

//添加方法
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

• 進行了排序。(在HashMap原理進行分析)

4.2 HashSet類

• 底層基于HashMap

	//鍵
	private transient HashMap map;
	
    // 值
    private static final Object PRESENT = new Object();

		//構造
	public HashSet() {
        map = new HashMap<>();
    }

• 無序

• 不可重復

4.3 LinkedHashSet類

• 底層基于LinkedHashMap實現，通過LinkedHashMap中的方法實現了順序存值。具體實現可看下面的LinkedHashMap

public LinkedHashSet() {
        super(16, .75f, true);
    }
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

5. Map類

• 鍵值對的形式存放數據

• 定義了通用的方法

• 不可重復

int size()
isEmpty();
containsKey()
containsValue()
get()    
put()
remove()    
keyset()
values()
entrySet()

5.1Entry類

• Map類的內部類，用來獲取所有的鍵值

5.2HashMap類

> put的時候，會通過hash算法，計算一個index，這個index就是節點數組的下標，此時這個實體就被存儲到這個數組中。但是由于這個hash算法不能保證任何一個key值計算出來的hash值均相同，所以采用鏈表的方式，掛載相同的index的實體。在1.8以后，當鏈表的節點數量大于或者等于8的時候且數組的容量大于64的時候，就會將鏈表轉換為紅黑樹

• 底層實現：數組+鏈表或者紅黑樹

//保存的數組，初始化16個
transient Node[] table;
//為entrySet和value提供一個緩存
transient Set> entrySet;
//元素的數量
transient int size;
//初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//數組遞增的策略 當size > capacity*loadFacotor的時候遞增
final float loadFactor;

• Node節點的定義(列表)

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

• 初始容量為16的原因

//hash算法，保證哈希值平均分布，只有當為16的時候才可以最大程度的保證平均分布
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

• put方法

//創建一個HashMap對象，并且設定它的遞增策略為0.75倍
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

static final float DEFAULT_LOAD_FACTOR = 0.75f;
//執行put方法
public V put(K key, V value) {
    //key通過hash算法計算一個index
        return putVal(hash(key), key, value, false, true);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
    //第一次進入為null,所以執行初始化容器大小
        if ((tab = table) == null || (n = tab.length) == 0)
            //此時返回的就是初始化容器以后的大小即16
            n = (tab = resize()).length;
    	//計算下標，如果等于null，直接賦值
    	if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    	else {
            //如果該數組剛好有值，則采用鏈表或者紅黑樹的方式添加數據節點
            Node e; K k;
            //判斷兩個節點是否相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判斷當前節點是否屬于紅黑樹節點
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                //如果不是直接進行鏈表連接
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //將當前節點的下一個節點設置為新的實體節點
                        p.next = newNode(hash, key, value, null);
                        //如果此時的節點容量為7那么將鏈表轉換為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //判斷新傳入的實體和當前綁定節點的子節點是否相同，如果相同直接退出
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //進入這個子節點
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
    //修改次數
        ++modCount;
    //查看當前容器的容量是否大于threshold ,如果大于增加數組容量為原來的一倍
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}
    
    //初始化容器大小
final Node[] resize() {
        Node[] oldTab = table;
    	//舊容量為0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
    	int oldThr = threshold;
    //設置當前容器的遞增為0
        int newCap, newThr = 0;
    //此時的oldCap=0 , newThr = 0 直接else執行
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //擴容，將數組的容量和擴容因子變為原來的一倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //初始化容器為默認16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //初始化闕值
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
    	//初始化存儲容器數組
        table = newTab;

5.2.1 Hash數據結構

在java中所有的數據結構都可以使用數組和指針即引用來實現。而Hash也成散列，就是一個鏈表加數組實現。

Hash數據結構具有無序的特征。這里的無序指的是存入順序于取出順序不一樣。

什么是Hash表的負載因子？負載因子代表了Hash表的空間填充度，即負載因子越大其對空間的使用率越高，但這也造成了查詢速度慢，而負載因子越小，其查詢速度越快，空間填充度越低。所以在使用的過程一般會通過保持一個平衡。如HashMap的負載因子初始化為0.75.保證了兩者之間的權衡。

Hash表如何存儲數據？Hash表的每一次存儲都會先調用一個Hash函數，而這個Hash函數最后運算的值就是所存儲數據的下標。即當需要查詢數據的時候，僅僅只需要調用Hash函數進行一次計算就可以得出該數據所在的下標。

5.2.2 HashMap中的數據結構實現

下面詳細解析一下HashMap中的Hash表的實現

在HashMap初始化的時候，首先會給內部的負載因子賦值為0.75，然后創建對象，注意此時的HashMap內部的Node數組并沒有實例化。

開始put數據，此時put方法會調用putVal()方法，但在調用這個putVal方法之前，他首先通過hash算法計算了一次這個key所對應的哈希值，而在putVal()方法中，又將這個哈希值通過和數組的容量-1進行&運算，得出了在這個數組的容量范圍內的一個index。此時這個key所需要存儲的index正式確定。

確定key以后，需要判斷該index下有沒有值，如果有，判斷新增的這個元素與現有這個元素是否相同，如果相同，替換該值；如果不相同，遍歷這個鏈表，判斷這個鏈表中是否存在和新增元素相同的值，如果不存在則直接添加到鏈表尾部，如果存在，替換該值；當然如果此時鏈表中節點的個數大于或者等于8且數組的容量大于64的時候以后就將鏈表轉化為紅黑樹。

containKey方法的實現，就是直接通過hash方法計算出哈希值，然后通過&運算，獲取數組下標，判斷這個下標是否為該值，如果不是，則進行遍歷鏈表或者紅黑樹。

containeValue方法實現，一級一級遍歷時間復雜度似乎蠻高的

5.3 LinkedHashMap類

我們所知道的LinkedHashMap類可以順序的輸出用戶所輸入的數據。下面談一下他的實現方式

LinkedHashMap中定義了一個Entry類，繼承了HashMap.Node節點類，額外定義了兩個屬性，before和after，還有最重要的一個方法newNode，這個方法被LinkedHashMap重寫，確定了順序性。看到這也就知道這是雙向鏈表的兩個值了。LinkedHashMap在每一次put元素之后都要將該元素的上一個節點設置為之前的那個節點。代碼說明！！！

• 成員屬性

	// 鏈表的第一個節點，LinkedHashMap會保存鏈表的最后一個節點的屬性，以方便進行節點添加
    transient LinkedHashMap.Entry head;

  	// 鏈表的最后一個節點
    transient LinkedHashMap.Entry tail;

• 創建對象了

//老方法，new個對象再說（單身狗的吶喊）
public LinkedHashMap() {
        super();
        accessOrder = false;
    }
//直接調用HashMap的put方法
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    //在putVal中調用了
    afterNodeAccess(e);
    afterNodeInsertion(evict);

Node newNode(int hash, K key, V value, Node e) {
        LinkedHashMap.Entry p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

// link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry p) {
        //獲取最后一個節點
        LinkedHashMap.Entry last = tail;
        //將最后一個節點定義為新增的節點
        tail = p;
        //如果等于null那么說明之前沒有元素
        if (last == null)
            head = p;
        else {
            //如果有，將這個元素的上一個節點定義為之前的最后一個元素
            p.before = last;
            //最后一個節點的下一個元素定義為新元素
            last.after = p;
        }
    }

//判斷這個新的節點是否為最后一個節點，如果不是移動該節點到最后
void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
    		//查看當前最后一個節點是否為當前新增的元素
        if (accessOrder && (last = tail) != e) {
            //p為當前元素，a為下一個元素，b為上一個元素
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            //將p的下一個元素定義為null，切斷和之前元素的聯系
            p.after = null;
            //如果上一個元素為null ，則說明將該節點的下一個節點賦值為頭結點
            if (b == null)
                head = a;
            else
                //否則，將上一個節點的下一個節點定義為a，到此，這個新的節點已經被獨立出來了
                b.after = a;
            //如果此時a不為null
            if (a != null)
                //則直接賦值
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

//永遠不起作用removeEldestEntry方法永遠返回false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }

5.4 TreeMap類

• 底層實現：紅黑樹

• 繼承了NavigableMap接口，NavigableMap接口繼承了SortedMap接口，可支持一系列導航方法即導航操作

• 實現了Cloneable接口，可被克隆

• 自然排序

5.4.1TreeMap創建源碼分析

• TreeMap定義的字段

//比較器
private final Comparator comparator;
//根節點
    private transient Entry root;
//節點數量
    private transient int size = 0;
//修改次數
    private transient int modCount = 0;
//紅黑顏色判斷
private static final boolean RED   = false;
    private static final boolean BLACK = true;

//節點實體
static final class Entry implements Map.Entry {
        K key;
        V value;
        Entry left;
        Entry right;
        Entry parent;
    //默認顏色為黑色
        boolean color = BLACK;
}

• 創建對象

public TreeMap() {
    //默認構造器
        comparator = null;
    }
public TreeMap(Comparator comparator) {
    //傳入自定義的構造器
        this.comparator = comparator;
    }
public TreeMap(Map m) {
        comparator = null;
        putAll(m);
    }

• Put對象

 public V put(K key, V value) {
     //賦值
        Entry t = root;
     //如果此時的root為null 
        if (t == null) {
            //檢查這個key是否為null
            compare(key, key); // type (and possibly null) check
			//創建根節點
            root = new Entry<>(key, value, null);
            size = 1;//設置節點數量
            modCount++;//修改次數增加
            return null;
        }
     	//定義比較值
        int cmp;
        Entry parent;
        // split comparator and comparable paths
        Comparator cpr = comparator;
     //如果此時存在自定義比較器，根據比較器規則進行二分比較
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    //形同替換value值
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            //使用默認的比較器，查找方法一樣
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable k = (Comparable) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
     //沒有當前節點，則創建該元素的實體節點
        Entry e = new Entry<>(key, value, parent);
     //根據比較器規則，添加節點
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
     //紅黑樹自動平衡算法
        fixAfterInsertion(e);
     //節點數量，修改數量遞增
        size++;
        modCount++;
        return null;
    }

5.4.2 TreeMap對象增加的過程

創建一個TreeMap，此時可以傳入一個比較器，如果不傳入按照默認的自然順序進行比較。

put對象，首先，檢查該root節點是否為null，如果為null，檢查當前傳入key是否為null，不為null，則直接創建一個root節點。如果當前root節點有值，則通過二分查找，尋找當前可以進行添加的父節點，找到以后按照比較器規則進行添加。

添加以后，紅黑樹進行自動平衡實現。

5.5 HashTable類

HashTable也是基于哈希表實現，和HashMap不同的是HashTable是線程安全的。

• 底層實現：哈希表+鏈表

 private transient Entry[] table;//存儲數組
 private transient int count;//容器中數據多少
private int threshold;//容器容量達到次數以后進行修改
private transient int modCount = 0;//修改次數

• Hash函數

		int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

• 初始化。在構造方法中初始化。初始化指為11

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

• put方法

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
    	//hash函數計算一個index
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry entry = (Entry)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }
//增加實體
private void addEntry(int hash, K key, V value, int index) {
        Entry tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry e = (Entry) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }

5.5.1 HashTable和HashMap的區別

5.6 Properties類

• Java配置文件中用的居多

• 可以直接通過load方法加載配置文件，通過store方法存儲配置文件

• 泛型鎖定，為兩個String類型

關于Java中集合的底層實現原理是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。