• 欢迎访问天天编码网站,Java技术、技术书单、开发工具,欢迎加入天天编码
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏天天编码吧
  • 我们的淘宝店铺已经开张了哦,传送门:https://shop145764801.taobao.com/

Java中HashSet、TreeSet和LinkedHashSet的联系与区别

Java基础 tiantian 3259次浏览 0个评论 扫描二维码

Java中的Set概念,与数学中的概念一样,一个Set是指不包含重复元素的的集合。通常在Java中使用Set元素的主要原因就是为了利用Set的元素不可重复特性。在JDK的集合框架中,在顶级接口之下,有一个直接的子类接口Set。而且,JDK还提供了对该接口的三个常见实现:HashSet、TreeSet和LinkedHashSet。此处,什么时候使用Set集合,使用哪个Set集合也是一个非常重要的问题。简单来说,如果你需要一个时间性能好的Set,应该使用HashSet;如果需要一个具有排序功能的Set,应该使用TreeSet;如果需要一个你能存储元素插入顺序的Set,应该使用LinkedHashSet。

Set接口

正如下图所示,Set接口是JDK中集合框架顶级接口Collection的直接子接口。在一个Set中,不允许出现重复的元素,一个Set集合中的元素都必须是唯一的。你可以简单地添加元素到Set集合中,重复的元素会自动被忽略掉,不会被添加成功。

Java中HashSet、TreeSet和LinkedHashSet的联系与区别

HashSet vs TreeSet vs LinkedHashSet

HashSet是基于数据结构中的哈希表(hash table)实现的。它的元素都是没有顺序的,它的add、remove和contains方法都只有O(1)的时间复杂度,效率非常好。当然了,哈希表空间效率不高的问题,HashSet同样具有,这是典型的空间换时间。

TreeSet是基于数据结构中的树(tree)实现的,具体来说,是具有排序功能的红黑树(red-black tree)。它的元素是有序的,但是它的add、remove和contains方法的时间复杂度是O(log(n))。而且,它还提供了好几个方法用于处理它的有序性,比如first()、last()、headSet()、tailSet()等。

LinkedHashSet被认为是基于HashSet和TreeSet之间的一个Set。它也是基于数据结构中的哈希表(hash table) 实现的。但是,它同时使用了数据结构中的链表(linked list)来连接整个的哈希表。所以,它可以存储元素的插入顺序。它的方法的时间复杂度是O(1)。

TreeSet的顺序

我们知道,在Set的三种类型中,TreeSet的元素是有顺序的,那么TreeSet中的元素的排序依据是什么呢?我们来看一个简单的实例:

class Dog {
int size;

public Dog(int size ) {
this.size = size;
}

@Override
public String toString() {
return size + "";
}
}

加入我们具有如上所示的一个POJO,当我们使用TreeSet来存储时:

public class Main {
public static void main(String[] args) {
TreeSet dogSet = new TreeSet();
dogSet.add(new Dog(2));
dogSet.add(new Dog(1));
dogSet.add(new Dog(3));
for (Dog dog : dogSet) {
System.out.println(dog + " ");
}
}
}

这个实例代码编译不会出错,但是运行时,会抛出如下所示的错误信息:

Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at collection.collection.Main.main(Main.java:22)

之所以出现这个错误,是因为TreeSet的元素需要有序。所以,其元素Dog必须要实现java.lang.Comparable接口。所以,Dog类应该修改成如下的形式:

class Dog implements Comparable {
int size;

public Dog(int size) {
this.size = size;
}

@Override
public String toString() {
return size + "";
}

@Overdie
public int compareTo(Dog dog) {
return size - dog.size;
}
}

这样修改以后,程序运行才能成功,并且运行结果如下:

1 2 3

TreeSet中元素按照我们定义的规则(compareTo方法)实现了排序。

HashSet与LinkedHashSet的顺序

我们知道HashSet的元素是没有任何顺序的,而LinkedHashSet的元素顺序是元素的插入顺序。我们可以使用如下的代码片段验证一下:

HashSet dogSet = new HashSet();
// LinkedHashSet dogSet = new LinkedHashSet();
dogSet.add(new Dog(2));
dogSet.add(new Dog(1));
dogSet.add(new Dog(3));
dogSet.add(new Dog(5));
dogSet.add(new Dog(4));
for (Dog dog : dogSet) {
System.out.println(dog + " ");
}

性能对比

三种Set分别使用哈希表、红黑树、哈希表来实现,这导致了它们对于add操作的时间复杂度具有较大差异。我们可以使用如下的代码片段进行测试:

public static void main(String[] args) {
Random random = new Random();
HashSet dogSet = new HashSet();
// TreeSet dogSet = new TreeSet();
// LinkedHashSet dogSet = new LinkdedHashSet();

long startTime = System.nanoTime();
for (int i = 0; i < 1000; i ++) {
int x = random.nextInt(1000 - 10) + 10;
dogSet.add(new Dog(x));
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("duration: " + duration);
}

此处的测试方法也许不是很精确,但是测验结果是可信的。TreeSet带来元素排序特性的同时,牺牲了其操作的性能。


天天编码 , 版权所有丨本文标题:Java中HashSet、TreeSet和LinkedHashSet的联系与区别
转载请保留页面地址:http://www.tiantianbianma.com/java-hashset-treeset-linkedhashset.html/
喜欢 (2)
支付宝[多谢打赏]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址