Set接口

set接口等同于Collection接口，不過(guò)其方法的行為有更嚴(yán)謹(jǐn)?shù)亩x。set的add方法不允許增加重復(fù)的元素。要適當(dāng)?shù)囟xset的equals方法：只要倆個(gè)set包含同樣的元素就認(rèn)為它們是相同的，而不要求這些元素有相同的順序。hashCode方法的定義要保證包含相同元素的倆個(gè)set會(huì)得到相同的散列碼。
——Java核心技術(shù) 卷一

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

set不允許包含相同的元素，如果調(diào)用 add 方法來(lái)添加倆個(gè)相同的元素，那么在添加第二個(gè)元素時(shí)就會(huì)返回 false。這個(gè)接口有倆個(gè)比較常用的實(shí)現(xiàn)類：HashSet，TreeSet。HashSet是一個(gè)沒(méi)有重復(fù)元素的一個(gè)無(wú)序集合，而TreeSet是一個(gè)有序集。

HashSet

HashSet 使用數(shù)組和鏈表來(lái)實(shí)現(xiàn)散列表，不同 hashcode 的值存放在不同數(shù)組下標(biāo)的位置，相同 hashcode 的值存放在相同數(shù)組下標(biāo)的鏈表上的不同位置上。

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

HashSet類中有四個(gè)構(gòu)造方法：

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

現(xiàn)在讓我們來(lái)看一下add方法的源碼：

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

可以看到這里面是調(diào)用了 map.put() 方法，map 在HashSet中的聲明如下：

private transient HashMap<E,Object> map;

由此可見HashSet和HashMap有很緊密的聯(lián)系。

HashSet的底層是用一個(gè)HashMap來(lái)實(shí)現(xiàn)的。HashSet再添加時(shí)如何擴(kuò)容問(wèn)題在下文HashMap中再詳細(xì)介紹。

散列表

Java中，散列表用鏈表，數(shù)組實(shí)現(xiàn)。也就可以這么理解，在數(shù)組不同索引位置上放的是一個(gè)鏈表，要想查找表中對(duì)象的位置，要先計(jì)算它的散列碼，然后與數(shù)組長(zhǎng)度取余，所得到的結(jié)果就是保存這個(gè)元素的索引。在保存對(duì)象時(shí)，通過(guò)這個(gè)計(jì)算方式得到了索引位置，如果這個(gè)位置沒(méi)有其他元素，那就將元素直接插入到該位置就好了，如果這個(gè)位置已經(jīng)有其他元素了，那么需要將這個(gè)新的對(duì)象與已有的對(duì)象進(jìn)行比較，查看這個(gè)對(duì)象是否已經(jīng)存在。如果不存在就在鏈表的末尾存儲(chǔ)這個(gè)對(duì)象。

TreeSet

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

樹集是一個(gè)有序集合，可以以任意順序?qū)⒃夭迦爰现小?/p>

TreeSet排序是用一個(gè)紅黑樹完成的，每次將一個(gè)元素添加到樹中時(shí)，都會(huì)將其放置到正確的排序位置上。由于樹集時(shí)有序的，所以將一個(gè)元素添加到樹中要比添加到散列表中慢，所以如果不需要數(shù)據(jù)是有序的，就沒(méi)必要為了排序而影響性能。

它也有四個(gè)構(gòu)造函數(shù)：

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

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

Map接口

集是一個(gè)集合，允許你快速的查找現(xiàn)有的元素。但是要查找一個(gè)元素，需要有所要查找的那個(gè)元素的準(zhǔn)確副本。這不是一種常見的查找方式。通常，我們知道某些關(guān)鍵信息，希望查找與之關(guān)聯(lián)的元素。映射（map）數(shù)據(jù)結(jié)構(gòu)就是為此設(shè)計(jì)的。映射用來(lái)存放鍵 / 值對(duì)。如果提供了鍵，就可以查找到值。
——Java核心技術(shù)

public interface Map<K,V> {
	int size();  //返回映射中的元素?cái)?shù)
    V get(Object key);  //返回指定鍵對(duì)應(yīng)的值
    V remove(Object key); //從映射中刪除指定鍵對(duì)應(yīng)的元素。
}

Java為映射提供了倆個(gè)通用的實(shí)現(xiàn)：HashMap和TreeMap

HashMap

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

實(shí)現(xiàn)了Map接口，存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射，將鍵進(jìn)行散列，散列或比較函數(shù)只應(yīng)用于鍵，與鍵相關(guān)的值不進(jìn)行散列或比較。

HashMap底層的結(jié)構(gòu)是，散列表（數(shù)組和鏈表）和紅黑樹

我用反射的方式輸出了這個(gè)map的容量，可以看到如果使用無(wú)參的構(gòu)造方法，那么map的容量默認(rèn)為16。我們也可以通過(guò)傳參的方式，來(lái)指定它的容量，值的一提的是，你指定的容量，一定要為 2 的冪次方，且要小于 int 范圍內(nèi)最大的 2 的冪次方數(shù)（1073741824）。

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

這個(gè)構(gòu)造方法還是調(diào)用了下面的這個(gè)構(gòu)造方法，只是把默認(rèn)的負(fù)載因子值傳進(jìn)去了：

put方法，直接看源碼：

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

調(diào)用put方法后，會(huì)根據(jù)鍵值來(lái)計(jì)算一個(gè)值（位置），然后調(diào)用putVal來(lái)存放元素。

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表為空或者長(zhǎng)度為0的話，創(chuàng)建hash表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//resize()HashMap擴(kuò)容的方法
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果位置上沒(méi)有元素，就加進(jìn)去，成為鏈表的頭結(jié)點(diǎn)
        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;
        //如果這個(gè)值的類型為樹結(jié)構(gòu)的話，就直接添加到樹中，不會(huì)判斷是否超過(guò)8
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //binCount鏈表的長(zhǎng)度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果鏈表不為空，就往下一個(gè)節(jié)點(diǎn)添加
                    p.next = newNode(hash, key, value, null);
                    //如果這個(gè)鏈表的長(zhǎng)度大于8，就會(huì)轉(zhuǎn)為紅黑樹存儲(chǔ)
                    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;
            }
        }
        //如果該鍵已經(jīng)有映射關(guān)系的話，用這次的值覆蓋掉之前的值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果里面的元素超過(guò) threshold 的話就擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

通過(guò)代碼中的注釋，相信你已經(jīng)初步了解了 put 方法，總的來(lái)說(shuō)就是添加時(shí)首先是用 k 通過(guò)哈希函數(shù)計(jì)算位置，位置上如果沒(méi)有元素添加在鏈表的頭結(jié)點(diǎn)，如果有插入到鏈表的下一個(gè)節(jié)點(diǎn)，當(dāng)鏈表的長(zhǎng)度為大于等于8時(shí)，轉(zhuǎn)為紅黑樹存儲(chǔ)，如果該鍵已經(jīng)有映射關(guān)系的話，用這次的值覆蓋掉之前的值，最后判斷要不要擴(kuò)容。如果要擴(kuò)容，會(huì)擴(kuò)容為原來(lái)容量的2倍。這樣效率會(huì)高一些，也可以減少哈希沖突。

負(fù)載因子

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

負(fù)載因子也叫裝填因子，是一個(gè)0.0~1.0之間的數(shù)，確定散列表填充的百分比，當(dāng)大于這個(gè)百分比時(shí)，散列表進(jìn)行再散列。在map中，也就是說(shuō)，當(dāng)put的元素?cái)?shù)量超過(guò)一定值的時(shí)候，就會(huì)擴(kuò)容，這個(gè)值就是負(fù)載因子*容量。

HashMap中的負(fù)載因子默認(rèn)是0.75：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

就是說(shuō)如果map中的元素超過(guò)容量的3/4就要進(jìn)行擴(kuò)容。

那么為什么這里要默認(rèn)為0.75呢？這了也是規(guī)定了一個(gè)相對(duì)合理的值，如果為 1 的話效率太低，滿了之后才擴(kuò)容；如果為0.5的話，浪費(fèi)空間。所以選了一個(gè)居中的值。

TreeMap

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

它沒(méi)有實(shí)現(xiàn)Map接口是因?yàn)锳bstractMap實(shí)現(xiàn)了Map接口，TreeMap是一個(gè)能比較元素大小的Map集合，可以對(duì) key 值進(jìn)行大小排序。其中，可以使用自然順序，也可以使用集合中自定義的比較器來(lái)進(jìn)行排序。底層是紅黑樹結(jié)構(gòu)。

TreeMap中運(yùn)用到的紅黑樹結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)的一種，相關(guān)知識(shí)太多，大家感興趣的話可以在網(wǎng)上查閱資料（博主對(duì)樹結(jié)構(gòu)的理解不是很透徹????）。

到此這篇關(guān)于Java集合框架之Set和Map詳解的文章就介紹到這了,更多相關(guān)Java集合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論