Java集合框架之Set，Map

大家好，我是Morning，在CSDN寫文，分享一些Java基礎知識，一些自己認為在學習程序中比較重要的東西，致力于幫助初學者入門，希望可以幫助你進步，感興趣的歡迎關注博主，和博主一起學習Java知識，大家還可以去專欄查看之前的文章，希望未來能和大家共同探討技術，

Set介面

set介面等同于Collection介面，不過其方法的行為有更嚴謹的定義，set的add方法不允許增加重復的元素，要適當地定義set的equals方法：只要倆個set包含同樣的元素就認為它們是相同的，而不要求這些元素有相同的順序，hashCode方法的定義要保證包含相同元素的倆個set會得到相同的散列碼，
——Java核心技術 卷一

public interface Set<E> extends Collection<E> {
    //一些方法
}

set不允許包含相同的元素，如果呼叫 add 方法來添加倆個相同的元素，那么在添加第二個元素時就會回傳 false，這個介面有倆個比較常用的實作類：HashSet，TreeSet，HashSet是一個沒有重復元素的一個無序集合，而TreeSet是一個有序集，

HashSet

HashSet 使用陣列和鏈表來實作散串列，不同 hashcode 的值存放在不同陣列下標的位置，相同 hashcode 的值存放在相同陣列下標的鏈表上的不同位置上，

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    //一些方法
}

HashSet類中有四個構造方法：

public HashSet()   //構造一個空的散列集
public HashSet(Collection<? extends E> c) //構造一個散列集，并將集合中的所有元素添加到這個散列集中
public HashSet(int initialCapacity, float loadFactor) //構造一個有指定容量和裝填因子的空散列集
public HashSet(int initialCapacity)  //構造一個指定容量的空散列集

現在讓我們來看一下add方法的原始碼：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以看到這里面是呼叫了 map.put() 方法，map 在HashSet中的宣告如下：

private transient HashMap<E,Object> map;

由此可見HashSet和HashMap有很緊密的聯系，

HashSet的底層是用一個HashMap來實作的，HashSet再添加時如何擴容問題在下文HashMap中再詳細介紹，

散串列

Java中，散串列用鏈表，陣列實作，也就可以這么理解，在陣列不同索引位置上放的是一個鏈表，要想查找表中物件的位置，要先計算它的散列碼，然后與陣列長度取余，所得到的結果就是保存這個元素的索引，在保存物件時，通過這個計算方式得到了索引位置，如果這個位置沒有其他元素，那就將元素直接插入到該位置就好了，如果這個位置已經有其他元素了，那么需要將這個新的物件與已有的物件進行比較，查看這個物件是否已經存在，如果不存在就在鏈表的末尾存盤這個物件，

TreeSet

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable{
    //一些方法
}

樹集是一個有序集合，可以以任意順序將元素插入集合中，

TreeSet排序是用一個紅黑樹完成的，每次將一個元素添加到樹中時，都會將其放置到正確的排序位置上，由于樹集時有序的，所以將一個元素添加到樹中要比添加到散串列中慢，所以如果不需要資料是有序的，就沒必要為了排序而影響性能，

它也有四個建構式：

public TreeSet()  //構造一個空的樹集，排序方式是自然排序
public TreeSet(Comparator<? super E> comparator)  //構造一個空樹集，指定比較器，就是排序方式
public TreeSet(Collection<? extends E> c)   //構造一個樹集，并將集合中的所有元素添加到這個樹集中
public TreeSet(SortedSet<E> s)     //構造一個樹集，并增加一個集合或者有序集中的所有元素，如果是有序集的話，要使用同樣的順序，

上面提到的自然排序是用元素的 compareTo() 方法來比較元素的大小關系（比如你存入v,b,a，就會輸出a,b,v），然后將集合元素按照升序排列，

Map介面

集是一個集合，允許你快速的查找現有的元素，但是要查找一個元素，需要有所要查找的那個元素的準確副本，這不是一種常見的查找方式，通常，我們知道某些關鍵資訊，希望查找與之關聯的元素，映射（map）資料結構就是為此設計的，映射用來存放鍵 / 值對，如果提供了鍵，就可以查找到值，
——Java核心技術

public interface Map<K,V> {
	int size();  //回傳映射中的元素數
    V get(Object key);  //回傳指定鍵對應的值
    V remove(Object key); //從映射中洗掉指定鍵對應的元素，
}

Java為映射提供了倆個通用的實作：HashMap和TreeMap

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
}

實作了Map介面，存盤的內容是鍵值對(key-value)映射，將鍵進行散列，散列或比較函式只應用于鍵，與鍵相關的值不進行散列或比較，

HashMap底層的結構是，散串列（陣列和鏈表）和紅黑樹

我用反射的方式輸出了這個map的容量，可以看到如果使用無參的構造方法，那么map的容量默認為16，我們也可以通過傳參的方式，來指定它的容量，值的一提的是，你指定的容量，一定要為 2 的冪次方，且要小于 int 范圍內最大的 2 的冪次方數（1073741824），

//指定容量
HashMap<String,String> map = new HashMap<String, String>(8);

這個構造方法還是呼叫了下面的這個構造方法，只是把默認的負載因子值傳進去了：

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//呼叫這個構造方法
public HashMap(int initialCapacity, float loadFactor) {
    //判斷是否小于0，拋出例外
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //判斷是否大于最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //判斷負載因子的合法性
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;  //更新負載因子的值
    //判斷需要擴容的臨界值
    this.threshold = tableSizeFor(initialCapacity);
}

put方法，直接看原始碼：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

呼叫put方法后，會根據鍵值來計算一個值（位置），然后呼叫putVal來存放元素，

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //hash表為慷訓者長度為0的話，創建hash表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//resize()HashMap擴容的方法
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果位置上沒有元素，就加進去，成為鏈表的頭結點
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果這個值的型別為樹結構的話，就直接添加到樹中，不會判斷是否超過8
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //binCount鏈表的長度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果鏈表不為空，就往下一個節點添加
                    p.next = newNode(hash, key, value, null);
                    //如果這個鏈表的長度大于8，就會轉為紅黑樹存盤
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        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;
}

通過代碼中的注釋，相信你已經初步了解了 put 方法，總的來說就是添加時首先是用 k 通過哈希函式計算位置，位置上如果沒有元素添加在鏈表的頭結點，如果有插入到鏈表的下一個節點，當鏈表的長度為大于等于8時，轉為紅黑樹存盤，如果該鍵已經有映射關系的話，用這次的值覆寫掉之前的值，最后判斷要不要擴容，如果要擴容，會擴容為原來容量的2倍，這樣效率會高一些，也可以減少哈希沖突，

負載因子

上文中我們提到了負載因子，那么負載因子是什么呢？

負載因子也叫裝填因子，是一個0.0~1.0之間的數，確定散串列填充的百分比，當大于這個百分比時，散串列進行再散列，在map中，也就是說，當put的元素數量超過一定值的時候，就會擴容，這個值就是負載因子*容量，

HashMap中的負載因子默認是0.75：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

就是說如果map中的元素超過容量的3/4就要進行擴容，

那么為什么這里要默認為0.75呢？這了也是規定了一個相對合理的值，如果為 1 的話效率太低，滿了之后才擴容；如果為0.5的話，浪費空間，所以選了一個居中的值，

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
    
}

它沒有實作Map介面是因為AbstractMap實作了Map介面，TreeMap是一個能比較元素大小的Map集合，可以對 key 值進行大小排序，其中，可以使用自然順序，也可以使用集合中自定義的比較器來進行排序，底層是紅黑樹結構，

TreeMap中運用到的紅黑樹結構，是資料結構的一種，相關知識太多，大家感興趣的話可以在網上查閱資料（博主對樹結構的理解不是很透徹😢😢），

好了，本次的分享到這里就結束了，博主會在日后給大家分享其他的知識，和大家一起探討，有興趣的可以關注博主，文中有什么不當的地方，歡迎大家在評論區指出，大家一起探討、學習，🤞🤞🤞

參考書籍：Java核心技術 卷一（第11版）