HashSet,TreeSet和LinkedHashSet的区别（hashset和treeset的区别和联系）

25-03-11 7

如果您对HashSet,TreeSet和LinkedHashSet的区别感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于HashSet,TreeSet和LinkedHashS

如果您对HashSet,TreeSet和LinkedHashSet的区别感兴趣，那么本文将是一篇不错的选择，我们将为您详在本文中，您将会了解到关于HashSet,TreeSet和LinkedHashSet的区别的详细内容，我们还将为您解答hashset和treeset的区别和联系的相关问题，并且为您提供关于5.Java集合框架剖析之 Hashset和LinkedHashSet源码剖析、HashMap,HashTable和TreeSet,HashSet的区别、HashSet vs TreeSet vs LinkedHashSet在添加重复值的基础上、HashSet vs. TreeSet vs. LinkedHashSet的有价值信息。

本文目录一览：

HashSet,TreeSet和LinkedHashSet的区别（hashset和treeset的区别和联系）
5.Java集合框架剖析之 Hashset和LinkedHashSet源码剖析
HashMap,HashTable和TreeSet,HashSet的区别
HashSet vs TreeSet vs LinkedHashSet在添加重复值的基础上
HashSet vs. TreeSet vs. LinkedHashSet

HashSet,TreeSet和LinkedHashSet的区别（hashset和treeset的区别和联系）

Set接口
Set不允许包含相同的元素，如果试图把两个相同元素加入同一个集合中，add方法返回false。
Set判断两个对象相同不是使用==运算符，而是根据equals方法。也就是说，只要两个对象用equals方法比较返回true，Set就不会接受这两个对象。

HashSet
HashSet有以下特点
 不能保证元素的排列顺序，顺序有可能发生变化
 不是同步的
 集合元素可以是null,但只能放入一个null
当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。
简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等
注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算 hashCode的值。

LinkedHashSet
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

TreeSet类
TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。
obj1.compareTo(obj2)方法如果返回0，则说明被比较的两个对象相等，如果返回一个正数，则表明obj1大于obj2，如果是负数，则表明obj1小于obj2。
如果我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0
定制排序
自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法

5.Java集合框架剖析之 Hashset和LinkedHashSet源码剖析

  1 package java.util;
  2 
  3 import java.io.InvalidObjectException;
  4 import sun.misc.SharedSecrets;
  5 
  6 //HashSet底层是数组 + 单链表 + 红黑树的数据结构
  7 public class HashSet<E> extends AbstractSet<E>
  8     implements Set<E>, Cloneable, java.io.Serializable {
  9     
 10     static final long serialVersionUID = -5024744406713321676L;
 11 
 12     // 底层使用HashMap来保存HashSet中所有元素
 13     private transient HashMap<E,Object> map;
 14 
 15     // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final
 16     private static final Object PRESENT = new Object();
 17 
 18     //默认的无参构造器，构造一个空的HashSet。 
 19     // 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
 20     public HashSet() {
 21         map = new HashMap<>();
 22     }
 23 
 24      //构造一个包含指定collection中的元素的新set。 
 25      //实际底层使用默认的加载因子0.75和足以包含指定 collection中所有元素的初始容量来创建一个HashMap。 
 26     public HashSet(Collection<? extends E> c) {
 27         map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
 28         addAll(c);
 29     }
 30 
 31     //以指定的initialCapacity和loadFactor构造一个空的HashSet。
 32     //实际底层以相应的参数构造一个空的HashMap。
 33     public HashSet(int initialCapacity, float loadFactor) {
 34         map = new HashMap<>(initialCapacity, loadFactor);
 35     }
 36 
 37     //以指定的initialCapacity构造一个空的HashSet。 
 38     //实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
 39     public HashSet(int initialCapacity) {
 40         map = new HashMap<>(initialCapacity);
 41     }
 42 
 43     //以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
 44     //此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 
 45     //实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 
 46     HashSet(int initialCapacity, float loadFactor, boolean dummy) {
 47         map = new LinkedHashMap<>(initialCapacity, loadFactor);
 48     }
 49 
 50     //返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 
 51     //底层实际调用底层HashMap的keySet来返回所有的key。 
 52     //可见HashSet中的元素，只是存放在了底层HashMap的key上，value使用一个static final的Object对象标识。 
 53     public Iterator<E> iterator() {
 54         return map.keySet().iterator();
 55     }
 56 
 57     //返回此set中的元素的数量（set的容量）。 
 58     //底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
 59     public int size() {
 60         return map.size();
 61     }
 62 
 63     //判断set是否为空，则返回true,底层实际调用HashMap的isEmpty()判断该HashSet是否为空。
 64     public boolean isEmpty() {
 65         return map.isEmpty();
 66     }
 67 
 68     //如果此set包含指定元素，则返回true。  
 69     //底层实际调用HashMap的containsKey判断是否包含指定key。
 70     public boolean contains(Object o) {
 71         return map.containsKey(o);
 72     }
 73 
 74     //如果此set中尚未包含指定元素，则添加指定元素。 
 75     //底层实际将将该元素作为key放入HashMap。 
 76     //由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
 77     //与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， 
 78     //新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， 
 79     //因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， 
 80     //原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。
 81     public boolean add(E e) {
 82         return map.put(e, PRESENT)==null;
 83     }
 84 
 85     //如果指定元素存在于此set中，则将其移除。
 86     public boolean remove(Object o) {
 87         return map.remove(o)==PRESENT;
 88     }
 89 
 90     //从此set中移除所有元素。此调用返回后，该set将为空。 
 91     //底层实际调用HashMap的clear方法清空Entry中所有元素。 
 92     public void clear() {
 93         map.clear();
 94     }
 95 
 96     //返回此HashSet实例的浅表副本：并没有复制这些元素本身。
 97     @SuppressWarnings("unchecked")
 98     public Object clone() {
 99         try {
100             HashSet<E> newSet = (HashSet<E>) super.clone();
101             newSet.map = (HashMap<E, Object>) map.clone();
102             return newSet;
103         } catch (CloneNotSupportedException e) {
104             throw new InternalError(e);
105         }
106     }
107 
108     //序列化
109     private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
110         s.defaultWriteObject();
111 
112         s.writeInt(map.capacity());
113         s.writeFloat(map.loadFactor());
114 
115         s.writeInt(map.size());
116 
117         for (E e : map.keySet())
118             s.writeObject(e);
119     }
120 
121     //反序列化
122     private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {
123         s.defaultReadObject();
124 
125         int capacity = s.readInt();
126         if (capacity < 0) {
127             throw new InvalidObjectException("Illegal capacity: " + capacity);
128         }
129 
130         float loadFactor = s.readFloat();
131         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
132             throw new InvalidObjectException("Illegal load factor: " + loadFactor);
133         }
134 
135         int size = s.readInt();
136         if (size < 0) {
137             throw new InvalidObjectException("Illegal size: " + size);
138         }
139 
140         capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f), HashMap.MAXIMUM_CAPACITY);
141 
142         SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));
143 
144         map = (((HashSet<?>)this) instanceof LinkedHashSet ?
145                new LinkedHashMap<E,Object>(capacity, loadFactor) :
146                new HashMap<E,Object>(capacity, loadFactor));
147 
148         for (int i=0; i<size; i++) {
149             @SuppressWarnings("unchecked")
150                 E e = (E) s.readObject();
151             map.put(e, PRESENT);
152         }
153     }
154 
155     public Spliterator<E> spliterator() {
156         return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
157     }
158 }

 1 package java.util;
 2 
 3 //LinkedHashSet继承自HashSet，内部使用的是LinkHashMap,好处是LinkedHashSet中的元素顺序是可以保证的，即遍历顺序和插入顺序是一致的。
 4 //LinkedHashSet底层是 数组 + 单链表 + 红黑树 + 双向链表的数据结构
 5 public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
 6 
 7     private static final long serialVersionUID = -2851667679971038690L;
 8 
 9     //调用HashSet中的LinkedHashMap
10     public LinkedHashSet(int initialCapacity, float loadFactor) {
11         super(initialCapacity, loadFactor, true);
12     }
13 
14     //调用HashSet中的 LinkedHashMap 的构造方法，该方法初始化了初始起始容量，以及加载因子，
15     //dummy 参数没有作用这里可以忽略，在HashSet中只是为了区别其他的构造方法而已
16     public LinkedHashSet(int initialCapacity) {
17         super(initialCapacity, .75f, true);
18     }
19 
20     //初始化 LinkedHashMap 的初始容量为诶 16 加载因子为 0.75f
21     public LinkedHashSet() {
22         super(16, .75f, true);
23     }
24 
25     //初始化 LinkedHashMap 的初始容量为 Math.max(2*c.size(), 11) 加载因子为 0.75f 
26     public LinkedHashSet(Collection<? extends E> c) {
27         super(Math.max(2*c.size(), 11), .75f, true);
28         addAll(c);
29     }
30 
31     //
32     @Override
33     public Spliterator<E> spliterator() {
34         return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
35     }
36 }

HashMap,HashTable和TreeSet,HashSet的区别

HashMap 和和 HashTable 区别

HashMap:线程不安全的，key和 value 可以是 null

Hashtable:线程安全的，key和 values 不可以是 null，否则会报空指针异常。

TreeSet 和 HashSet 区别

HashSet是采用hash表来实现的。其中的元素是没有顺序排列的，add,remove,contain等方法都是复杂度为O（1）的方法。

TreeSet是采用树结构来实现的（红黑树算法），元素是按顺序进入的，因此以上方法复杂度都为O(log(n)),还提供了一些排序的set,如first(),last(),headSet(),tailSet()方法。

HashSet vs TreeSet vs LinkedHashSet在添加重复值的基础上

我正在学习核心Java的心脏，即Collections。我想知道，当我们在添加重复元素什么内部发生HashSet，TreeSet，LinkedHashSet。

无论条目被替换，忽略还是引发异常，程序都将终止 。一个子问题是，哪个问题 的所有操作都具有相同或平均的时间复杂度

您的答复将不胜感激。

HashSet vs. TreeSet vs. LinkedHashSet

Set 集合不包含重复的元素，这是使用 Set 的主要原因。有三种常见的 Set 实现 ——HashSet, TreeSet 和 LinkedHashSet。什么时候使用它们，使用哪个是个重要的问题。总体而言，如果你需要一个访问快速的 Set，你应该使用 HashSet；当你需要一个排序的 Set，你应该使用 TreeSet；当你需要记录下插入时的顺序时，你应该使用 LinedHashSet。

1. Set 接口

Set 接口继承了 Collection 接口。Set 集合中不能包含重复的元素，每个元素必须是唯一的。你只需将元素加入 set 中，重复的元素会自动移除。

2. HashSet vs. TreeSet vs. LinkedHashSet

HashSet 是采用 hash 表来实现的。其中的元素没有按顺序排列，add ()、remove () 以及 contains () 等方法都是复杂度为 O (1) 的方法。

TreeSet 是采用树结构实现 (红黑树算法)。元素是按顺序进行排列，但是 add ()、remove () 以及 contains () 等方法都是复杂度为 O (log (n)) 的方法。它还提供了一些方法来处理排序的 set，如 first (), last (), headSet (), tailSet () 等等。

LinkedHashSet 介于 HashSet 和 TreeSet 之间。它也是一个 hash 表，但是同时维护了一个双链表来记录插入的顺序。基本方法的复杂度为 O (1)。

3. TreeSet 的例子

TreeSet tree =newTreeSet();

tree.add(12);

tree.add(63);

tree.add(34);

tree.add(45);

Iterator iterator = tree.iterator();

System.out.print("Tree set data: ");

while(iterator.hasNext()) {

System.out.print(iterator.next() +" ");

}

输出如下：

1	Tree set data: 12 34 45 63

现在让我们定义一个 Dog 类：

classDog {

intsize;

publicDog(ints) {

size = s;

}

publicString toString() {

returnsize +"";

}

我们将 “dog” 添加到 TreeSet 中：

importjava.util.Iterator;

importjava.util.TreeSet;

publicclassTestTreeSet {

publicstaticvoidmain(String[] args) {

TreeSet dset =newTreeSet();

dset.add(newDog(2));

dset.add(newDog(1));

dset.add(newDog(3));

Iterator iterator = dset.iterator();

while(iterator.hasNext()) {

System.out.print(iterator.next() +" ");

}

编译正常，但是运行时出错：

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.TestTreeSet.main(TestTreeSet.java:22)

因为 TreeSet 是有序的，Dog 类必须实现 java.lang.Comparable 的 compareTo () 方法才行:

classDogimplementsComparable{

intsize;

publicDog(ints) {

size = s;

}

publicString toString() {

returnsize +"";

}

@Override

publicintcompareTo(Dog o) {

returnsize - o.size;

}

输出:

1 2 3

4. HashSet 的例子

HashSet dset =newHashSet();

dset.add(newDog(2));

dset.add(newDog(1));

dset.add(newDog(3));

dset.add(newDog(5));

dset.add(newDog(4));

Iterator iterator = dset.iterator();

while(iterator.hasNext()) {

System.out.print(iterator.next() +" ");

}

输出：

5 3 2 1 4

注意输出顺序是不确定的。

5. LinkedHashSet 的例子

LinkedHashSet dset =newLinkedHashSet();

dset.add(newDog(2));

dset.add(newDog(1));

dset.add(newDog(3));

dset.add(newDog(5));

dset.add(newDog(4));

Iterator iterator = dset.iterator();

while(iterator.hasNext()) {

System.out.print(iterator.next() +" ");

}

输出的顺序时确定的，就是插入的顺序。

2 1 3 5 4

6. 性能测试

下面的代码测试了以上三个类的 add () 方法的性能。

publicstaticvoidmain(String[] args) {

Random r =newRandom();

HashSet<Dog> hashSet =newHashSet<Dog>();

TreeSet<Dog> treeSet =newTreeSet<Dog>();

LinkedHashSet<Dog> linkedSet =newLinkedHashSet<Dog>();

// start time

longstartTime = System.nanoTime();

for(inti =0; i <1000; i++) {

intx = r.nextInt(1000-10) +10;

hashSet.add(newDog(x));

}

// end time

longendTime = System.nanoTime();

longduration = endTime - startTime;

System.out.println("HashSet: "+ duration);

// start time

startTime = System.nanoTime();

for(inti =0; i <1000; i++) {

intx = r.nextInt(1000-10) +10;

treeSet.add(newDog(x));

}

// end time

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("TreeSet: "+ duration);

// start time

startTime = System.nanoTime();

for(inti =0; i <1000; i++) {

intx = r.nextInt(1000-10) +10;

linkedSet.add(newDog(x));

}

// end time

endTime = System.nanoTime();

duration = endTime - startTime;

System.out.println("LinkedHashSet: "+ duration);

}

从输出看来，HashSet 是最快的：

HashSet: 2244768

TreeSet: 3549314

LinkedHashSet: 2263320

* 这个测试并不是非常精确，但足以反映基本的情况。

关于HashSet,TreeSet和LinkedHashSet的区别和hashset和treeset的区别和联系的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于5.Java集合框架剖析之 Hashset和LinkedHashSet源码剖析、HashMap,HashTable和TreeSet,HashSet的区别、HashSet vs TreeSet vs LinkedHashSet在添加重复值的基础上、HashSet vs. TreeSet vs. LinkedHashSet等相关内容，可以在本站寻找。

本文标签：