首頁 > Java > java教程 > Java集合類源碼之Set的具體分析

Java集合類源碼之Set的具體分析

黄舟
發布: 2017-10-10 10:16:51
原創
1626 人瀏覽過

下面小編就為大家帶來一篇java集合類別源碼分析之Set詳解。小編覺得蠻不錯的,現在就分享給大家,也給大家做個參考。一起跟著小編過來看看吧

Set集合與List一樣,都是繼承自Collection接口,常用的實作類別有HashSet和TreeSet。值得注意的是,HashSet是透過HashMap來實現的而TreeSet是透過TreeMap來實現的,所以HashSet和TreeSet都沒有自己的資料結構,具體可以歸納如下:

•Set集合中的元素不能重複,即元素唯一

•HashSet按元素的哈希值存儲,所以是無序的,並且最多允許一個null對象

•TreeSet按元素的大小存儲,所以是有序的,且不允許null物件

•Set集合沒有get方法,所以只能透過迭代器(Iterator)來遍歷元素,不能隨機存取

##1 .HashSet

下面給出HashSet的部分原始碼,以瞭解它的實作方式。



static final long serialVersionUID = -5024744406713321676L;

 private transient HashMap<E,Object> map;

 // Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();
登入後複製

觀察源碼,我們知道HashSet的資料是儲存在HashMap的實例物件map中的,並且對應於map中的key,而Object類型的引用PRESENT則是對應於map中的value的一個虛擬值,沒有實際意義。聯想到HashMap的一些特性:無序儲存、key值唯一等等,我們就可以很自然地理解Set集合元素不能重複以及HashSet無序儲存的特性了。

下面從原始碼的角度來理解HashSet的基本用法:

•建構器(四種)

1.HashSet() 空的建構器,初始化一個空的HashMap

2.HashSet(Collection c) 傳入一個子集c,用於初始化HashMap

3.HashSet(int initialCapacity, float loadFactor) 初始化一個空的HashMap,並指定初始容量和載入因子

4.HashSet(int initialCapacity) 初始化一個空的HashMap,並指定初始容量



public HashSet() {
  map = new HashMap<>();
 }

 public HashSet(Collection<? extends E> c) {
  map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  addAll(c);
 }

 public HashSet(int initialCapacity, float loadFactor) {
  map = new HashMap<>(initialCapacity, loadFactor);
 }

 public HashSet(int initialCapacity) {
  map = new HashMap<>(initialCapacity);
 }
登入後複製

•插入元素

1.add(E e) 插入指定元素(呼叫HashMap的put方法實作)


   Set<String> hashSet = new HashSet<String>();
   hashSet.add("D");
   hashSet.add("B");
   hashSet.add("C");
   hashSet.add("A");
登入後複製

#•找出元素

1.contains(Object o) 判斷集合中是否包含指定的元素(呼叫HashMap的containsKey方法實作)


  public boolean contains(Object o) {
   return map.containsKey(o);
  }
登入後複製

2.由於HashSet的實作類別中沒有get方法,所以只能透過迭代器依序遍歷,而不能隨機存取(呼叫HashMap中keySet的迭代器實作)


  public Iterator<E> iterator() {
   return map.keySet().iterator();
  }
登入後複製

應用範例:


##

Set<String> hashSet = new HashSet<String>();
  hashSet.add("D");
  hashSet.add("B");
  hashSet.add("C");
  hashSet.add("A");
  for (Iterator iterator = hashSet.iterator(); iterator.hasNext();) {
   String string = (String) iterator.next();
   System.out.print(string+" ");
  }//D A B C
登入後複製

•修改元素

由於HashMap中的key值不能修改,所以HashSet不能進行修改元素的運算

##•刪除元素

1.remove(Object o) 刪除指定元素(呼叫HashMap中的remove方法實現,傳回值為true或false)

  public boolean remove(Object o) {
   return map.remove(o)==PRESENT;
  }
登入後複製

2. clear() 清空元素(呼叫HashMap中的clear方法實現,沒有傳回值)


public void clear() {
   map.clear();
  }
登入後複製


2.TreeSet

TreeSet是SortedSet介面的唯一實作類別。前面說過,TreeSet沒有自己的資料結構而是透過TreeMap實現的,所以TreeSet也是基於紅黑二元樹的一種儲存結構,所以TreeSet不允許null對象,並且是有序儲存的(預設升序)。

private transient NavigableMap<E,Object> m;
 
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
登入後複製

上述原始程式碼中的NavigableMap是繼承自SrotedMap的一個接口,其實作類為TreeMap,因此TreeSet中的資料是透過TreeMap來儲存的,此處的PRESENT也是沒有實際意義的虛擬值。

下面從原始碼的角度來理解HashSet的基本用法:

•建構器(四種)

1.TreeSet() 空的建構器,初始化一個空的TreeMap,預設升序排列

2.TreeSet(Comparator comparator) 傳入一個自訂的比較器,常用於實現降序排列

3.TreeSet(Collection c) 傳入一個子集c,用於初始化TreeMap對象,預設升序

4.TreeSet(SortedSet s) 傳入一個有序的子集s,用於初始化TreeMap對象,採用子集的比較器


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

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

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

 public TreeSet(SortedSet<E> s) {
  this(s.comparator());
  addAll(s);
 }
登入後複製

應用範例

//自定义一个比较器,实现降序排列
  Set<Integer> treeSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  treeSet.add(200);
  treeSet.add(120);
  treeSet.add(150);
  treeSet.add(110);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110
登入後複製


#
ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  //传入一个子集,默认升序排列
  TreeSet<Integer> treeSet = new TreeSet<Integer>(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300
登入後複製


/*
   * 传入一个有序的子集,采用子集的比较器
   *  注意子集的类型必须是SortedSet及其子类或者实现类,否则将采用默认的比较器
   *  所以此处subSet的类型也可以是TreeSet。
   */
  
  SortedSet<Integer> subSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  subSet.add(200);
  subSet.add(120);
  subSet.add(150);
  subSet.add(110);
  for (Iterator iterator = subSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110 
  
  System.out.println();
  Set<Integer> treeSet = new TreeSet<Integer>(subSet);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//200 150 120 110 
  
  System.out.println();
  treeSet.add(500);
  treeSet.add(100);
  treeSet.add(105);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//500 200 150 120 110 105 100
登入後複製

##• 插入元素

1.add(E e) 插入指定的元素(呼叫TreeMap的put方法實作)2.addAll(Collection c) 插入子集c


ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  Set<Integer> treeSet = new TreeSet<Integer>();
  
  //插入一个子集,默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300
登入後複製

•找出元素

#1.contains(Object o) 判斷集合中是否包含指定物件(呼叫TreeMap的containsKey方法實作)

2.与HashSet一样,TreeSet的实现类中没有get方法,所以只能通过迭代器依次遍历,而不能随机访问(调用TreeMap中keySet的迭代器实现)。

•修改元素

TreeSet不能进行修改元素的操作,原因与HashSet一样。

•删除元素

1.remove(Object o) 删除指定元素(调用TreeMap中的remove方法实现,返回true或者false)


  public boolean remove(Object o) {
   return m.remove(o)==PRESENT;
  }
登入後複製

2.clear() 清空元素(调用TreeMap中的clear方法实现,无返回值)


  public void clear() {
   m.clear();
  }
登入後複製

应用示例:


ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  Set<Integer> treeSet = new TreeSet<Integer>();
  
  //插入一个子集,默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300 
  
  System.out.println(treeSet.remove(100));//true
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//120 150 300 
  
  treeSet.clear();
  System.out.println(treeSet.size());//0
登入後複製

至此,HashSet和TreeSet的存储结构及基本用法介绍完毕。

以上是Java集合類源碼之Set的具體分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板