Java基础14-集合

概述

集合框架被设计成要满足以下几个目标：

• 该框架必须是高性能的。
  基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
• 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
• 对一个集合的扩展和适应必须是简单的。

为此，整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现，诸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

从上面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器:

• 一种是集合（Collection），存储一个元素集合
• 另一种是图（Map），存储键/值对映射

Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

---

Collection

单列集合的顶层接口 , java.util包下 , 继承了Iterable接口：
public interface Collection<E> extends Iterable<E>

List

List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。
List 接口存储一组不唯一，有序（插入顺序）的对象。

特点：
1.元素有序(有序指的是存取有序)
2.可重复
3.允许多个null值

其常见实现子类有: ArrayList / LinkedList / Vector：

• ArrayList：底层实现是数组，增删慢 , 查询快
  

该类实现了List接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能
该类是非同步的
（1）ArrayList内部使用数组存储元素，默认初识容量为10，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（7）ArrayList支持求并集，调用addAll(Collection<? extends E> c)方法即可；
（8）ArrayList支持求交集，调用retainAll(Collection<? extends E> c)方法即可；
（9）ArrayList支持求单向差集，调用removeAll(Collection<? extends E> c)方法即可；

• LinkedList：底层实现是双向链表，增删快、查询慢
  该类实现了List接口，允许有null（空）元素
  该类是非同步的
  

  
  LinkedList添加元素示意图
  
  在队列首尾添加元素很高效，时间复杂度为O(1)。
  在中间添加元素比较低效，首先要先找到插入位置的节点，再修改前后节点的指针，时间复杂度为O(n)。
  LinkedList删除元素示意图
  
  在队列首尾删除元素很高效，时间复杂度为O(1)。
  在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为O(n)。

• Vector：底层实现是数组，它ArrayList基本相同，主要区别是它的线程是同步的(安全的),而ArrayList和LinkedList是非同步的(实际开发中如果使用了多线程一般方法就已经使用同步机制了，例如同步锁，所以不推荐使用Vectoer)

常用API

返回值	方法	描述
boolean	add(E e)	向列表的尾部添加指定的元素（可选操作）
void	add(int index, E element)	在列表的指定位置插入指定元素（可选操作）
boolean	addAll(Collection<? extends E> c)	添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序（可选操作）
boolean	addAll(int index, Collection<? extends E> c)	将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）
void	clear()	从列表中移除所有元素（可选操作）
boolean	contains(Object o)	如果列表包含指定的元素，则返回true
boolean	containsAll(Collection<?> c)	如果列表包含指定 collection 的所有元素，则返回true
boolean	equals(Object o)	比较指定的对象与列表是否相等
E	get(int index)	返回列表中指定位置的元素。
int	hashCode()	返回列表的哈希码值
int	indexOf(Object o)	返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1
boolean	isEmpty()	如果列表不包含元素，则返回true
Iterator<E>	iterator()	返回按适当顺序在列表的元素上进行迭代的迭代器
int	lastIndexOf(Object o)	返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1
ListIterator<E>	listIterator()	返回此列表元素的列表迭代器（按适当顺序）
ListIterator<E>	listIterator(int index)	返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始
E	remove(int index)	移除列表中指定位置的元素（可选操作）。
boolean	remove(Object o)	从此列表中移除第一次出现的指定元素（如果存在）（可选操作）
boolean	removeAll(Collection<?> c)	从列表中移除指定 collection 中包含的其所有元素（可选操作）
boolean	retainAll(Collection<?> c)	仅在列表中保留指定 collection 中所包含的元素（可选操作）
E	set(int index, E element)	用指定元素替换列表中指定位置的元素（可选操作）
int	size()	返回列表中的元素数
List<E>	subList(int fromIndex, int toIndex)	返回列表中指定的fromIndex（包括 ）和toIndex（不包括）之间的部分视图
Object[]	toArray()	返回按适当顺序包含列表中的所有元素的数组（从第一个元素到最后一个元素）

Set

Set 具有与 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。
Set 接口存储一组唯一，无序的对象

特点:
1.元素无序且不可重复(无序指的是存取无序)
2.无角标
3.最多允许1个null值

常用实现子类有: HashSet / TreeSet / LinkedHashSet：

• HashSet：底层数据结构是HashMap , 通过复写hashCode()方法和equals()方法来保证元素的唯一性(非同步)
  

（1）HashSet内部使用HashMap的key存储元素，以此来保证元素不重复；
（2）HashSet是无序的，因为HashMap的key是无序的；
（3）HashSet中允许有一个null元素，因为HashMap允许key为null；
（4）HashSet是非线程安全的；
（5）HashSet是没有get()方法的；

• TreeSet：底层数据结构是NavigableMap , 通过Compareable接口的compareTo()方法来保证元素的唯一性(非同步)
  

（1）TreeSet底层使用NavigableMap存储元素；
（2）TreeSet是有序的；
（3）TreeSet是非线程安全的；
（4）TreeSet实现了NavigableSet接口，而NavigableSet继承自SortedSet接口；
（5）TreeSet实现了SortedSet接口；

• LinkedHashSet：具有可预知迭代顺序的Set 接口的哈希表和链接列表实现(非同步),底层是LinkedHashMap，很少使用

常用API

返回值	方法	描述
boolean	add(E e)	如果set中尚未存在指定的元素，则添加此元素（可选操作）
boolean	addAll(Collection<? extends E> c)	如果 set 中没有指定 collection 中的所有元素，则将其添加到此set中（可选操作）
void	clear()	移除此 set 中的所有元素（可选操作）
boolean	contains(Object o)	如果 set 包含指定的元素，则返回true
boolean	containsAll(Collection<?> c)	如果此 set 包含指定 collection 的所有元素，则返回true
boolean	equals(Object o)	比较指定对象与此 set 的相等性
int	hashCode()	返回 set 的哈希码值
boolean	isEmpty()	如果 set 不包含元素，则返回true
Iterator<E>	iterator()	返回在此 set 中的元素上进行迭代的迭代器
boolean	remove(Object o)	如果 set 中存在指定的元素，则将其移除（可选操作）
boolean	removeAll(Collection<?> c)	移除 set 中那些包含在指定 collection 中的元素（可选操作）
boolean	retainAll(Collection<?> c)	仅保留 set 中那些包含在指定 collection 中的元素（可选操作）
int	size()	返回 set 中的元素数（其容量）
Object[]	toArray()	返回一个包含 set 中所有元素的数组

---

Map

双列集合的顶层接口,将键映射到值的对象。
一个映射不能包含重复的键；每个键最多只能映射一个值

HashMap(允许1个null键、多个null值)

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
它的底层实现实际是：数组+单向链表+红黑树

该类实现了Map接口，根据键的HashCode值存储数据，具有很快的访问速度，最多允许一条记录的键为null，不支持线程同步。

常用API

返回值	方法	描述
void	clear()	从此映射中移除所有映射关系
Object	clone()	返回此HashMap实例的浅表副本：并不复制键和值本身
boolean	containsKey(Object key)	如果此映射包含对于指定键的映射关系，则返回true
boolean	containsValue(Object value)	如果此映射将一个或多个键映射到指定值，则返回 true
Set<Map.Entry<K,V>>	entrySet()	返回此映射所包含的映射关系的 Set 视图
V	get(Object key)	返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回 null
boolean	isEmpty()	如果此映射不包含键-值映射关系，则返回 true
Set<K>	keySet()	返回此映射中所包含的键的 Set 视图
V	put(K key, V value)	在此映射中关联指定值与指定键
void	putAll(Map<? extends K,? extends V> m)	将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系
V	remove(Object key)	从此映射中移除指定键的映射关系（如果存在）
int	size()	返回此映射中的键-值映射关系数
Collection<V>	values()	返回此映射所包含的值的 Collection 视图

（1）HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构；
（2）HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是2的n次方
负载因子越小查找的性能就会越高，但同时额外占用的内存就会越多，如果没有特殊需要不建议修改默认值。
（3）HashMap扩容时每次容量变为原来的两倍；
（4）当桶的数量小于64时不会进行树化，只会扩容；
（5）当桶的数量大于64且单个桶中元素的数量大于8时，进行树化；
（6）当单个桶中元素数量小于6时，进行反树化；
（7）HashMap是非线程安全的容器；
（8）HashMap查找添加元素的时间复杂度都为O(1)；
使用HashMap时还需要注意一点，它不会动态地进行缩容，也就是说，你不应该保留一个已经删除过大量Entry的HashMap（如果不打算继续添加元素的话），此时它的buckets数组经过多次扩容已经变得非常大了，这会占用非常多的无用内存，不过一般也不会出现这种情况，如果遇见了，请毫不犹豫地丢掉它，或者把数据转移到一个新的HashMap。

HashTable(不允许null键和null值):

Hashtable是线程安全的
其实现方式是在对应的方法上加上synchronized关键字
效率不高,推荐使用ConcurrentHashMap
其他和HashMap相同

TreeMap(不允许null键 , 允许null值):

基于红黑树（Red-Black tree）的NavigableMap实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法(非同步)

构造方法	描述
TreeMap()	使用键的自然顺序构造一个新的、空的树映射
TreeMap(Comparator<? super K> comparator)	构造一个新的、空的树映射，该映射根据给定比较器进行排序
TreeMap(Map<? extends K,? extends V> m)	构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序 进行排序
TreeMap(SortedMap<K,? extends V> m)	构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射

常用API

返回值	方法	描述
Map.Entry<K,V>	ceilingEntry(K key)	返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null
K	ceilingKey(K key)	返回大于等于给定键的最小键；如果不存在这样的键，则返回 null
void	clear()	从此映射中移除所有映射关系
Object	clone()	返回此 <tt>TreeMap</tt> 实例的浅表副本
Comparator<? superK>	comparator()	返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null
boolean	containsKey(Object key)	如果此映射包含指定键的映射关系，则返回true
boolean	containsValue(Object value)	如果此映射为指定值映射一个或多个键，则返回 true
NavigableSet<K>	descendingKeySet()	返回此映射中所包含键的逆序 NavigableSet 视图
NavigableMap<K,V>	descendingMap()	返回此映射中所包含映射关系的逆序视图
Set<Map.Entry<K,V>>	entrySet()	返回此映射中包含的映射关系的 Set 视图
Map.Entry<K,V>	firstEntry()	返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null
K	firstKey()	返回此映射中当前第一个（最低）键
Map.Entry<K,V>	floorEntry(K key)	返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null
K	floorKey(K key)	返回小于等于给定键的最大键；如果不存在这样的键，则返回 null
V	get(Object key)	返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回 null
SortedMap<K,V>	headMap(K toKey)	返回此映射的部分视图，其键值严格小于toKey
NavigableMap<K,V>	headMap(K toKey, boolean inclusive)	返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey
Map.Entry<K,V>	higherEntry(K key)	返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null
K	higherKey(K key)	返回严格大于给定键的最小键；如果不存在这样的键，则返回 null
Set<K>	keySet()	返回此映射包含的键的 Set 视图
Map.Entry<K,V>	lastEntry()	返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null
K	lastKey()	返回映射中当前最后一个（最高）键
Map.Entry<K,V>	lowerEntry(K key)	返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null
K	lowerKey(K key)	返回严格小于给定键的最大键；如果不存在这样的键，则返回 null
NavigableSet<K>	navigableKeySet()	返回此映射中所包含键的 NavigableSet 视图。
Map.Entry<K,V>	pollFirstEntry()	移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null
Map.Entry<K,V>	pollLastEntry()	移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null
V	put(K key, V value)	将指定值与此映射中的指定键进行关联
void	putAll(Map<? extends K,? extends V> map)	将指定映射中的所有映射关系复制到此映射中
V	remove(Object key)	如果此 TreeMap 中存在该键的映射关系，则将其删除
int	size()	返回此映射中的键-值映射关系数
NavigableMap<K,V>	subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	返回此映射的部分视图，其键的范围从 fromKey 到 toKey
SortedMap<K,V>	subMap(K fromKey, K toKey)	返回此映射的部分视图，其键值的范围从fromKey（包括）到toKey（不包括）。
SortedMap<K,V>	tailMap(K fromKey)	返回此映射的部分视图，其键大于等于fromKey
NavigableMap<K,V>	tailMap(K fromKey, boolean inclusive)	返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。
Collection<V>	values()	返回此映射包含的值的 Collection 视图