注:以下仅个人常用集合整理,更多待后续学习整理
所有的集合类位于java.util包下,后来为了解决并发问题,Java 5 还在Java.util.concurrent包下提供了一些线程支持的集合类。
对于Set\List\Deque\Map 最常用的集合类有:
HashSet、TreeSet、ArrayList、ArrayList、ArrayDeque、LinkedList、HashMap、TreeMap
一、常用集合分类
按照实现划分,如图:
image.png按照数据结构划分,如图:
image.png下面此图来自博友:
image.png
三 、Set不能存放重复值的原因
Set 集合访问时,是通过访问元素本身来实现的。
Set本质上与Collection没有什么区别,主要在于Set不允许包含重复元素
(Set比较两个对象相等是通过equals方法比较的)
四、Set
(一)HashSet 主要特性
①不排序、不同步、元素可为 null
②HashSet 集合判断添加的元素是否包含重复是通过“equals”和“hashCode” 方法返回值来判断的,如果一个类只重写了其中某一个方法,另一个方法的返回值与之不对应,同样也会出现添加了重复元素。若多个元素的hashCode值相等,将会导致性能下降。
③采用Hash算法 决定元素的存储位置,Hash算法详见:https://www.jianshu.com/p/4cb61f333b51
③结合上述特征:所以HashSet最好用于添加不可变元素
(二)LinkedHashSet主要特征
①它是HashSet的一个“子类”,但它是使用“链表”维护元素的次序,所以这个类是按照插入的顺序存储元素的。
②需要维护元素的插入顺序,因此性能略低于HashSet。
(三)TreeSet主要特征
①SortedSet的实现类,因此可以支持排序
②采用“红黑树”来存储集合元素,支持“自然排序”和“定制排序”
③所添加的元素必须实现Comparable接口,因为TreeSet会调用集合元素的 o1.compareTo(Object o2)方法来判断大小(compareTo返回0相等,返回正数,o1大于o2,反之小于)。
④所添加元素必须是同一类型对象,否则发生ClassCastException异常。
⑤当我们重写对应类的equals方法时,必须保证compareTo方法与之对应。
⑥结合上述特征:所以TreeSet也最好用于添加不可变元素
(四)EnumSet
①专为枚举类设计的集合类,此类中所有元素都必须是指定枚举类型的枚举值
②集合元素也是有序的:以枚举值在枚举类中的定义顺序来决定集合元素的顺序。
③内部以向量的形式存储,非常紧凑、高效,占用内存小,运行效率高。
④不允许添加null元素。
各Set实现类的性能分析
①HashSet的性能总是比TreeSet性能好,特别是常用的添加、查询元素,因为TreeSet需要额外的红黑树算法来维护集合元素的次序,只有需要一个保持排序的Set时候,才使用TreeSet。否则都用HashSet。
②HashSet的子类LinkedHashSet对于普通的插入、删除操作,它比HashSet要略微慢一点,这是由于维护链表的开销造成的,不过也因为链表,遍历会更快一些。
③EnumSet是所有实现类中性能最好的,但只适用于枚举类
最后最重要的是Set的HashSet、TreeSet和EnumSet都是线程不安全的,通常可以通过Collections工具类(只是java.util包下的一个工具类)的synchronizedSortedSet方法来包装Set集合,在创建的时候执行:
SortedSet s = Collections.synchronizedSortedSet( new TreeSet( ....) );
五、List
List集合代表一个有序、可重复的集合,默认按照添加顺序设置元素的索引。
(一)List接口和ListIterator接口
①List是Collection的子接口
②与Set集合相比,List增加了根据索引来插入、替换和删除集合元素的方法。
③List集合判断两个对象相等只要通过equals方法比较返回true即可。
④与Set集合遍历方法Iterator不同的是:List集合额外提供了一个listIterator方法,继承自Iterator接口,提供专门操作List接口的方法,这个方法增加了向前迭代的功能:hasPrevious和previous,还可以add元素,Iterator只能remove删除元素。
(二)ArrayList和Vector实现类
①两者都是List的典型实现
②基于数组,所以内部封装了一个动态的、允许再分配的Object[]数组,使用initialCapacity参数来设置数组的长度,当元素超过数组长度时候,就会自动增加initialCapacity。
下面两种情况可提前指定initialCapacity提高性能:
第一添加大量元素时,第二知道元素个数的时候。
③trimToSize方法用来减少集合对象占用的多于空间,调整数组长度为当前元素个数。
④ArrayList与Vector最显著的区别在于前者是线程不安全的,但是Collections提供的一个方法能结解决这个问题,所以就性能上讲,淘汰Vector是必然的。
固定长度的List(Arrays数组工具类)
提供asList(Object......a)方法把一个数组或指定个数的对象转换成一个List对象,这个对象只是Arrays的内部类ArrayList的实例。它是一个固定长度的List集合,程序只能遍历访问该集合里面的元素,不可以增加、删除,否则应发UnsupportedOperationException异常。
*:LinkedList也是List集合的实现类,在后面Queue集合中简述。
六、Queue
Queue用于模拟队列这种数据结构
(一)PriorityQueue
①一个标准的队列实现类
②之所以称之为标准:是因为它保存队列元素的顺序并不是以加入队列的元素的顺序,而是按队列元素的“大小”进行重新排序,因袭调用peek或者poll方法取出队列中的元素时,是取出队列中最小的元素。
③不允许插入Null值
④有两种排序方式,与TreeSet有异曲同工的特点。
(二)Deque接口与ArrayDeque实现类
①Deque是Queue接口的子接口,代表双端队列
②Deque不仅可以当成双端队列使用,而且可以被当成栈来使用,因为该类包含出栈pop、push 出栈入栈两个方法。
③Deque接口提供了一个典型的实现类:ArrayDeque:基于数组实现的双端队列,创建Deque的同时同样可以指定一个numElements参数指定内部数组的长度。
④ArrayList和ArrayDeque两个集合类的实现机制基本 相似,它们的底层都采用一个动态、可重新分配的Object[]数组来存储集合元素。
⑤程序中需要使用“栈”这种数据结构时,推荐使用ArrayDeque或者LinkedList。
(三)LinkedList
①List接口、Deque接口的实现类,所以可根据索引访问元素,也可被当做双端队列来使用,自然也可以被当做“栈”来使用。
②此类与ArrayDeque、ArrayList实现机制完全不同,前者是以链表的形式保存元素,后者是数组,所以此类随机访问性能较差,但插入删除和迭代的性能非常好,原因就在于数组和链表这两种数据结构的不同。
*:对于所有基于数组实现的集合:使用随机访问的性能比使用Iterator迭代访问的性能要好。
七、Map
如果把Map的key放在一起,就组成了一个Set集合(所有的key没有顺序,不重复),keySet方法返回所有key值组成的Set对象。Set和Map关系密切。当然values方法返回所有value组成的Collection集合。
事实上,Map提供了一个Entry内部类来封装key-value对,而计算Entry存储时则只考虑Entry封装的key,从Java源码来看,Java是先实现了Map ,然后通过包装一个所有value都为null的Map就实现了Set集合。
如果把Map 里所有value放在一起看又类似于一个List,元素与元素之间可以重复,每个元素可以根据索引查找,只是Map中的索引不再使用整数值,而是以另一个对象作为索引,Map有时也被称为字典,或关联数组。
(一)HashMap 和Hashtable 实现类
①Map的典型实现类,所以大部分特性为Map特性,Hashtable从Java 1.0就开始了,目前很少使用
HashMap与Hashtable的区别?
1、Hashtable是线程安全的,所以HashMap的性能高一点
Hashtable底层是利用锁住整个操作来实现线程安全,所以在多线程情况下是串行的,这就导致了运行效率非常低。
2、Hashtable不允许使用Null值作为key,HashMap可以。
尽量少用Hashtable,即使要线程安全,也可以使用前面提到的Collections工具类的方法把HashMap变成线程安全的。
②所有的Map实现类都重写了toString 方法,调用Map对象的toString方法总是返回一个类似于json字符串的数据。
③用作key的对象必须实现hashCode方法和equals方法。
与HashSet类似的是:
④这两个都不能保证其中key-value对的顺序。
⑤判断两个key相等的标准也是:两个key通过equals方法比较返回true,两个key的hashCode返回值也相等。
⑥尽量使用不可变对象作为存储元素,若要存可变元素,也必须保证元素不要被更改,否则可能引发不必要的错误。
⑥判断两个value相等的标准更简单:只要两个对象通过equals方法比较返回true即可。
(二)LinkedHashMap
①使用双向链表来维护key-value对的次序(其实只需要考虑key的次序),该链表负责维护Map的迭代顺序,迭代顺序与key-value的插入顺序保持一致,且性能较好。
②可以避免对HashMap、Hashtable里的key-value对进行排序,同时又可以避免使用TreeMap所增加的成本。
③需要维护元素的插入顺序,因此性能略低于HashMap的性能。
(三)Properties
Properties作为Hashtable类的子类,在处理属性文件时特别方便(windows 操作平台上的ini文件就是一种属性文件,Java中的xml文件),此类可以把Map对象和属性文件关联起来,从而可以把Map对象中的key-value对写入属性文件中,也可以把属性文件中的“属性名=属性值”加载到Map对象中。
(四)SortedMap接口和TreeMap实现类
正如Set接口派生出SortedSet子接口,SortedSet接口有一个TreeSet实现类一样,Map接口也派生出SortedMap,也有一个TreeMap实现类。
①TreeMap就是一个红黑树结构,每个key-value对即为红黑树的一个节点,在存储节点时,需要根据key对节点进行排序,TreeMap是有序的。
同TreeSet类似,也有两个排序方式:
1、自然排序:所有key必须实现Compatable接口,而且所有key必须是同一个对象,否则会抛出ClassCastException异常。
2、定制排序:创建TreeMap时,传入一个Comparator对象,该对象负责对TreeMap中所有key进行排序,采用定制排序时不要求Map的key实现Comparable接口。
②判断两个key相等的标准是:两个key通过compareTo方法返回0,和equals方法返回值为true,TreeMap就认为这两个key是相等的。
③TreeMap是有序的:所以访问前一个、后一个、第一个、最后一个都有相应的API。
(五)WeakHashMap实现类与HashMap的区别
此类的key只保留了对实际对象(字符串是强引用)的弱引用,意味着当此类对象的key所引用的对象没有被其他强引用变量所引用,则这些key将可能被垃圾回收,WeakHashMap也可能自动删除这些key所对应的key-value对。
而HashMap的key保留了对实际对象的强引用,意味着只要该HashMap对象不被销毁,该HashMap的所有key所引用的对象就不会被垃圾回收,HashMap也不会自动删除这些key所对应的key-value对。
那么什么是强引用?什么是弱引用?详情见:https://www.jianshu.com/p/14a778168840
(六)EnumMap实现类
①此类中的所有key都必须是单个枚举类的枚举值,创建此类时必须显示或者隐式的指定它对应的枚举类。
②在内部是以数组形式保存的,所以这种形式非常紧凑高效。
③根据key的自然顺序来维护key-value对的顺序
④不允许使用null值作为key,但允许使用null作为value。
(七)各Map实现类的性能分析
①HashMap通常比Hashtable要快,因为Hashtable需要额外的线程同步控制。
②TreeMap通常比HashMap、Hashtable要慢(尤其是插入、删除),因为TreeMap采用红黑树来管理key-value键值对。但使用TreeMap的好处在于:TreeMap中的key-value对总是有序状态,无须专门进行排序操作,可以调用keySet(),取得key组成的Set,然后使用toArray()方法生成key的数组,接下来使用Arrays的binarySearch()方法在已 排序的数组中快速地查询对象。
③LinkedHashMap比HashMap要慢,没什么特别出色之处
④EnumMap性能最好,但是它只能使用同一个枚举类的枚举值作为key。
(八)HashSet和HashMap的性能选项
①HashSet和HashMap都是使用hash算法来决定集合中元素的存储位置(HashMap是key),来控制元素的大小(HashMap是key)
②hash表里可以存储元素的位置叫作“桶”,在通常情况下,单个“桶”中存储一个元素,此时有最好的性能。
③hash算法可以根据hashCode值计算出“桶”的存储位置,接着就可以从桶中取出元素。
④但hash表中的状态我open:在发生hash冲突的时候,单个桶会存储多个元素,这些元素就会以链表的形式存储,必须按照顺序搜索。
⑤hash表包含如下属性:
1、容量(capacity):hash表中桶的数量
2、初始化容量(initial capacity):创建hash表时桶的数量,HashMap和HashSet都允许在构造器中指定初始化容量。
3、尺寸(size):当前hash表中记录的数量。
4、负载因子(load factory):负载因子 = size/capacity,轻负载的hash表具有冲突少、适宜查询与插入的特点(但是Iterator遍历较慢)
⑥负载极限:范围0~1,决定了hash表的最大填满程度,hash表会自动成倍的增加桶的数量,称为“rehashing”,默认为0.75,也就是当该hash表的3/4被填满的时候,就会发生“rehashing”
为什么是0.75?
较高会降低hash表占用的内存空间,但会增加查询数据的时间开销,当然对于时间效率和占用内存可以根据实际情况进行调整。
最后提及一个操作集合的工具类:Collections
该工具类提供了大量的方法对集合元素进行排序、查询和修改等操作,还提供将集合设置为不可变、对集合实现同步控制等方法。具体见API文档。
(以上为纯Java集合框架必知基础,整理来源:《Java疯狂讲义》第八章 Java集合)
网友评论