疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

java集合类源码分析之Set


 

 
Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet。值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下:
 
Set集合中的元素不能重复,即元素唯一
HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象
TreeSet按元素的大小存储,所以是有序的,并且不允许null对象
Set集合没有get方法,所以只能通过迭代器(Iterator)来遍历元素,不能随机访问
1.HashSet
 
下面给出HashSet的部分源码,以理解它的实现方式。
 
复制代码
1     static final long serialVersionUID = -5024744406713321676L;
3     private transient HashMap<E,Object> map;
5     // Dummy value to associate with an Object in the backing Map
6     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<? extends E> 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方法实现)
 
1         Set<String> hashSet = new HashSet<String>();
2         hashSet.add("D");
3         hashSet.add("B");
4         hashSet.add("C");
5         hashSet.add("A");
查找元素
1.contains(Object o) 判断集合中是否包含指定的元素(调用HashMap的containsKey方法实现)
 
1     public boolean contains(Object o) {
2         return map.containsKey(o);
3     }
2.由于HashSet的实现类中没有get方法,所以只能通过迭代器依次遍历,而不能随机访问(调用HashMap中keySet的迭代器实现)
 
1     public Iterator<E> iterator() {
2         return map.keySet().iterator();
3     }
应用示例:
 
 
复制代码
1         Set<String> hashSet = new HashSet<String>();
2         hashSet.add("D");
3         hashSet.add("B");
4         hashSet.add("C");
5         hashSet.add("A");
6         for (Iterator iterator = hashSet.iterator(); iterator.hasNext();) {
7             String string = (String) iterator.next();
8             System.out.print(string+" ");
9         }//D A B C 
复制代码
修改元素
由于HashMap中的key值不能修改,所以HashSet不能进行修改元素的操作
 
删除元素
1.remove(Object o) 删除指定元素(调用HashMap中的remove方法实现,返回值为true或者false)
 
1     public boolean remove(Object o) {
2         return map.remove(o)==PRESENT;
3     }
2.clear() 清空元素(调用HashMap中的clear方法实现,没有返回值)
 
 
1     public void clear() {
2         map.clear();
3     }
 
 
2.TreeSet
 
 TreeSet是SortedSet接口的唯一实现类。前面说过,TreeSet没有自己的数据结构而是通过TreeMap实现的,所以TreeSet也是基于红黑二叉树的一种存储结构,所以TreeSet不允许null对象,并且是有序存储的(默认升序)。
 
1     private transient NavigableMap<E,Object> m;
3     // Dummy value to associate with an Object in the backing Map
4     private static final Object PRESENT = new Object();
上述源代码中的NavigableMap是继承自SrotedMap的一个接口,其实现类为TreeMap,因此TreeSet中的数据是通过TreeMap来存储的,此处的PRESENT也是没有实际意义的虚拟值。
 
下面从源代码的角度来理解HashSet的基本用法:
 
构造器(四种)
1.TreeSet() 空的构造器,初始化一个空的TreeMap,默认升序排列
 
2.TreeSet(Comparator<? super E> comparator) 传入一个自定义的比较器,常常用于实现降序排列
3.TreeSet(Collection<? extends E> c) 传入一个子集c,用于初始化TreeMap对象,默认升序
 
4.TreeSet(SortedSet<E> s) 传入一个有序的子集s,用于初始化TreeMap对象,采用子集的比较器
 
复制代码
 1     public TreeSet() {
 2         this(new TreeMap<E,Object>());
 3     }
 4 
 5     public TreeSet(Comparator<? super E> comparator) {
 6         this(new TreeMap<>(comparator));
 7     }
 8 
 9     public TreeSet(Collection<? extends E> c) {
10         this();
11         addAll(c);
12     }
13 
14     public TreeSet(SortedSet<E> s) {
15         this(s.comparator());
16         addAll(s);
17     }
复制代码
 应用示例:
 
 
复制代码
 1         //自定义一个比较器,实现降序排列
 2         Set<Integer> treeSet = new TreeSet<Integer>(new Comparator<Integer>() {
 3 
 4             @Override
 5             public int compare(Integer o1, Integer o2) {
 6 //                return 0;        //默认升序
 7                 return o2.compareTo(o1);//降序
 8             }
 9         });
10         treeSet.add(200);
11         treeSet.add(120);
12         treeSet.add(150);
13         treeSet.add(110);
14         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
15             Integer integer = (Integer) iterator.next();
16             System.out.print(integer+" ");
17         }    //200 150 120 110 
复制代码
 
复制代码
 1         ArrayList<Integer> list = new ArrayList<Integer>();
 2         list.add(300);
 3         list.add(120);
 4         list.add(100);
 5         list.add(150);
 6         System.out.println(list); //[300, 120, 100, 150]
 7         
 8         //传入一个子集,默认升序排列
 9         TreeSet<Integer> treeSet = new TreeSet<Integer>(list);
10         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
11             Integer integer = (Integer) iterator.next();
12             System.out.print(integer+" ");
13         }//100 120 150 300 
复制代码
 
复制代码
 1         /*
 2          * 传入一个有序的子集,采用子集的比较器
 3          *     注意子集的类型必须是SortedSet及其子类或者实现类,否则将采用默认的比较器
 4          *     所以此处subSet的类型也可以是TreeSet。
 5          */
 6         
 7         SortedSet<Integer> subSet = new TreeSet<Integer>(new Comparator<Integer>() {
 8 
 9             @Override
10             public int compare(Integer o1, Integer o2) {
11 //                return 0;        //默认升序
12                 return o2.compareTo(o1);//降序
13             }
14         });
15         subSet.add(200);
16         subSet.add(120);
17         subSet.add(150);
18         subSet.add(110);
19         for (Iterator iterator = subSet.iterator(); iterator.hasNext();) {
20             Integer integer = (Integer) iterator.next();
21             System.out.print(integer+" ");
22         }    //200 150 120 110 
23         
24         System.out.println();
25         Set<Integer> treeSet = new TreeSet<Integer>(subSet);
26         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
27             Integer integer = (Integer) iterator.next();
28             System.out.print(integer+" ");
29         }//200 150 120 110 
30         
31         System.out.println();
32         treeSet.add(500);
33         treeSet.add(100);
34         treeSet.add(105);
35         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
36             Integer integer = (Integer) iterator.next();
37             System.out.print(integer+" ");
38         }//500 200 150 120 110 105 100 
复制代码
 插入元素
 1.add(E e) 插入指定的元素(调用TreeMap的put方法实现)
 
2.addAll(Collection<? extends E> c) 插入一个子集c
 
复制代码
 1         ArrayList<Integer> list = new ArrayList<Integer>();
 2         list.add(300);
 3         list.add(120);
 4         list.add(100);
 5         list.add(150);
 6         System.out.println(list); //[300, 120, 100, 150]
 7         
 8         Set<Integer> treeSet  = new TreeSet<Integer>();
 9         
10         //插入一个子集,默认升序
11         treeSet.addAll(list);
12         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
13             Integer integer = (Integer) iterator.next();
14             System.out.print(integer+" ");
15         }//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)
 
1     public boolean remove(Object o) {
2         return m.remove(o)==PRESENT;
3     }
2.clear() 清空元素(调用TreeMap中的clear方法实现,无返回值)
 
1     public void clear() {
2         m.clear();
3     }
应用示例:
 
复制代码
 1         ArrayList<Integer> list = new ArrayList<Integer>();
 2         list.add(300);
 3         list.add(120);
 4         list.add(100);
 5         list.add(150);
 6         System.out.println(list); //[300, 120, 100, 150]
 7         
 8         Set<Integer> treeSet  = new TreeSet<Integer>();
 9         
10         //插入一个子集,默认升序
11         treeSet.addAll(list);
12         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
13             Integer integer = (Integer) iterator.next();
14             System.out.print(integer+" ");
15         }//100 120 150 300 
16         
17         System.out.println(treeSet.remove(100));//true
18         for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
19             Integer integer = (Integer) iterator.next();
20             System.out.print(integer+" ");
21         }//120 150 300 
22         
23         treeSet.clear();
24         System.out.println(treeSet.size());//0
复制代码
 
 
至此,HashSet和TreeSet的存储结构及基本用法介绍完毕。