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

我們一直強(qiáng)調(diào)網(wǎng)站設(shè)計、成都網(wǎng)站設(shè)計對于企業(yè)的重要性,如果您也覺得重要,那么就需要我們慎重對待,選擇一個安全靠譜的網(wǎng)站建設(shè)公司,企業(yè)網(wǎng)站我們建議是要么不做，要么就做好,讓網(wǎng)站能真正成為企業(yè)發(fā)展過程中的有力推手。專業(yè)網(wǎng)站制作公司不一定是大公司,創(chuàng)新互聯(lián)公司作為專業(yè)的網(wǎng)絡(luò)公司選擇我們就是放心。

Java集合類實(shí)現(xiàn)原理

1.Iterable接口

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

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

2. Collection接口

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

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

3.List接口

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

• List可以重復(fù)。

• 存在下標(biāo)，可以直接依靠下標(biāo)取值

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

3.1 ArrayList類

• 底層是一個Object數(shù)組。

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

• 初始容量為10

private static final int DEFAULT_CAPACITY = 10;

• 當(dāng)數(shù)組容量不夠是自動擴(kuò)容為以前的1.5倍

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

• 數(shù)組最大容量為Integer.MAX_VALUE-8

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

• 線程不安全

3.2.Vector類（不常用）

• 底層是一個Object數(shù)組

protected Object[] elementData;

• 初始容量為10

public Vector() {
        this(10);
    }

• 數(shù)組容量不夠的時候自動擴(kuò)容為原來的一倍

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

• 數(shù)組最大容量為

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;

• 存放節(jié)點(diǎn)個數(shù)

transient int size = 0;

• 默認(rèn)構(gòu)造方法增加元素實(shí)現(xiàn)原理

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

• 指定下標(biāo)增加元素實(shí)現(xiàn)原理

//LinkedList支持指定的索引出增加節(jié)點(diǎn)
public void add(int index, E element) {
    	//檢查傳入的索引是否符合要求
        checkPositionIndex(index);
		//如果這個索引是最后一個節(jié)點(diǎn)，則直接添加
        if (index == size)
            linkLast(element);
        else
            //否則
            linkBefore(element, node(index));
    }
//返回了指定下標(biāo)的Node
Node node(int index) {
        // assert isElementIndex(index);
		//如果此時的下標(biāo)小于節(jié)點(diǎn)的一半，相當(dāng)于一個二分查找的方法，
        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;
        }
    //將需要插入的元素進(jìn)行插入
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++;
    }

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

4.Set接口

• 插入無序

• 元素不能重復(fù)

• 底層均為Map集合實(shí)現(xiàn)

4.1 TreeSet類

先來瞅一眼這個類的繼承關(guān)系吧

• 實(shí)現(xiàn)了AbstractSet擁有了Set的屬性和方法

• 實(shí)現(xiàn)了NavigableSet，支持一系列導(dǎo)航方法，可以進(jìn)行精確查找

剖析一下這個類的源碼

• 底層實(shí)現(xiàn)TreeMap結(jié)構(gòu)

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;
    }

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

4.2 HashSet類

• 底層基于HashMap

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

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

• 無序

• 不可重復(fù)

4.3 LinkedHashSet類

• 底層基于LinkedHashMap實(shí)現(xiàn)，通過LinkedHashMap中的方法實(shí)現(xiàn)了順序存值。具體實(shí)現(xiàn)可看下面的LinkedHashMap

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

5. Map類

• 鍵值對的形式存放數(shù)據(jù)

• 定義了通用的方法

• 不可重復(fù)

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

5.1Entry類

• Map類的內(nèi)部類，用來獲取所有的鍵值

5.2HashMap類

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

• 底層實(shí)現(xiàn)：數(shù)組+鏈表或者紅黑樹

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

• Node節(jié)點(diǎn)的定義(列表)

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

• put方法

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

static final float DEFAULT_LOAD_FACTOR = 0.75f;
//執(zhí)行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;
    //第一次進(jìn)入為null,所以執(zhí)行初始化容器大小
        if ((tab = table) == null || (n = tab.length) == 0)
            //此時返回的就是初始化容器以后的大小即16
            n = (tab = resize()).length;
    	//計算下標(biāo)，如果等于null，直接賦值
    	if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    	else {
            //如果該數(shù)組剛好有值，則采用鏈表或者紅黑樹的方式添加數(shù)據(jù)節(jié)點(diǎn)
            Node e; K k;
            //判斷兩個節(jié)點(diǎn)是否相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判斷當(dāng)前節(jié)點(diǎn)是否屬于紅黑樹節(jié)點(diǎn)
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                //如果不是直接進(jìn)行鏈表連接
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)設(shè)置為新的實(shí)體節(jié)點(diǎn)
                        p.next = newNode(hash, key, value, null);
                        //如果此時的節(jié)點(diǎn)容量為7那么將鏈表轉(zhuǎn)換為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //判斷新傳入的實(shí)體和當(dāng)前綁定節(jié)點(diǎn)的子節(jié)點(diǎn)是否相同，如果相同直接退出
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //進(jìn)入這個子節(jié)點(diǎn)
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
    //修改次數(shù)
        ++modCount;
    //查看當(dāng)前容器的容量是否大于threshold ,如果大于增加數(shù)組容量為原來的一倍
        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;
    //設(shè)置當(dāng)前容器的遞增為0
        int newCap, newThr = 0;
    //此時的oldCap=0 , newThr = 0 直接else執(zhí)行
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //擴(kuò)容，將數(shù)組的容量和擴(kuò)容因子變?yōu)樵瓉淼囊槐?
            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
            //初始化容器為默認(rèn)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];
    	//初始化存儲容器數(shù)組
        table = newTab;

5.2.1 Hash數(shù)據(jù)結(jié)構(gòu)

在java中所有的數(shù)據(jù)結(jié)構(gòu)都可以使用數(shù)組和指針即引用來實(shí)現(xiàn)。而Hash也成散列，就是一個鏈表加數(shù)組實(shí)現(xiàn)。

Hash數(shù)據(jù)結(jié)構(gòu)具有無序的特征。這里的無序指的是存入順序于取出順序不一樣。

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

Hash表如何存儲數(shù)據(jù)？Hash表的每一次存儲都會先調(diào)用一個Hash函數(shù)，而這個Hash函數(shù)最后運(yùn)算的值就是所存儲數(shù)據(jù)的下標(biāo)。即當(dāng)需要查詢數(shù)據(jù)的時候，僅僅只需要調(diào)用Hash函數(shù)進(jìn)行一次計算就可以得出該數(shù)據(jù)所在的下標(biāo)。

5.2.2 HashMap中的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

下面詳細(xì)解析一下HashMap中的Hash表的實(shí)現(xiàn)

在HashMap初始化的時候，首先會給內(nèi)部的負(fù)載因子賦值為0.75，然后創(chuàng)建對象，注意此時的HashMap內(nèi)部的Node數(shù)組并沒有實(shí)例化。

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

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

containKey方法的實(shí)現(xiàn)，就是直接通過hash方法計算出哈希值，然后通過&運(yùn)算，獲取數(shù)組下標(biāo)，判斷這個下標(biāo)是否為該值，如果不是，則進(jìn)行遍歷鏈表或者紅黑樹。

containeValue方法實(shí)現(xiàn)，一級一級遍歷時間復(fù)雜度似乎蠻高的

5.3 LinkedHashMap類

我們所知道的LinkedHashMap類可以順序的輸出用戶所輸入的數(shù)據(jù)。下面談一下他的實(shí)現(xiàn)方式

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

• 成員屬性

	// 鏈表的第一個節(jié)點(diǎn)，LinkedHashMap會保存鏈表的最后一個節(jié)點(diǎn)的屬性，以方便進(jìn)行節(jié)點(diǎn)添加
    transient LinkedHashMap.Entry head;

  	// 鏈表的最后一個節(jié)點(diǎn)
    transient LinkedHashMap.Entry tail;

• 創(chuàng)建對象了

//老方法，new個對象再說（單身狗的吶喊）
public LinkedHashMap() {
        super();
        accessOrder = false;
    }
//直接調(diào)用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中調(diào)用了
    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) {
        //獲取最后一個節(jié)點(diǎn)
        LinkedHashMap.Entry last = tail;
        //將最后一個節(jié)點(diǎn)定義為新增的節(jié)點(diǎn)
        tail = p;
        //如果等于null那么說明之前沒有元素
        if (last == null)
            head = p;
        else {
            //如果有，將這個元素的上一個節(jié)點(diǎn)定義為之前的最后一個元素
            p.before = last;
            //最后一個節(jié)點(diǎn)的下一個元素定義為新元素
            last.after = p;
        }
    }

//判斷這個新的節(jié)點(diǎn)是否為最后一個節(jié)點(diǎn)，如果不是移動該節(jié)點(diǎn)到最后
void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
    		//查看當(dāng)前最后一個節(jié)點(diǎn)是否為當(dāng)前新增的元素
        if (accessOrder && (last = tail) != e) {
            //p為當(dāng)前元素，a為下一個元素，b為上一個元素
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            //將p的下一個元素定義為null，切斷和之前元素的聯(lián)系
            p.after = null;
            //如果上一個元素為null ，則說明將該節(jié)點(diǎn)的下一個節(jié)點(diǎn)賦值為頭結(jié)點(diǎn)
            if (b == null)
                head = a;
            else
                //否則，將上一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)定義為a，到此，這個新的節(jié)點(diǎn)已經(jīng)被獨(dú)立出來了
                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;
        }
    }

//永遠(yuǎn)不起作用removeEldestEntry方法永遠(yuǎn)返回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類

• 底層實(shí)現(xiàn)：紅黑樹

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

• 實(shí)現(xiàn)了Cloneable接口，可被克隆

• 自然排序

5.4.1TreeMap創(chuàng)建源碼分析

• TreeMap定義的字段

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

//節(jié)點(diǎn)實(shí)體
static final class Entry implements Map.Entry {
        K key;
        V value;
        Entry left;
        Entry right;
        Entry parent;
    //默認(rèn)顏色為黑色
        boolean color = BLACK;
}

• 創(chuàng)建對象

public TreeMap() {
    //默認(rèn)構(gòu)造器
        comparator = null;
    }
public TreeMap(Comparator comparator) {
    //傳入自定義的構(gòu)造器
        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
			//創(chuàng)建根節(jié)點(diǎn)
            root = new Entry<>(key, value, null);
            size = 1;//設(shè)置節(jié)點(diǎn)數(shù)量
            modCount++;//修改次數(shù)增加
            return null;
        }
     	//定義比較值
        int cmp;
        Entry parent;
        // split comparator and comparable paths
        Comparator cpr = comparator;
     //如果此時存在自定義比較器，根據(jù)比較器規(guī)則進(jìn)行二分比較
        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 {
            //使用默認(rèn)的比較器，查找方法一樣
            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);
        }
     //沒有當(dāng)前節(jié)點(diǎn)，則創(chuàng)建該元素的實(shí)體節(jié)點(diǎn)
        Entry e = new Entry<>(key, value, parent);
     //根據(jù)比較器規(guī)則，添加節(jié)點(diǎn)
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
     //紅黑樹自動平衡算法
        fixAfterInsertion(e);
     //節(jié)點(diǎn)數(shù)量，修改數(shù)量遞增
        size++;
        modCount++;
        return null;
    }

5.4.2 TreeMap對象增加的過程

創(chuàng)建一個TreeMap，此時可以傳入一個比較器，如果不傳入按照默認(rèn)的自然順序進(jìn)行比較。

put對象，首先，檢查該root節(jié)點(diǎn)是否為null，如果為null，檢查當(dāng)前傳入key是否為null，不為null，則直接創(chuàng)建一個root節(jié)點(diǎn)。如果當(dāng)前root節(jié)點(diǎn)有值，則通過二分查找，尋找當(dāng)前可以進(jìn)行添加的父節(jié)點(diǎn)，找到以后按照比較器規(guī)則進(jìn)行添加。

添加以后，紅黑樹進(jìn)行自動平衡實(shí)現(xiàn)。

5.5 HashTable類

HashTable也是基于哈希表實(shí)現(xiàn)，和HashMap不同的是HashTable是線程安全的。

• 底層實(shí)現(xiàn)：哈希表+鏈表

 private transient Entry[] table;//存儲數(shù)組
 private transient int count;//容器中數(shù)據(jù)多少
private int threshold;//容器容量達(dá)到次數(shù)以后進(jìn)行修改
private transient int modCount = 0;//修改次數(shù)

• Hash函數(shù)

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

• 初始化。在構(gòu)造方法中初始化。初始化指為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函數(shù)計算一個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;
    }
//增加實(shí)體
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的區(qū)別

5.6 Properties類

• Java配置文件中用的居多

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

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

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