Set接口
是Collection的子接口,Set要点:
- 不允许包含相同的元素
- 使用equals方法判断对象是否相同
- 一个不包含重复元素的 collection。更确切地讲,set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2,并且最多包含一个 null 元素
HashSet类
该类实现的接口:Serializable, Cloneable, Iterable, Collection, Set
HashSet原理
- HashSet是基于HashMap来实现的,操作很简单,更像是对HashMap做了一次“封装”,而且只使用了HashMap的key来实现各种特性
- HashSet是通过HashMap实现,整个HashSet的核心就是HashMap。HashMap中的键作为HashSet中的值,HashMap中的值通过创建一个假的value来实现。
- 下面是HashSet的部分源码
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
* 首先有一个HashMap成员变量,我们在HashSet的构造函数中将其初始化,默认情况下用的是Initial capacity为16,load factory加载因子为0.75
*/
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public int size() {
return map.size();
}
HashSet中的一些基本操作都是调用HashMap来实现的。
HashSet注意事项
- HashSet不同步,如果需要使用多线程访问,可以使用
方法包装Collections.synchronizedSet()
Set s = Collections.synchronizedSet(new HashSet());
- HashSet类判断两个元素是否相等,需要两个条件,第一个条件:
的结果为true,第二个条件:equals()
的值相等,即对应的元素的hashCode码要相同。hashCode()
- HashSet类:向该类中添加元素,排列的顺序不确定,因此只有不关心集合中元素的顺序时才应该是会用HashSet类来存储元素。
-
集合HashSet类中元素的值可以是null
下面的例子来自:https://www.bysocket.com/?p=195
package set;
import java.util.HashSet;
import java.util.Set;
public class HashSetTest {
public static void main(String[] agrs){
Set s = new HashSet();
s.add(new EqualsObj());
s.add(new EqualsObj());
s.add(new HashCodeObj());
s.add(new HashCodeObj());
s.add(new HashSetObj());
s.add(new HashSetObj());
System.out.println("HashSet Elements:");
System.out.print("\t" + s + "\n");
}
}
class EqualsObj {
public boolean equals(Object obj) {
return true;
}
}
class HashCodeObj {
public int hashCode() {
return ;
}
}
class HashSetObj {
public boolean equals(Object obj) {
return true;
}
public int hashCode() {
return ;
}
}
在控制台输出的结果如下:
HashSet Elements:
[set.EqualsObj@7852e922, set.HashCodeObj@1, set.HashCodeObj@1, set.HashSetObj@2, set.EqualsObj@6d06d69c]
从输出结果可以看出,1.HashSet类存储数据的顺序是不确定的,2. 该类只认为hashCode和equals方法的值都不同的对象为不同的对象
当我们使用HashSet集合时,需要注意:将对象存储在HashSet之前,要确保对象重写了和
equals()
方法,即如果要把一个对象放在HashSet中,如果重写了该对象的
hashCode()
方法,也要重写该对象的
equals()
方法,修改的规则是:如果两个对象通过equals方法比较返回true时,这两个对象的hashCode一定也要相同
hashCode()
-
HashSet集合的优点:
它可以通过一个对象快速查找到集合中的对象。hash算法的价值在于查找速度很快:它是通过将对象转变为对应的hashCode值,然后按照hashCode值在桶中对应位置取出该元素。
下面的程序来自:http://blog.csdn.net/shb_derek1/article/details/8729605
package set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class HashSetTest2 {
public static void main(String[] args) {
Set sets = new HashSet();
sets.add(new HashSet2());
sets.add(new HashSet2(-));
sets.add(new HashSet2());
sets.add(new HashSet2());
sets.add(new HashSet2(-));
//HashSet是无序集合,因此打印的结果是无序的
System.out.println(sets);
Iterator i = sets.iterator();
//取出集合中第一个元素元素
HashSet2 hs = (HashSet2) i.next();
//将取出的元素赋新值,赋的值与集合中原有的元素之相同
hs.count = ;
//集合中有两个元素一样
System.out.println(sets);
//从集合中移出值
sets.remove(new HashSet2());
System.out.println(sets);
//集合中不包含21,因为按照hashCode值找到的槽内没有该值。
System.out.println("sets.contains(new HashSets(21):"+sets.contains(new HashSet2()));
}
}
class HashSet2 {
int count;
public HashSet2(int count) {
super();
this.count = count;
}
public String toString() {
return "HashSet2 [count=" + count + "]" ;
}
public boolean equals(Object obj) {
if(obj instanceof HashSet2){
HashSet2 hs = (HashSet2) obj;
if(this.count == hs.count)
return true;
return false;
}
return false;
}
public int hashCode() {
return this.count;
}
}
运行结果:
[HashSet2 [count=-], HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
[HashSet2 [count=], HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
[HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
sets.contains(new HashSets():false
LinkedHashSet类
该类实现的接口:Serializable, Cloneable, Iterable, Collection, Set
- 该类是一种可以记住元素插入次序的类,即输出顺序与插入顺序一致
- 它是HashSet类的子类,所以也是通过HashCode的值来决定元素的位置
package set;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSet1 {
public static void main(String[] args) {
Set s = new LinkedHashSet();
s.add(new String("e"));
s.add(new String("b"));
s.add(new String("a"));
s.add(new String("c"));
System.out.println(s);
}
}
上述程序运行结果:
[e, b, a, c]
TreeSet类
该类实现的接口:Serializable, Cloneable, Iterable, Collection, NavigableSet, Set, SortedSet
- TreeSe使用红黑树的结构实现,集合中的元素进行排序,添加、删除等算法的复杂度为O(log(n))
- 使用该集合的类必须实现Comparable接口中的
方法,因为该类是有序的compare To()
-
该类是通过元素的值进行排序的,而不是通过插入元素的顺序进行排序的
如下面代码:
package set;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet nums = new TreeSet();
nums.add(new Bird());
nums.add(new Bird());
nums.add(new Bird());
nums.add(new Bird());
System.out.println(nums);
}
}
class Bird {
int size;
public Bird(int size) {
super();
this.size = size;
}
public String toString() {
return "Bird [size=" + size + "]";
}
}
运行后,编译器报错:
Exception in thread "main" java.lang.ClassCastException: set.Bird cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(TreeMap.java:)
at java.util.TreeSet.add(TreeSet.java:)
at set.TreeSetTest.main(TreeSetTest.java:)
因为TreeSet是实现SortedSet接口的类,因此他有排序功能,对应的传递进来的对象也要有需要可比较。先修改上述代码如下:
package set;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet nums = new TreeSet();
nums.add(new Bird());
nums.add(new Bird());
nums.add(new Bird());
nums.add(new Bird());
System.out.println(nums);
}
}
class Bird implements Comparable<Bird>{
int size;
public Bird(int size) {
super();
this.size = size;
}
public String toString() {
return "Bird [size=" + size + "]";
}
public int compareTo(Bird o) {
// TODO Auto-generated method stub
return this.size - o.size;
}
}
程序运行结果:
[Bird [size=], Bird [size=], Bird [size=], Bird [size=]]