Java集合框架总结

集合框架

系列文章

类图结构

在前面的系列文章中，我们主要分析了java的集合框架。Java集合框架位于Java.util包下，包含了很多常用的数据结构，如数组、链表、栈、队列、集合、哈希表等，下面我们结合类图再来回顾一下。

Map接口类图
Collection接口类图

Collection接口类图

Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些接口或实现类。Set和List接口是Collection接口派生的两个子接口，Queue是Java提供的队列实现，类似于List。Map是一个映射接口，其中的每个元素都是一个key-value键值对，抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数，TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现。另外，不常用的HashTable直接实现了Map接口。对于Set、List和Map三种集合，最常用的实现类分别是HashSet、ArrayList和HashMap三个实现类。

总结

Map 接口

Map是一个映射接口，其中的每个元素都是一个key-value键值对，抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数，HashMap、LinkedHashMap、 TreeMap等实现类都通过继承AbstractMap实现。

HashMap

HashMap采用了hash表数据结构来实现，其内部维护的数组+单链表+红黑树的结构实现了基于哈希表的存储结构。在key未发生冲突的情况下，搜索时间复杂度为O(1)，可以快速定位元素。存储时，根据key的哈希值决定元素存放的位置，采用链地址法解决hash冲突，当单链表长度超过8时，单链表转为红黑树。
1.HashMap是不保证存取的顺序性的，也就是说遍历HashMap的时候，得到的元素的顺序与添加元素的顺序是不同的。
2.HashMap的key不允许重复，至多允许一个key为null，任意key对应的vlue都可以为null。
3.HashMap不是线程安全的。
4.HashMap常被用作映射存储容器、简单缓存对象等。

LinkedHashMap

LinkedHashMap直接继承自HashMap，大部分常用的方法都是复用的HashMap的方法，重写了其中的某些方法，与HashMap最大的不同是LinkedHashMap保证了元素的顺序性，其内部使用双向链表结构实现。基于双向链表的数据结构使LinkedHashMap拥有了顺序访问元素的能力，但是由于维护了元素的顺序性，在插入元素时速度要比HashMap慢一些。
1.LinkedHashMap保证元素顺序性。
2.LinkedHashMap的key不允许重复，至多允许一个key为null，任意key对应的vlue都可以为null。
3.LinkedHashMap不是线程安全的。

TreeMap

TreeMap继承自AbstractMap，并实现了NavigableMap接口，AbstractMap完成了大部分map接口所支持的方法，而NavigableMap接口继承自SortedMap接口，SortedMap存储的是有序的键值对。TreeMap内部使用红黑树结构实现元素存储，红黑树属于二叉排序树的一种，所以保证了TreeMap的有序性。红黑树三个重要的操作，左旋、右旋和着色，当TreeMap的元素发生变化时，为了维持红黑树的特性，需要针对性的对元素进行左旋、右旋和重新着色。
1.TreeMap保证元素顺序性。
2.不允许插入值为null的key。
3.可以插入值为null的value。
4.若key重复，则后面插入的直接覆盖原来的value。
5.非线程安全。

Collection 接口

Collection接口是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，主要又分为两大部分：List和Set。List接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为ArrayList和LinkedList。

ArrayList

ArrayList实现了 List 接口，其内部基于数组的数据结构实现，维护了一个object类型的动态数组。object数组长度默认10，超过这个长度就需要扩容。扩容机制是根据计算出来的新的容量重新实例化一个数组，并将原来数组的内容拷贝至新的数组。如果频繁扩容的话，比较浪费空间且容易引发性能问题。
1.基于数组实现，元素有序，元素可为null、可重复。
2.动态数组，容量不够时需要扩容，扩容基于数组拷贝，不适合用于频繁增删的场景，如果可以确定数据量大小，推荐使用固定的容量实例化。
3.非线程安全。

LinkedList

LinkedList实现了List接口，并直接继承自AbstractSequentialList，AbstractSequentialList继承自AbstractList。LinkedList内部维护了一个双向链表的数据结构，LinkedList正是利用这个双向链表的数据结构实现了内部的元素存储，并通过维护一个头指针和尾指针，进行元素的增加和删除。
1.LinkedList基于双向链表结构实现存储，元素是有序的，并且元素可以为null、可以重复。
2.由于基于双向链表实现存储，增删比较快速，适用于频繁增删的场景。
3.查找比较耗时，遍历是需要注意，使用随机访问方式查找效率比较低下，需使用Iterator方式或者foreach方式遍历。
4.非线程安全，多线程环境慎用。

Set接口

Set接口通常表示一个集合，其中的元素不允许重复，常用实现类有HashSet、LinkedHashSet和TreeSet。
1.对于HashSet而言，它是基于HashMap实现的，可以看作是对HashMap的封装，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。由于底层基于HashMap实现，内部使用基于哈希表的数组+链表方式存储，所以不保证元素的存取顺序。基于key的hash值存储，同样的对象hash值相同，所以元素不可重复，但是可以为null，可以快速查找是否包含某个元素。
2.LinkedHashSet继承自HashSet，内部是基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素，其所有的方法操作上又与HashSet相同。底层存储基于LinkedHashMap实现，内部使用双向链表存储元素，所以保证了元素的顺序性。基于key的hash值存储，同样的对象hash值相同，所以元素不可重复，但是可以为null，可以快速查找是否包含某个元素。
3.TreeSet是基于TreeMap实现的有序集合，TreeSet中含有一个NavigableMap类型的成员变量m，而m实际上是TreeMap的实例。我们知道TreeMap内部是用红黑树实现元素存储从而保证元素的顺序性的，那么同理TreeSet同样也是一个有序的集合。底层存储基于TreeMap实现，内部使用红黑树结构表存储元素，所以保证了元素的顺序性。元素不可以为null。遍历时不支持随机访问，只能通过迭代器和for-each遍进行遍历。