Set集合
Set集合与Collection基本上完全一样,它没有提供任何额外的方法。实际上Set就是Collection,只是行为略有不同(Set不允许包含重复元素)。
Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set集合中,则添加操作失败,add方法返回false,且新元素不会被加入。
Set判断两个对象相同不是使用==运算符,而是根据equals方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class SetTest { public static void main(String[] args) { Set books = new HashSet(); //添加一个字符串对象 books.add(new String("疯狂Java讲义")); //再次添加一个字符串对象 //因为两个字符串对象通过equals方法比较相等 //所以添加失败,返回false boolean result = books.add(new String("疯狂Java讲义")); //从下面输出看到集合只有一个元素 System.out.println(result + "——>" + books); } }
1
2false——>[疯狂Java讲义]
HashSet类
HashSet是Set接口的典型实现,大多数时候使用Set集合就是使用这个实现类。HashSet按Hash算法来存储集合中的元素,因此具有很好的存取和查找性能。
HashSet具有以下特点
- 不能保证元素的排列顺序,顺序有可能发生变化
- HashSet不是同步的,如果多个线程同时访问一个HashSet,假设有两个或者两个线程同时修改了HashSet集合时,则必须通过代码来保证其同步
- 集合元素值可以是null
当向HashSet集合中存入一个元素时,HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法比较返回true,但它们的hashCode()方法返回值不相等,HashSet将会把它们存储在不同的位置,依然可以添加成功。
也就是说HashSet添加元素能否添加成功取决于该元素的hashCode()方法和equals()方法
简单地说,HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等,并且两个对象的hashCode()方法返回值也相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52public class HashSetTest { public static void main(String[] args) { Set books = new HashSet(); //分别向books集合中添加两个A对象、两个B对象、两个C对象 books.add(new A()); books.add(new A()); books.add(new B()); books.add(new B()); books.add(new C()); books.add(new C()); for (Object obj : books){ System.out.println(obj); } } } //类A的equals()方法总是返回true,但没有重写其hashCode()方法 class A{ @Override public boolean equals(Object obj){ return true; } } //类B的hashCoded()方法总是返回1,但没有重写其equals()方法 class B{ @Override public int hashCode(){ return 1; } } //类C的hashCode()方法总是返回2,且重写了其equals()方法 class C{ @Override public int hashCode(){ return 2; } @Override public boolean equals(Object obj) { return true; } }
输出结果
1
2
3
4
5
6
7B@1 B@1 A@30f39991 C@2 A@a09ee92
上面程序中向books集合中分别添加了两个A对象、两个B对象和两个C对象,其中C类重写了equals()方法总是返回true,hashCode()方法总是返回2,这将导致HashSet把两个C对象当成同一个对象。
当把一个对象放入HashSet中时,如果需要重写该对象对应类的equals()方法,则也应该重写其hashCode()方法。其规则是:如果两个对象通过equals()方法比较返回true,这两个对象的hashCode值也应该相同。
如果两个对象通过equals()方法比较返回true,但这两个对象的hashCode()方法返回不同的hashCode值时,这将导致HashSet会把这两个对象保存在Hash表的不同位置,从而使两个对象都可以添加成功,这就与Set集合的规则有些出入了。
如果两个对象的hashCode()方法返回的hashCode值相同,但它们通过equals()方法比较返回false时将更麻烦:因为两个对象的hashCode值相同,HashSet将试图把它们保存在同一个位置,但又不行(否则将只剩下一个对象),所以实际上会在这个位置用链式结构来保存多个对象;而HashSet访问元素时也是根据元素的hashCode值来快速定位的,如果HashSet中两个以上的元素具有相同的hashCode值,将会导致性能下降。
当从HashSet中访问元素时,HashSet先计算该元素的hashCode值(也就是调用该对象的hashCode()方法的返回值),然后直接到该hashCode值对应的位置去取出该元素,这就是HashSet速度很快的原因。
重写hashCode()方法的基本规则
- 在程序运行过程中,同一个对象多次调用hashCode()方法应该返回相同的值。
- 当两个对象通过equals()方法比较返回true时,这两个对象的hashCode()方法应返回相等的值。
- 对象中用作equals()方法比较标准的Field,都应该用来计算hashCode值。
重写hashCode()方法的一般规则
- 把对象内每个有意义的Field(即每个用作equals()方法比较标准的Field)计算出int类型的hashCode值。
Field类型 | 计算方式 |
---|---|
boolean | hashCode = (f ? 0 : 1) |
整数类型(byte、short、char、int) | hashCode = (int)f |
long | hashCode = (int)(f ^ (f >>> 32)) |
float | hashCode = Float.floatToIntBits(f) |
double | long l = Double.doubleToLongBits(f) |
hashCode = (int)(l ^ (l >>> 32)) | |
普通引用类型 | hashCode = f.hashCode() |
- 用第一步计算出来的多个hashCode值组合计算出一个hashCode值返回
1
2return f1.hashCode() + (int)f2;
为了避免直接相加产生偶然相等(两个对象的f1、f2 Field并不相等,但它们的和恰好相等),可以通过为各Field乘以任意一个质数后再相加。
1
2return f1.hashCode() * 17 + (int)f2 * 13;
如果向HashSet中添加一个可变对象后,后面程序修改了该可变对象的Field,则可能导致它与集合中的其他元素相同(即两个对象通过equals()方法比较返回true,两个对象的hashCode值也相等),这就有可能导致HashSet中包含了两个相同的对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62public class HashSetTest2 { public static void main(String[] args) { HashSet hs = new HashSet(); hs.add(new R(5)); hs.add(new R(-3)); hs.add(new R(9)); hs.add(new R(-2)); //打印HashSet集合,集合元素没有重复 System.out.println(hs); //取出第一个元素 Iterator it = hs.iterator(); R first = (R) it.next(); //为第一个元素的count实例变量赋值 first.count = -3; //再次输出HashSet集合,集合元素有重复元素 System.out.println(hs); //删除count为-3的R对象 hs.remove(new R(-3)); //可以看到被删除了一个R元素 System.out.println(hs); //输出false System.out.println("hs是否包含count为-3的R对象?" + hs.contains(new R(-3))); //输出false System.out.println("hs是否包含count为-2的R对象?" + hs.contains(new R(-2))); } } class R{ int count; public R(int count){ this.count = count; } @Override public String toString(){ return "R[count:" + count + "]"; } @Override public boolean equals(Object obj){ if (this == obj) return true; if (obj != null && obj.getClass() == R.class){ R r = (R) obj; if (r.count == this.count){ return true; } } return false; } @Override public int hashCode(){ return this.count; } }
输出结果
1
2
3
4
5
6[R[count:-2], R[count:-3], R[count:5], R[count:9]] [R[count:-3], R[count:-3], R[count:5], R[count:9]] [R[count:-3], R[count:5], R[count:9]] hs是否包含count为-3的R对象?false hs是否包含count为-2的R对象?false
解析
1
2
3
4因为将第一个R(-2)对象的count值改成了-3,但HashSet一开始 已经把R(-2)对象添加到了hashCode值为-2的地方, 所以当改变R(-2)的count为-3,再打印hs集合就存在两个相同的元素了。
1
2
3
4当删除R(-3)对象时,会先去计算R(-3)对象的hashCode值, 然后根据hashCode值找到对应对象R(-3),此时找到的是集合中的第二个元素, 然后通过equals比较相等则删除hs集合中第二个元素。
1
2
3
4
5同理,判断hs是否包含count为-3的R对象,先根据R(-3)的hashCode值为-3, hs集合中通过hashCode值找不到该对象,所以打印false 判断hs是否包含count为-2的R对象,虽然通过hashCode值-2可以找到就是 第一个元素,但equals方法不等,所以也是打印false
当向HashSet中添加可变对象时,必须十分小心。如果修改HashSet集合中的对象,有可能导致该对象与集合中的其他对象相等,从而导致HashSet无法准确访问该对象。
LinkedHashSet类
HashSet还有一个子类LinkedHashSet,LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置,但它同时使用链表维护元素的次序,这样使得元素看起来是以插入的顺序保存的。也就是说,当遍历LinkedHashSet集合里的元素时,LinkedHashSet将会按元素的添加顺序来访问集合里的元素。
LinkedHashSet需要维护元素的插入顺序,因此性能略低于HashSet的性能,但在迭代访问Set里的全部元素时将有很好的性能,因为它以链表来维护内部顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class LinkedHashSetTest { public static void main(String[] args) { LinkedHashSet books = new LinkedHashSet(); books.add("疯狂Java讲义"); books.add("轻量级Java EE企业应用实战"); System.out.println(books); //删除 疯狂Java讲义 books.remove("疯狂Java讲义"); //重新添加 疯狂Java讲义 books.add("疯狂Java讲义"); System.out.println(books); } }
1
2
3[疯狂Java讲义, 轻量级Java EE企业应用实战] [轻量级Java EE企业应用实战, 疯狂Java讲义]
输出LinkedHashSet集合的元素时,元素的顺序总是与添加顺序一致。
TreeSet类
TreeSet是SortedSet接口的实现类,正如SortedSet名字所暗示的,TreeSet可以确保集合元素处于排序状态。与HashSet集合想比,TreeSet还提供了如下几个额外的方法。
1
2
3
4
5
6//如果TreeSet采用了定制排序,则该方法返回定制排序所使用的Comparator //如果TreeSet采用了自然排序,则返回null public Comparator<? super E> comparator() { return m.comparator(); }
1
2
3
4
5//返回集合中的第一个元素 public E first() { return m.firstKey(); }
1
2
3
4
5//返回集合中的最后一个元素 public E last() { return m.lastKey(); }
1
2
3
4
5
6//返回集合中位于指定元素之前的元素 //即小于指定元素的最大元素,参考元素不需要是TreeSet集合里的元素 public E lower(E e) { return m.lowerKey(e); }
1
2
3
4
5
6//返回集合中位于指定元素之后的元素 //即大于指定元素的最小元素 public E higher(E e) { return m.higherKey(e); }
1
2
3
4
5//返回此Set的子集合,范围从fromElement(包含)到toElement(不包含) public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); }
1
2
3
4
5//返回此Set的子集,由小于toElement的元素组成 public SortedSet<E> headSet(E toElement) { return headSet(toElement, false); }
1
2
3
4
5//返回此Set的子集,由大于或等于fromElement的元素组成 public SortedSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); }
表面上看起来这些方法很复杂,其实它们很简单,因为TreeSet中的元素是有序的,所以增加了访问第一个、前一个、后一个、最后一个元素的方法,并提供了三个从TreeSet中截取子TreeSet的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public class TreeSetTest { public static void main(String[] args) { TreeSet nums = new TreeSet(); //向TreeSet中添加四个Integer对象 nums.add(5); nums.add(2); nums.add(10); nums.add(-9); //输出集合元素,看到集合元素已经处于排序状态 System.out.println(nums); //输出集合里的第一个元素 System.out.println(nums.first()); //输出集合里的最后一个元素 System.out.println(nums.last()); //返回小于4的子集,不包含4 System.out.println(nums.headSet(4)); //返回大于5的子集,如果Set中包含5,子集中也包含 System.out.println(nums.tailSet(5)); //返回大于等于-3、小于4的子集 System.out.println(nums.subSet(-3, 4)); } }
输出结果
1
2
3
4
5
6
7[-9, 2, 5, 10] -9 10 [-9, 2] [5, 10] [2]
根据上面程序的运行结果即可看出,TreeSet并不是根据元素的插入顺序进行排序的,而是根据元素实际值的大小来进行排序的。
与HashSet集合采用hash算法来决定元素的存储位置不同,TreeSet采用红黑树的数据结构来存储集合元素
。
那么TreeSet进行排序的规则是怎样的呢?TreeSet支持两种排序方法:自然排序和定制排序。在默认情况下,TreeSet采用自然排序
自然排序
TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序排列,这种方式就是自然排序。
Java提供了一个Comparable接口,该接口定义了一个compareTo(Object obj),该方法返回一个整数值,实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时,例如obj1.compareTo(obj2),如果该方法返回0,则表明这两个对象相等;如果该方法返回一个正整数,则表明obj1大于obj2;如果该方法返回一个负整数,则表明obj1小于obj2.
Java的一些常用类已经实现了Comparable接口,并提供了比较大小的标准。下面是实现了Comparable接口的常用类
- BigDecimal、BigInteger以及所有的数值型对应的包装类:按它们对应的数值大小进行比较
- Character:按字符的unicode值进行比较
- Boolean:true对应的包装类实例大于false对应的包装类实例
- String:按字符串中字符的unicode值进行比较
- Date、Time:后面的时间、日期比前面的时间、日期大
如果试图把一个对象添加到TreeSet时,则该对象的类必须实现Comparable接口,否则程序将会抛出异常。
1
2
3
4
5
6
7
8
9
10
11public class TreeSetErrorTest { public static void main(String[] args) { TreeSet ts = new TreeSet(); ts.add(new Err()); } } class Err{}
运行程序
1
2
3
4
5
6Exception in thread "main" java.lang.ClassCastException: com.sunrise.eHealth.day0611.Err cannot be cast to java.lang.Comparable at java.util.TreeMap.compare(TreeMap.java:1294) at java.util.TreeMap.put(TreeMap.java:538) at java.util.TreeSet.add(TreeSet.java:255) at com.sunrise.eHealth.day0611.TreeSetErrorTest.main(TreeSetErrorTest.java:10)
当把一个对象加入TreeSet集合中时,TreeSet调用该对象的compareTo(Object obj)方法与容器中的其他对象比较大小,然后根据红黑树结构找到它的存储位置。如果两个对象通过compareTo(Object obj)方法比较相等,新对象将无法添加到TreeSet集合中。
对于TreeSet集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过compareTo(Object obj)方法比较是否返回0,如果通过compareTo(Object obj)方法比较返回0,TreeSet则会认为它们相等,否则就认为它们不相等。
定制排序
TreeSet的自然排序是根据集合元素的大小,TreeSet将它们以升序排序。如果需要实现定制排序,例如以降序排序,则可以通过Comparator接口的帮助。
如果需要实现定制排序,则需要在创建TreeSet集合对象时,提供一个Comparator对象与该TreeSet集合关联,由该Comparator对象负责集合元素的排序逻辑。
当通过Comparator对象来实现TreeSet的定制排序时,依然不可以向TreeSet中添加类型不同的对象,否则会引发ClassCastException异常。使用定制排序时,TreeSet对集合元素排序不管集合元素本身的大小,而是由Comparator对象负责集合元素的排序规则。TreeSet判断两个集合元素相等的标准是:通过Comparator比较两个元素返回了0,这样TreeSet不会把第二个元素添加到集合中。
EnumSet类
EnumSet是一个专门为枚举类设计的集合类,EnumSet中的所有元素都必须是指定枚举类型的枚举值,该枚举类型在创建EnumSet时显式或隐式地指定。EnumSet集合元素也是有序的,EnumSet以枚举值在Enum类内的定义顺序来决定集合元素的顺序。
EnumSet在内部以位向量的形式存储,这种存储形式非常紧凑、高效,因此EnumSet对象占用内存很小,而且运行效率很好。尤其是进行批量操作(如调用containsAll和retainAll方法)时,如果其参数也是EnumSet集合,则该批量操作的执行速度也非常快。
EnumSet类没有暴露任何构造器来创建该类的实例,程序应该通过它提供的static方法来创建EnumSet对象。EnumSet类它提供了如下常用的static方法来创建EnumSet对象
创建一个包含指定枚举类里所有枚举值的EnumSet集合
1
2
3
4
5
6public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) { EnumSet<E> result = noneOf(elementType); result.addAll(); return result; }
创建一个其元素类型与指定EnumSet里元素类型相同的EnumSet集合,新EnumSet集合包含原EnumSet集合所不包含的、此枚举类剩下的枚举值(即新EnumSet和原EnumSet集合的集合元素加起来就是该枚举类的所有枚举值)
1
2
3
4
5
6public static <E extends Enum<E>> EnumSet<E> complementOf(EnumSet<E> s) { EnumSet<E> result = copyOf(s); result.complement(); return result; }
使用一个普通集合来创建EnumSet集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public static <E extends Enum<E>> EnumSet<E> copyOf(Collection<E> c) { if (c instanceof EnumSet) { return ((EnumSet<E>)c).clone(); } else { if (c.isEmpty()) throw new IllegalArgumentException("Collection is empty"); Iterator<E> i = c.iterator(); E first = i.next(); EnumSet<E> result = EnumSet.of(first); while (i.hasNext()) result.add(i.next()); return result; } }
创建一个与指定EnumSet具有相同元素类型、相同集合元素的EnumSet集合
1
2
3
4public static <E extends Enum<E>> EnumSet<E> copyOf(EnumSet<E> s) { return s.clone(); }
创建一个元素类型为指定枚举类型的空EnumSet
1
2
3
4
5
6
7
8
9
10
11
12public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) { Enum<?>[] universe = getUniverse(elementType); if (universe == null) throw new ClassCastException(elementType + " not an enum"); if (universe.length <= 64) return new RegularEnumSet<>(elementType, universe); else return new JumboEnumSet<>(elementType, universe); }
创建一个包含一个或多个枚举值的EnumSet集合,传入的多个枚举值必须属于同一个枚举类。
1
2
3
4
5
6
7
8public static <E extends Enum<E>> EnumSet<E> of(E first, E... rest) { EnumSet<E> result = noneOf(first.getDeclaringClass()); result.add(first); for (E e : rest) result.add(e); return result; }
创建一个包含从from枚举值到to枚举值范围内所有枚举值的EnumSet集合
1
2
3
4
5
6
7
8public static <E extends Enum<E>> EnumSet<E> range(E from, E to) { if (from.compareTo(to) > 0) throw new IllegalArgumentException(from + " > " + to); EnumSet<E> result = noneOf(from.getDeclaringClass()); result.addRange(from, to); return result; }
以下代码示范了EnumSet集合的常规用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38public class EnumSetTest { public static void main(String[] args) { //创建一个EnumSet集合,集合元素就是Season枚举类的全部枚举值 EnumSet es1 = EnumSet.allOf(Season.class); System.out.println(es1); //创建一个EnumSet空集合,指定其集合元素是Season类的枚举值 EnumSet es2 = EnumSet.noneOf(Season.class); System.out.println(es2); //手动添加两个元素 es2.add(Season.WINTER); es2.add(Season.SPRING); System.out.println(es2); //以指定枚举值创建EnumSet集合 EnumSet es3 = EnumSet.of(Season.SUMMER, Season.WINTER); System.out.println(es3); EnumSet es4 = EnumSet.range(Season.SUMMER, Season.WINTER); System.out.println(es4); //新创建的EnumSet集合元素和es4集合元素有相同的类型 //es5集合元素 + es4集合元素 = Season枚举类的全部枚举值 EnumSet es5 = EnumSet.complementOf(es4); System.out.println(es5); } } enum Season{ SPRING,SUMMER,FALL,WINTER }
输出结果
1
2
3
4
5
6
7[SPRING, SUMMER, FALL, WINTER] [] [SPRING, WINTER] [SUMMER, WINTER] [SUMMER, FALL, WINTER] [SPRING]
当试图复制一个Collection集合里的元素来创建EnumSet集合时,必须保证Collection集合里的所有元素都是同一个枚举类的枚举值。
各Set实现类的性能分析
HashSet和TreeSet是Set的两个典型实现,到底如何选择HashSet和TreeSet呢?
HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作),因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时,才应该使用TreeSet,否则都应该使用HashSet。
HashSet还有一个子类:LinkedHashSet,对于普通的插入、删除操作,LinkedHashSet比HashSet要略微慢一点,这是有维护链表所带来的额外开销造成的;不过,因为有了链表,遍历LinkedHashSet会更快。
EnumSet是所有Set实现类中性能最好的,但它只能保存同一个枚举类的枚举值作为集合元素。
必须指出的是,Set的三个实现类HashSet、TreeSet和EnumSet都是线程不安全的。如果有多个线程同时访问一个Set集合,并且有超过一个线程修改了该Set集,则必须手动保证该Set集合的同步性。通常可以通过Collections工具类的synchronizedSortedSet方法来包装该Set集合。此操作最好在创建时进行,以防止对Set集合的意外非同步访问。
最后
以上就是忧伤冷风最近收集整理的关于Set集合的全部内容,更多相关Set集合内容请搜索靠谱客的其他文章。
发表评论 取消回复