专栏首页desperate633Java的HashSet vs. TreeSet vs. LinkedHashSet比较

Java的HashSet vs. TreeSet vs. LinkedHashSet比较

set是用来存储没有重复的元素的。set在java中有三种比较常用实现:HashSet, TreeSet and LinkedHashSet。所以,不同的时候我们自然需要考虑如何选择使用不同的set。这就要我们对于这三种set的特点和实现有一定的了解。一般来说,如果我们需要一个存取效率比较高的set,我们可以选择hashset,如果我们需要一个可以自动给元素排序的set,我们就需要使用treeset,如果我们想要元素按插入的样子保持顺序,那么我们就可以使用LinkedHashSet。

image.png

hashset通过哈希表实现,元素是不排序的,所以输出set的时候元素的顺序是随机的,add,remove, and contains这三个方法的时间复杂度都是常数 O(1)。 treeset通过红黑树实现,元素是排好序的,但是相应的操作时间复杂度就增加了,add,remove, and contains这三个方法的时间复杂度都是 O(log (n)) LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1) LinkedHashSet是介于HashSet and TreeSet.之间。通过一个带链表的哈希表实现,所以它是按插入顺序排序的,保持插入的顺序,基本操作的时间复杂度和hashset一样都是常数时间。

** 注意的是,treeset由于需要对元素排序,所以添加的元素需要实现comparable或者comparator,不然就会报错 **像下面这个例子

import java.util.Iterator;
import java.util.TreeSet;

public class SetTest {

    public static void main(String[] args) {
        
        TreeSet<Dog> tree = new TreeSet<>();
        tree.add(new Dog(1));
        tree.add(new Dog(5));
        tree.add(new Dog(3));
        
        Iterator<Dog> iter = tree.iterator();
        while(iter.hasNext()) {
            System.out.println(iter.next());
        }
    }

}

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

image.png

我们对dog实现comparable接口就可以

class Dog implements Comparable<Dog>{
    private int size;
    
    public Dog(int size) {
        this.size = size;
    }

    @Override
    public int compareTo(Dog o) {
        return this.size - o.size;
    }
    
    public String toString() {
        return size + " ";
    }
    
}

下面我们简单的写一个小程序测试三个set的效率:

public static void main(String[] args) {
Random r = new Random();
HashSet<Dog> hashSet = new HashSet<Dog>();
TreeSet<Dog> treeSet = new TreeSet<Dog>();
LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
// start time
long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Dog(x));
}
// end time
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: " + duration);
}

image.png

image.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 爬楼梯题目分析代码小结

    假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

    desperate633
  • LintCode 判断数独是否合法题目分析代码

    请判定一个数独是否有效。 该数独可能只填充了部分数字,其中缺少的数字用 .表示。

    desperate633
  • LintCode整数排序题目分析解答选择排序插入排序小结

    Given an integer array, sort it in ascending order. Use selection sort, bubble s...

    desperate633
  • Single Number

    问题:给你一组数一个数字出现一次,其他的数字出现两次,找出那个出现一次的数字 分析:相同数字异或为0,所以将所有数字都异或后剩下的就是出现一次的数 class ...

    用户1624346
  • agc015E - Mr.Aoki Incubator(dp)

    平面上有$n$个点,每个点都有一个位置$x_i$,和向右的速度$v_i$ 现在要求你对其中的一些点进行染色,当一个点被染色后,在无限距离内与它相遇的点也会被染...

    attack
  • 构造蛇形矩阵

    1  2  3 8  9  4 7  6  5 n=4的回型矩阵 1  2  3  4 12  13  14  5 11  16  15  6 10  9 ...

    week
  • HUST 1586 数字排列

    1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

    Angel_Kitty
  • C++之基于排序方法求一组数的中位数

    中位数也就是中值; 故需要先对数组进行排序(选择,插入,冒泡排序),然后在找出数组的中值。 //求中值 #include<iostream> using nam...

    互联网金融打杂
  • HDU3015(树状数组+离散)详解版

    逐梦的青春
  • POJ3744 Scout YYF I(概率dp 矩阵快速幂)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack

扫码关注云+社区

领取腾讯云代金券