HashSet、TreeSet 总结

HashSet：

1、概述：

向一个 HashSet 集合中存入一个元素时， HashSet 会调用该对象的 hashCode（）方法得到该对象的 hashCode 值，然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。如果两个元素通过 equals（）方法比较返回 true，但它们的 hashCode 不同，HashSet 将会把它们存储在不同的位置，可以添加成功,所以， HashSet 集合判断两个元素是否一样的标准是两个对象的 equals（）方法和 hashCode（）方法返回的值都相同。下面的例子可以帮我们验证：

上面的例子中，类 A 重写了 equals（）方法，而且都返回 true；类 B 重写了 hashCode（）方法，都返回1；类 C 重写了 equals（）和 hashCode（）方法，返回固定值。此时，我们往 HashSet 集合中分别添加两个ABC对象然后打印出来，可以看出，里面有两个 A 对象，两个 B 对象，一个 C 对象。

不过，当我们需要把对象存入 HashSet 中，并且重写了 equals（）方法的时候，我们应该重写 hashCode（）方法，而且应该保证equals（）方法返回 true 时，hashCode（）返回值也应该相等。如果 hashCode（）方法返回值不同，两个对象就会都存储到集合中，这就与存储元素不能重复相冲突。而当 hashCode（）方法返回相同时，equals（）应该返回 true。因为 hashCode（）方法返回相同而 equals（）方法返回 false 时，两个对象会保存在同一位置，这个时候这个位置会采用链式结构保存多个对象。HashSet 访问集合元素时是根据 hashCode 值来快速定位的，如果集合中有多个元素 hashCode 相同，会影响访问性能。（HashSet 访问元素时会根据 hashCode 快速计算出该元素所在的位置，从而快速定位该元素）

2、特点：

a、不能保证元素的排列顺序，排列顺序可能和添加顺序不同，而且有可能发生变化。

b、HashSet 不是同步的，如果多个线程同时访问一个 HashSet，假设有多个线程同时修改了 HashSet 集合时，要通过代码来保证其同步。

c、集合元素可以为 null。

3、LinkedHashSet：                 

LinkedHashSet 是 HashSet 的子类。也是根据元素的 hashCode 值来决定元素的存储位置，同时它使用链表维护元素的顺序，这样我们遍历 LinkedHashSet 的时候会按照元素添加的顺序取出元素。

TreeSet：

1、概述：

TreeSet 是 SortedSet 接口的实现类。SortedSet 可以确保集合元素处于排序状态。TreeSet 是采用红黑树的数据结构来存储集合元素的。 TreeSet 支持两种排序方法：自然排序和定制排序。

从输出日志可以看出，元素并不是按照 add 的顺序排列的，是按照加入整型数据的大小排列的。

2、自然排序：

自然排序是 TreeSet 调用集合元素的 compareTo（Object object）方法来比较元素之间的大小关系，然后将集合元素按升序排列。所以，当我们采用自然排序的时候，添加到 TreeSet 的元素必须实现 Comparable 接口，而且添加元素应该是相同类型，否则会报 ClassCastException 异常。Java 中一些常用类已经实现了 Comparable 接口：BigDecimal、BigInteger、Character、Boolean、String、Date、Time等。

如图，当 compareTo 方法返回为0时，认为两个元素是相等的，不为0则不相等。所以，当我们需要把一个对象放入 TreeSet 中去，又重写该类的 equals（）方法的时候，我们应该保证在 equals（）方法返回 true 的时候，compareTo 方法返回的是0。

已经加入 TreeSet 集合的元素不要修改变量值，这容易导致一些错误。如图：

如果我们修改后导致元素相等，这个时候 TreeSet 是不会重新排序的，这个时候我们如果想删除修改后的元素会失败，而且和修改后元素相等的元素也会删除失败。不过我们可以正常删除没有改变的元素。

3、定制排序：

自然排序是根据集合元素的大小升序。如果我们想降序或者按照自己的意愿排序，我们可以通过 Comparator 接口实现。在我们创建 TreeSet 集合对象时，我们需要提供一个 Comparator 对象关联 TreeSet，实现 compare 方法。如果该方法返回正数，表示 o1 大于 o2；如果返回0，表示 o1 等于 o2；如果返回负数，表示 o1 小于 o2。如图所示：

总结：

HashSet 的性能比 TreeSet 好，特别是常用的添加、查询等操作。只有需要排序的时候，我们才使用 TreeSet。LinkedHashSet 对于普通的插入、删除操作，比 HashSet 会慢一点，但是遍历会更快。