java集合类源码分析之Set详解

网友投稿 224 2023-03-27


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 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 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方法实现)

Set hashSet = new HashSethttp://();

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 iterator() {

return map.keySet().iterator();

}

应用示例:

Set hashSet = new HashSet();

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 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 super E> comparator) 传入一个自定义的比较器,常常用于实现降序排列

3.TreeSet(Collection extends E> c) 传入一个子集c,用于初始化TreeMap对象,默认升序

4.TreeSet(SortedSet s) 传入一个有序的子集s,用于初始化TreeMap对象,采用子集的比较器

public TreeSet() {

this(new TreeMap());

}

public TreeSet(Comparator super E> comparator) {

this(new TreeMap<>(comparator));

}

public TreeSet(Collection extends E> c) {

this();

addAll(c);

}

public TreeSet(SortedSet s) {

this(s.comparator());

addAll(s);

}

应用示例

//自定义一个比较器,实现降序排列

Set treeSet = new TreeSet(new Comparator() {

@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.hasNextUqpBXFHit();) {

Integer integer = (Integer) iterator.next();

System.out.print(integer+" ");

} //200 150 120 110

ArrayList list = new ArrayList();

list.add(300);

list.add(120);

list.add(100);

list.add(150);

System.out.println(list); //[300, 120, 100, 150]

//传入一个子集,默认升序排列

TreeSet treeSet = new TreeSet(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 subSet = new TreeSet(new Comparator() {

@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(http://); iterator.hasNext();) {

Integer integer = (Integer) iterator.next();

System.out.print(integer+" ");

} //200 150 120 110

System.out.println();

Set treeSet = new TreeSet(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 extends E> c) 插入一个子集c

ArrayList list = new ArrayList();

list.add(300);

list.add(120);

list.add(100);

list.add(150);

System.out.println(list); //[300, 120, 100, 150]

Set treeSet = new TreeSet();

//插入一个子集,默认升序

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 list = new ArrayList();

list.add(300);

list.add(120);

list.add(100);

list.add(150);

System.out.println(list); //[300, 120, 100, 150]

Set treeSet = new TreeSet();

//插入一个子集,默认升序

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的存储结构及基本用法介绍完毕。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:基于多线程并发的常见问题(详解)
下一篇:基于Java中对域和静态方法的访问不具有多态性(实例讲解)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~