Java容器学习笔记Set接口及其实现类的相关知识总结.docx

《Java容器学习笔记Set接口及其实现类的相关知识总结.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Java容器学习笔记（二）Set接口及其实现类的相关知识总结分类： Java学习 实习笔记2011-10-2100:54 652人阅读 评论(4) 收藏 举报在Java容器学习笔记（一）中概述了Collection的基本概念及接口实现，并且总结了它的一个重要子接口List及其子类的实现和用法。本篇主要总结Set接口及其实现类的用法，包括HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurr

2、ent包），CopyOnWriteArraySet（来自于java.util.concurrent包）等。 2.    Set接口及其实现类Set接口中方法清单：Set集合和List集合都存放的是单个元素的序列，但是Set集合不允许集合中有重复元素（主要依赖于equals方法）。Set接口的父接口为Collection和Iterable，直接实现该接口的子接口有SortedSet和NavigableSet。实现Set接口的重要类有HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），En

3、umSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）。在Set接口中没有新增任何方法，所有方法均来自其父接口。它无法提供像List中按位存取的方法。在数学上一个集合有三个性质：确定性，互异性，无序性。Ø  HashSet的特点、实现机制及使用方法a)     HashSet的特点：HashSet中存放的元素是无序的，底层是用HashMap实现的，其中key是要放入的元素，value是一个Object类型的名为PR

4、ESENT的常量，由于用到了散列函数，因此其存取速度是非常快的，在地址空间很大的情况下它的存取速度可以达到O(1)级。如果首先了解了HashMap的实现方法，那么HashSet的实现是非常简单的。b）HashSet的实现机制：首先需要了解一下散列或者哈希的用法。我们知道，当数据量很大时hash函数计算的结果将会重复，按照下图所示的形式进行存贮。在HashSet中有个loadFactor（负载因子），对于上图所示总共有11个位置，目前有4个位置已经存放，即40%的空间已被使用。在HashSet的默认实现中，初始容量为16，负载因子为0.75，也就是说当有75

5、%的空间已被使用，将会进行一次再散列（再哈希），之前的散列表（数组）将被删除，新增加的散列表是之前散列表长度的2倍，最大值为Integer.MAX_VALUE。负载因子越高，内存使用率越大，元素的寻找时间越长。负载因子越低，内存使用率越小，元素的寻找时间越短。从上图可以看出，当哈希值相同时，将存放在同一个位置，使用链表方式依次链接下去。（面试官问到这个问题，当时我的回答是再哈希，其实我并不知道HashSet真正是怎么实现的，我只知道在学习数据结构时学习过再哈希，就是这个哈希表很满时需要重新建立哈希表，以便于存取，因为大量的值放在一个位置上就变成了链表的查询

6、了，几乎是O(n/2)级别的，但是我没有说出来再哈希的过程，以及哈希值相同时到底如何存放，所以……~~o(>_<)o~~）。为了说明HashSet在Java中确实如上实现，下面附上JDK中两个重要方法的源码：（下面源码来自于HashMap，原因是HashSet是基于HashMap实现的）viewplainprint?1./** 1.     * Rehashes the contents of this map into a new array with a 2.     * larger capacity.  This method is called 

7、automatically when the 3.     * number of keys in this map reaches its threshold. 4.     * 5.     * If current capacity is MAXIMUM_CAPACITY, this method does not 6.     * resize the map, but sets threshold to Integer.MAX_VALUE. 7.     * This has the effect of preventing future cal

8、ls. 8.     * 9.     * @param newC