文章目錄

Set接口
HashSet
- HashSet的使用&周遊
- 源碼淺析
- - 構造函數
  - HashSet常用方法
  - 周遊
LinkedHashSet
- LinkedHashSet的使用&周遊
- 源碼淺析
TreeSet
- TreeSet的使用&周遊
總結
參考

Set接口

整體Collection&Map的實作關系：

Java Collection系列之：HashSet、LinkedHashSet、TreeSet的使用及源碼解析Set接口HashSetLinkedHashSetTreeSet總結參考

public interface Set<E> extends Collection<E> {
  
  int size();

  boolean isEmpty();

  boolean contains(Object o);

  Iterator<E> iterator();

  Object[] toArray();

  <T> T[] toArray(T[] a);

  boolean add(E e);

  boolean remove(Object o);

  boolean containsAll(Collection<?> c);

  boolean addAll(Collection<? extends E> c);

  boolean retainAll(Collection<?> c);

  boolean removeAll(Collection<?> c);

  void clear();

  boolean equals(Object o);

  int hashCode();

  @Override
  default Spliterator<E> spliterator() {
      return Spliterators.spliterator(this, Spliterator.DISTINCT);
   }

}

HashSet

HashSet基于key-value形式儲存元素，底層是基于HashMap實作的

(預設容量是16 負載因子是0.75)

，HashSet的相關操作基本都是調用HashMap來完成的，Hashset存儲元素具有無序、不可重複的特點。

無序: 因為底層資料結構是HashMap并且利用HashMap去存儲元素，是以HashSet存儲的元素也是無序的。
不可重複：HashSet#add添加元素時，底層利用HashMap将添加的元素當成HashMap中的key,并建立一個預設值PRESENT(Object類型,final修飾不可修改)當做HashMap中的value，利用HashMap中key值相等會覆寫的特點，進而實作HashSet不能存儲重複元素(當添加元素不重複時，HashSet#add方法添加成功并傳回true；如果添加的元素重複，則添加失敗，并傳回false)。

HashSet的使用&周遊

Set<String> hashSet = new HashSet<>();
hashSet.add("A");
hashSet.add("C");
hashSet.add("B");
hashSet.add("D");
hashSet.add("A");

System.out.println("使用for循環周遊：");
for (String str : hashSet) {
    System.out.println("元素：" + str);
}

System.out.println("-------------");

System.out.println("使用Iterator循環周遊：");
Iterator<String> iterator = hashSet.iterator();
while (iterator.hasNext()) {
    System.out.println("元素：" + iterator.next());
}

執行結果：

元素：A
元素：B
元素：C
元素：D

-------------

使用Iterator循環周遊：
元素：A
元素：B
元素：C
元素：D

我們往HashSet中添加了2次"A"元素，通過結果發現并沒有存儲2個"A"，并且元素存儲順序并不是按添加順序排序的。是以HashSet存儲的是無序、不可重複的元素。

源碼淺析

構造函數

//預設無參構造函數 内部初始化一個HashMap  預設容量是16 負載因子0.75
public HashSet() {
    map = new HashMap<>();
}

//構造一個包含指定collection的set
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

//構造一個指定容量和負載因子的HashSet
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

//構造函數中指定容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

//構造函數僅能在包内通路 此構造函數是為了支援LinkedHashSet的初始化
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet常用方法

//hashSet中元素個數
public int size() {
    return map.size();
}
//是否為空 為空傳回true 不為空傳回false
public boolean isEmpty() {
    return map.isEmpty();
}
//hashSet中是否包含元素o，包含傳回true；不包含傳回false
public boolean contains(Object o) {
    return map.containsKey(o);
}
//添加元素到hashSet中 成功傳回true 失敗傳回false
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
//删除hashSet中的元素 成功傳回true 失敗傳回false
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
//清空hashSet中的元素
public void clear() {
    map.clear();
}
//拷貝副本
@SuppressWarnings("unchecked")
public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

周遊

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

可以看到調用的是HashMap#keySet方法，是以也證明了上面的結論：Hashset中的元素時儲存在HashMap中的key中，具有無序、不可重複的特點；value 則是使用的 PRESENT對象，該對象被static final修飾，不可更改。

LinkedHashSet

LinkedHashSet繼承于HashSet,是以存放的元素不可重複；又因為底層是通過LinkedHashMap(内部維護一個雙向連結清單)實作的，是以LinkedHashSet可以按順序周遊(按插入順序排序)。

LinkedHashSet的使用&周遊

LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("A");
linkedHashSet.add("C");
linkedHashSet.add("B");
linkedHashSet.add("D");
linkedHashSet.add("A");

for (String s : linkedHashSet) {
    System.out.println("value is " + s);
}

System.out.println("-------------");

Iterator<String> iterator = linkedHashSet.iterator();
while (iterator.hasNext()) {
    System.out.println("value is " + iterator.next());
}

執行結果：

value is A
value is C
value is B
value is D
-------------
value is A
value is C
value is B
value is D

添加元素時，分别在第一次和最後一次嘗試添加元素"A"，通過結果看隻有第一次添加成功。通過結果可以看到LinkedHashSet可以按插入順序周遊元素，并且存儲的元素是不能重複的。

源碼淺析

LinkedHashSet的源碼很簡單：

public class LinkedHashSet<E> extends HashSet<E>
              implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

隻有幾個構造參數并通過super調用了父類的構造函數，還記得父類HashSet中的那個構造函數:

//HashSet構造函數
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

這個構造函數就是供LinkedHashSet構造函數調用super時被調用的，是以LinkedHashSet内部就是通過LinkedHashMap及父類HashSet實作的，LinkedHashSet存儲的是有序、不可重複的元素。

TreeSet

TreeSet内部是通過TreeMap(紅黑樹)實作的，因為TreeMap可以按自然順序或自定義順序排序，是以TreeSet同樣可以對元素進行排序存儲。

TreeSet的使用&周遊

按自然順序排序：

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("A");
treeSet.add("C");
treeSet.add("B");
treeSet.add("D");
treeSet.add("A");

for (String s : treeSet) {
    System.out.println("value is " + s);
}

System.out.println("-------------");

Iterator<String> iterator = treeSet.iterator();
while (iterator.hasNext()) {
    System.out.println("value is " + iterator.next());
}

執行結果:

value is A
value is B
value is C
value is D
-------------
value is A
value is B
value is C
value is D

放入的元素是String類型，内部實作了Comparable接口，TreeSet對元素進行了排序并且放入的元素時不能重複。

自定義排序：

Person person1 = new Person("張三", 10);
Person person2 = new Person("李四", 30);
Person person3 = new Person("王五", 20);
Person person4 = new Person("趙六", 10);

TreeSet<Person> treeSet = new TreeSet<>();
treeSet.add(person1);
treeSet.add(person2);
treeSet.add(person3);
treeSet.add(person4);

for (Person person : treeSet) {
    System.out.println("value is " + person);
}

System.out.println("-------------");

Iterator<Person> iterator = treeSet.iterator();
while (iterator.hasNext()) {
    System.out.println("value is " + iterator.next());
}



static class Person implements Comparable<Person> {

    private String Name;
    private int age;

    Person(String name, int age) {
        this.Name = name;
        this.age = age;
    }

    public String getName() {
        return Name;
    }

    public void setName(String name) {
        Name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person o) {
        if (age >= o.getAge()) {
            //年齡大的或相等的元素放在後面
            return 1;
        }
        return -1;
    }

    @Override
    public String toString() {
        return "[person(name:" + getName() + ",age:" + getAge() + ")]";
    }
}

執行結果：

value is [person(name:張三,age:10)]
value is [person(name:趙六,age:10)]
value is [person(name:王五,age:20)]
value is [person(name:李四,age:30)]
-------------
value is [person(name:張三,age:10)]
value is [person(name:趙六,age:10)]
value is [person(name:王五,age:20)]
value is [person(name:李四,age:30)]

TreeSet放入的是Person類型，在Person類中實作了Comparable接口并重寫其中的compareTo方法，在compareTo方法中根據age進行排序，age大的放在後面，是以最後周遊的結果可以看到age是從小到大輸出的。

總結

HashSet内部幾乎都是通過HashMap實作的，LinkedHashSet内部是通過LinkedHashMap實作的，TreeSet内部是通過TreeMap實作的；
HashSet存儲無序、不可重複元素；LinkedHashSet存儲有序(按插入順序排序)、不可重複元素；TreeSet内部是TreeMap(紅黑樹)，内部元素可以按自然順序或自定義順序排序。

參考

【1】https://wiki.jikexueyuan.com/project/java-enhancement/java-twentyfour.html

【2】TreeSet: https://wiki.jikexueyuan.com/project/java-enhancement/java-twentyeight.html

【3】TreeSet: https://www.cnblogs.com/skywang12345/p/3311268.html

Java Collection系列之：HashSet、LinkedHashSet、TreeSet的使用及源碼解析Set接口HashSetLinkedHashSetTreeSet總結參考

文章目錄

Set接口

HashSet

HashSet的使用&周遊

源碼淺析

構造函數

HashSet常用方法

周遊

LinkedHashSet

LinkedHashSet的使用&周遊

源碼淺析

TreeSet

TreeSet的使用&周遊

總結

參考

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]