Set集合

 

set接口是collection接口的子接口，set集合是无序的（但子类中有很多都是有序的），不能有重复的元素，如果用add()加入一个已有的元素，会添加失败，返回false。

 

set接口的继承关系：

 

 

set接口的常用实现类：

 

1、hashset

• 按hash算法来存储元素，具有良好的存储、查找性能。
• 元素无序，就是说排列顺序和添加顺序可能不同
• 不是同步的，如果多个线程同时访问、修改一个hashset，必须要使用同步代码来保证同步。就是说hashset不是线程安全的。
• 元素的值可以是null

 

hashset添加元素（存储）的机制：

先调用该元素的hashcode()方法获取hashcode值，根据hashcode值确定存储位置。

如果该位置上没有元素，则说明hashset集合中没有与之相同的元素，直接在该位置存储该元素。

如果该位置已有元素，则使用equals()比较这两个元素，返回false则在此位置存储该元素（但这样会在一个位置存储多个元素，导致hashset性能降低），返回true则添加失败，不存储此元素。

 

hash，被翻译为哈希、散列。hash算法的价值在于速度，它能快速查找被检索的对象。查询某个元素时，根据hashcode值直接定位元素的存储位置，实现快速查找。如果在hashset中有多个元素的hashcode相同（在一个位置存储了多个元素），会导致查找性能下降。

 

为了保证hashset的性能（一个位置只存储一个元素），我们需要重写元素所属类的hashcode()。

重写规则：如果两个对象通过equals()返回true，则它们的hashcode()也应该相同。

 

因为java自带的类大多数都重写了object的hashcode()方法，所以java自带的类（包括string）、以及继承自这些类的自定义类一般都不必重写hashcode()。不会存入相同的元素，一个位置只存一个元素。

如果要在hashset中存储自定义的类（未继承自java自带的类），则需要在定义该类时重写该类继承自object的hashcode()，而重写hashcode()，又必须重写equals()。

如果不重写，是可以存入该类相同的对象的（这里的相同是指对象本身相同、对象本身的存储地址可以不同）。注意hashset存储的实际上是对象的引用。

 

示例：

1  hashset hashset=new hashset();
2         //java自带的类，下面2个相同的string只会存入第一个。使用new string("ok")也一样
3         hashset.add("ok");
4         hashset.add("ok");

 

1  hashset hashset=new hashset();
2         //这个自定义的类未重写hashcode()、equals()。下面2个相同的对象都会被存入
3         hashset.add(new myclass("ok"));
4         hashset.add(new myclass("ok"));

 

 

重写示例：

 1 class myclass{
 2     private string id;  //id唯一标识创建的实例
 3     private string name;
 4 
 5     public myclass(string id,string name) {
 6         this.id = id;
 7         this.name = name;
 8     }
 9 
10     //tostring可以不重写，不强制要求
11     @override
12     public string tostring() {
13         return id + ":" + name;
14     }
15 
16     //重写hashcode(),返回唯一标识此对象的成员变量的hashcode
17     @override
18     public int hashcode() {
19         return id.hashcode();
20     }
21 
22     //重写equals()，object的equals()是根据对象地址来判断，我们重写的效果是要根据对象本身来判断
23     @override
24     public boolean equals(object object){
25         if (this==object)   //判断是否是同一个对象
26             return true;
27         if (!(object instanceof myclass))  //判断是否是此类的对象
28             return false;  //如果不是，返回false
29         //如果是此类的对象
30         myclass obj=(myclass)object;   //强制类型转换
31         boolean b=this.id.equals(obj.id);  //通过唯一标识对象的id来比较。成员变量id不一定要是单独的，可以是居民类的身份证号码、学生类的学号等。
32         return b;
33     }
34 
35     //可以*添加其它的成员变量、方法
36 
37 }

1  hashset hashset=new hashset();
2         //重写后只存入第一个
3         hashset.add(new myclass("1","ok"));
4         hashset.add(new myclass("1","ok"));

 

hashset是最常用的set。

 

linkedhashset类是hashset的子类，具有hashset的一切特性（依然不能有重复的元素），但其内部使用一个链表维持元素的插入顺序，就是说存取、查找时仍是按hashcode进行的，但同时维护了一个链表来保持元素的添加顺序，遍历linkedhashset时，根据链表依次访问（和存入的顺序相同）。

因为维护了一个链表，存储、查找的性能略低于hashset，但遍历时性能高于hashset（根据链表进行遍历）。

 

 

 

 

 

 

 

2、treeset

set接口有一个子接口sortedset（有序的set），treeset是sortedset的一个实现类。

tresset类采用红黑树的数据结构来存储元素，元素是有序的，但并不是按存入顺序排序的，而是按炎元素的实际值排序的。

 

treeset有2种排序方式：

• 自然排序　　这是treeset默认的排序方式。数值型按数值大小排列，字符按码值排列，date、time按时间戳的大小排列........默认升序。
• 定制排序　　按我们自定义的规则排序

 

treeset具有父类的一切方法，还具有自身的一些方法：

object  first()   返回集合中的第一个元素

object last()    最后一个

object  lower(object obj)   返回obj的前一个元素，默认自然排序（默认升序），所以是lower，略小于

object  higher(object obj)  后一个

sortedset  subset(object start,object end)   返回子集合

sortedset  headset(object end)   返回子集合

sortedset  tailset(object start)

 

java中，一个区间，[a,b)，都是包含前者，不包含后者。

 

 

 

 

 

 

 

3、enumset

enumset是专门为枚举类设计的集合类，enumset的所有元素都必须是某个枚举类的某个枚举值。必须要是同一个枚举类的。

enumset是有序的，根据该枚举值在枚举类中的定义顺序来决定在enumset中的顺序。

 

 

 

 

 

性能比较：

treeset性能最好，因为不需要维持什么，没有其他开销。但应用不广泛，只能用于枚举类的枚举值。

hashset次之，尤其是存储（添加）、查找性能很高。

treeset性能最差，因为要使用红黑树算法来维护集合的元素顺序。

 

hashset有一个子类：linkedhashset。

存储（添加）、查找操作，hashset性能要高于linkedhashset，因为linkedhashset内部要维护一个链表，有额外的开销。

但正是由于链表，遍历集合时，linkedhashset要快于hashset。

 

 

 

 

set的三个实现类：hashset、treeset、enumset都不是线程安全的。

当一个以上的线程访问、修改同一个set集合时，需要手动同步该set集合。

通常可通过collections工具类的静态方法synchronizedxxx()来同步集合。