set集合框架體系圖

set集合介紹

Set接口繼承了Collection接口,含有許多常用的方法。

int size();返回集合的長(zhǎng)度
boolean isEmpty();判斷集合是否為空
boolean contains(Object o);是否包含某個(gè)值
boolean add(E e);添加元素
boolean remove(Object o);刪除元素

Set接口的存儲(chǔ)特點(diǎn)是無(wú)序不可重復(fù)，可以存放唯一一個(gè)null值，Set的常用實(shí)現(xiàn)類(lèi)有HashSet，TreeSet。

Set集合的遍歷方式有三種

1.直接打印System.out.println(set);

2.增強(qiáng)for循環(huán)遍歷

3.迭代器遍歷

Set集合的實(shí)現(xiàn)類(lèi)

HashSet

1.HashSet實(shí)現(xiàn)了Cloneable, Serializable兩個(gè)接口。

Cloneable:實(shí)現(xiàn)了clone（）方法可以實(shí)現(xiàn)克隆功能
Serializable：表示可以被序列化傳輸。

2.HashSet的底層結(jié)構(gòu)

HashSet的底層是通過(guò)HashMap實(shí)現(xiàn)

HashMap是通過(guò)數(shù)組加鏈表加紅黑樹(shù)實(shí)現(xiàn)的。

(1)add()方法

調(diào)用Map集合中的put方法。

將要添加的元素作為Map集合中的key，PRESENT作為Map集合中的Value;

PERSENT的值為new Object( );

HashCode相同會(huì)發(fā)生什么?

產(chǎn)生hash碰撞，hash碼相同，則通過(guò)key的equals()方法比較值是否相同.

key值不相等：則會(huì)在該節(jié)點(diǎn)的鏈表結(jié)構(gòu)上新增一個(gè)節(jié)點(diǎn)(如果鏈表長(zhǎng)度>=8且 數(shù)組節(jié)點(diǎn)數(shù)>=64 鏈表結(jié)構(gòu)就會(huì)轉(zhuǎn)換成紅黑樹(shù))

key值相等：則用新的value替換舊的value

(2)remove()方法

也調(diào)用的是Map集合中的remove方法

(3)contains()方法

由此可見(jiàn)HashSet的底層是借助與HashMap實(shí)現(xiàn)的，底層的初始化原理，擴(kuò)容原理都和HashSet集合相同·

3.HashSet的去重原理

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
             //如果Hash相同并且數(shù)值相同直接替換即可
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //如果p是一個(gè)紅黑樹(shù)結(jié)點(diǎn)
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
                        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;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

TreeSet

1.TreeSet是一個(gè)有序的集合，它的作用是提供有序的Set集合。它繼承了AbstractSet抽象類(lèi)，實(shí)現(xiàn)了NavigableSet，Cloneable，Serializable接。它是非線(xiàn)程安全的，TreeSet是基于TreeMap實(shí)現(xiàn)的

TreeMap是通過(guò)紅黑樹(shù)實(shí)現(xiàn)的

2.TreeSet的基本使用

如果我們像使用HashSet一樣使用TreeSet這樣是否會(huì)報(bào)錯(cuò)呢?

答案是報(bào)錯(cuò)

如何解決呢?解決辦法有兩種

解決方法一:(自然排序)、

在Student類(lèi)中實(shí)現(xiàn)Comparable接口，重寫(xiě)compareTo方法即可

解決方法二:定制排序

在創(chuàng)建TreeMap對(duì)象時(shí)，傳入一個(gè)Comparator接口，并實(shí)現(xiàn)里面的compare方法。

3.TreeSet的構(gòu)造方法

TreeSet提供了五種構(gòu)造方法。

(1)無(wú)參構(gòu)造方法，創(chuàng)建一個(gè)TreeMap類(lèi)。

public TreeSet() {
this(new TreeMap<E,Object>());
}

(2)指定TreeSet的比較器

public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}

(3)創(chuàng)建一個(gè)TreeSet,并將Collection c集合中的元素加入到TreeSet中

public TreeSet(Collection<? extends E> c) {
this();
addAll?;
}

(4)構(gòu)造一個(gè)包含相同元素并使用與指定排序集相同的順序的新樹(shù)集。

public TreeSet(SortedSet s) {
this(s.comparator());
addAll(s);
}

(5)構(gòu)造一個(gè)由指定的可導(dǎo)航地圖支持的集合。

TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}

4.TreeSet的去重方法：前面講到hashSet去重的方法是hashcode和equals方法判斷相同則覆蓋，TreeSet是通過(guò)compareTo方法的返回值來(lái)判斷是否相同，如果返回值為0則認(rèn)定是重復(fù)元素

5.TreeSet的常用方法

public boolean add(E e) {
return m.put(e, PRESENT)==null;
}`
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
public void clear() {
m.clear();
}
m為底層的HashMap集合，

LinkedHashSet

LinkedHashSet是一個(gè)哈希表和鏈表的結(jié)合，且是一個(gè)雙向鏈表

并且linkedHashSet是一個(gè)非線(xiàn)程安全的集合。如果有多個(gè)線(xiàn)程同時(shí)訪問(wèn)當(dāng)前l(fā)inkedhashset集合容器，并且有一個(gè)線(xiàn)程對(duì)當(dāng)前容器中的元素做了修改，那么必須要在外部實(shí)現(xiàn)同步保證數(shù)據(jù)的準(zhǔn)確性。

LinkedHashSet 底層使用 LinkedHashMap 來(lái)保存所有元素，它繼承與 HashSet，其所有的方法操作上又與 HashSet 相同

TreeSet和HashSet的區(qū)別

1.TreeSet 是二叉樹(shù)(紅黑樹(shù))實(shí)現(xiàn)的,Treeset中的數(shù)據(jù)是自動(dòng)排好序的，不允許放入null值。

2.HashSet 是哈希表實(shí)現(xiàn)的,HashSet中的數(shù)據(jù)是無(wú)序的，可以放入null，但只能放入一個(gè)null，兩者中的值都不能重復(fù)。

3.HashSet要求放入的對(duì)象實(shí)現(xiàn)HashCode()和equals()方法，TreeSet要求放入的對(duì)象繼承Comparable接口并實(shí)現(xiàn)compareTo方法或者在建TreeMap對(duì)象時(shí)，傳入一個(gè)Comparator接口，并實(shí)現(xiàn)里面的compare方法