Java-57 集合框架

集合框架Collections Framework

集合框架介绍

1 什么是集合框架

集合框架是关于实现在内存中如何存储、组织和访问数据的、在JDK中被广泛使用的API。

集合框架包含一组接口，对不同类型容器的存储数据的不同方式建模。集合框架也包含每个接口对应的至少一个实现类。

2 如何选择集合框架中的接口和实现类

1) 选择正确的接口，要知道你的应用需要什么功能：

• 存储对象并遍历它们？
• 将对象push到队列并pop它们？
• 用key来找到它们？
• 通过索引来访问它们？
• 对它们排序？
• 防止出现重复或null值？

2) 选择正确的实现，要知道你需要如何使用这些功能：

• 访问对象是通过遍历还是随机索引来完成的？
• 对象是否在应用程序启动时固定，并且在生命周期内不会发生太大的变化？
• 在大量检查特定对象是否存在的情况下，对象的数量是否很重要？
• 需要存储对象的结构是否将被并发访问？

集合框架对所有这些问题都有解决方法。

3 集合框架的三大部分

1) 2大类接口
集合框架中有2大类接口：collections和maps。

collections是关于存储对象并遍历它们的一类接口。
Collection接口是这类接口的root接口。

实际上，Collection接口是Iterable接口的子接口，但Iterable接口不属于集合框架。

maps是关于存储对象及代表该对象的key的一类接口，简单地说，maps存储key-value对。

Map是这类接口的root接口。

Collection层次结构和Map层次结构的接口之间没有直接关系。

2) 队列和栈
在Collection层次结构中有建模队列和栈的接口。

队列和栈实际上并不是关于对象的遍历，但由于它们在Collection层次结构中，因此可以对它们进行遍历。

3) Iterator
Iterator是关于元素遍历的接口。
一个Iterator是一个能够遍历一堆对象的对象，属于集合框架。

4 相比于数组，集合的优势

1) 集合能够跟踪其包含的元素的数量；
2) 集合的容量不是固定的；
3) 集合可以控制存储的数据，比如可以防止添加null元素；
4) 集合可以查询给定元素是否存在；
5) 集合提供更多相关的高效操作；
6) 集合可以存储无序、不重复的数据。

5 集合框架总体层次结构（仅涉及要学习的内容）

Collection接口

1 Collection接口

Collection接口是指java.util Interface Collection<E>，它建模一般的集合，能够存储元素并提供不同的方式来检索元素。

Collection接口是集合框架中collections层级结构的root接口，也就是说，collections层次结构中的所有结构都继承Collection接口的方法，并且Collection接口的方法都非常常用，因此有必要重点学习。

2 Collection接口中的抽象方法（目前不涉及没学习到的内容相关的方法）

1) 对单个元素进行处理的方法

• 增：boolean add(E e)：这里泛型E可暂且理解为Object类型。该方法添加指定对象e到对应的Collection对象中，添加成功返回true，否则返回false。这里添加成功的含义是：对应Collection对象因该方法而发生改变。
  
  
  
• 删：boolean remove(Object o)：该方法删除对应Collection对象中的指定对象o，删除成功返回true，否则返回false。这里删除成功的含义是：对应Collection对象因该方法而发生改变。如果对应Collection对象中有多个指定的对象o，只会删除第一个。
  该方法是根据指定对象的o的equals方法来检索对应Collection对象中是否存在指定对象，换句话说，该方法对于重写过equals方法的对象操作，就是根据内容来进行删除，否则就是根据地址来进行删除。因此，一般对于要作为Collection中的对象的对象对应的类，应该重写equals()方法。
  
  
• 查：boolean contains(Object o)：该方法查找对应Collection对象中是否存在指定对象o，存在返回true，否则返回false。该方法也是根据指定对象的o的equals方法来检索对应Collection对象中是否存在指定对象。
  
  

2) 对另一个Collection对象进行处理的方法

• 并集(增)：boolean addAll(Collection<? extends E> c)：该方法将指定Collection对象中的所有元素增加到对应Collection对象中，只要改变了对应Collection对象则返回true，否则返回false。
  
  
• 差集(删)：boolean removeAll(Collection<?> c)：该方法删除对应Collection对象中存在的指定的Collection对象中存在的所有元素，只要改变了对应Collection对象则返回true，否则返回false。
  
  
• 交集(改)：boolean retainAll(Collection<?> c)：该方法将对应Collection对象中与指定Collection对象的相同元素保留，而删除与指定Collection对象的不相同的元素，只要改变了对应Collection对象则返回true，否则返回false。
  
  
• 查：boolean containsAll(Collection<?> c)：该方法查找对应Collection对象中是否存在指定Collection对象中的所有元素，存在则返回true，否则返回false。
  
  
• 是否相等：boolean equals(Object o)：该方法是指定的参数一般是指Collection类型的对象，就是比较两个Collection对象是否相等，相等的含义针对不同的具体Collection不同，比如List对象，还会对元素顺序进行比较。
  
  

3) 对Collection自身的处理

• 元素个数：int size()：该方法返回对应Collection对象中的元素个数。
  
  
• 是否为空：boolean isEmpty()：该方法判断对应Collection对象中的元素个数是否为0，是则返回true，否则返回false。
  
  
• 清空元素：void clear()：该方法将对应Collection对象中的元素全部清空，即使对应Collection对象中的元素个数为0。
  
  
• 遍历元素：Iterator<E> iterator()：该方法会生成对应Collection对象对应的Iterator对象，可以利用对应的Iterator对象来遍历对应的Collection对象中的元素。具体可参考后续关于Iterator的学习。
  

4) Collection转换为Array处理

• Object[] toArray()：该方法将对应Collection对象转换为包含其所有元素的Array对象。
  
  

3 遍历Collection

1) 使用Iterator遍历Collection
Iterator是接口，是指java.util Interface Iterator<E>，其对应对象称为迭代器，是用于遍历Collection的一种方式。

Collection接口是Iterable接口的子接口，因此继承了其iterator()方法，该方法能够生成对应Collection对象对应的Iterator对象，即迭代器。也就是说，collections层次结构的所有接口都有该方法，都能利用对应的iterator对象来进行遍历。

理解Iterator对象：
一个集合生成对应的Iterator对象，相当于生成了一个指向自身的第一个元素前的指针，通过该指针能够遍历自身元素，具体地，hasNext()方法能够判断当前位置的下一个位置是否存在可遍历的元素，next()方法首先推进指针到下一个位置，然后对当前位置的元素进行遍历，即返回当前位置的元素。

使用Iterator遍历涉及Iterator接口中的以下方法：

• 查看是否具有下一个元素：boolean hasNext()：该方法会判断对应集合当前位置的下一个位置是否存在可遍历的元素。
  
• 推进到下一个元素进行遍历：E next()：该方法会返回下一个元素。
  
• 删除当前遍历的元素：default void remove()：该方法会将当前遍历的位置的元素进行删除，即会改变集合。对于不可变的结构进行该操作，会报错。
  

使用Iterator对象进行遍历：

• 首先对要遍历的集合使用其iterator()方法，生成对应的Iterator对象，即迭代器；
  注意，每调用一次iterator()方法就会生成一个新的对应的迭代器。
• 迭代器生成时，其游标默认指向对应集合的第一个元素的前一个位置；
• (可选操作)在遍历对应集合的每个元素之前，可以使用对应迭代器的hasNext()方法判断下一个位置是否存在可遍历的元素；
• 使用对应迭代器的next()方法推进当前迭代器的游标，遍历下一个位置的元素；
• 当对应迭代器游标已经指向最后一个元素，还使用next()方法时，会报NoSuchElementException异常，此时该迭代器游标就停在最后一个元素位置。如果想重新遍历，需要使用一个新的迭代器。

示例：

2) 使用foreach遍历Collection
JDK5.0新增了foreach遍历模式，能够用来遍历Collection和数组，其底层仍然是使用Iterator。

使用foreach遍历Collection的格式为：for(遍历的元素类型 局部变量名：要遍历的Collection){}，冒号前面部分相当于定义一个装要遍历的元素的局部变量，冒号后面的部分为要遍历的Collection或数组。

示例：

List接口

1 List接口介绍

List是Collection的子接口，指的是java.util Interface List<E>，是关于存储有序、可重复的数据。因此，一般使用List作为数组Array的替代，List可以看作是“动态的数组”。

List与一般的集合(Collection)相比，多了两个特性：

• 有序。有序是指每个元素的存储是按照每个元素被add进List的顺序顺序存储的。具体表现为，每次对List中元素的遍历，顺序都是一样的，并且该顺序是遵循每个元素被add进List时的顺序。
• 有索引。每个元素都有自己的索引。

List的实现类主要有三个：ArrayList, LinkedList和Vector。（Vector相对过时了，基本不用，因此这里不做过多讨论。）

2 ArrayList，LinkedList和Vector

• ArrayList：是List的主要实现类，底层是由数组实现的，是线程不安全的因此效率相对高；

  • 源码分析：

    • jdk7时，ArrayList在使用无参构造器实例化时，是初始构造一个大小为10的数组，后续由于add操作需要扩容时，默认是扩容到原来数组大小的1.5倍，如果默认扩容仍不能满足所需要的大小，则扩容到所需要的大小。极端情况就是扩容的所需大小超过了预设的最大容量。
    • jdk8时，ArrayList在使用无参构造器实例化时，初始构造的是一个空数组，初次add操作会初始构造一个大小为10的数组，后续由于add操作需要扩容时，操作与jdk7一致。
    • 总结：jdk7的初始化数组操作类似于单例模式中的饿汉式，而jdk8的初始化数组操作类似于单例模式的懒汉式。jdk8实现了优化，具体地就是，延迟了数组的构建，节省了内存。由于扩容会影响效率，在实际开发中，建议尽量使用ArrayList的带参构造器，即指定初始容量的构造器。

• LinkedList：底层是双向链表实现的，是线程不安全的因此效率相对高；

  • 源码分析：底层就是基于双向链表的操作。
• Vector：底层是由数组实现的，但是线程安全的，因此效率相对低。

3 List实现类的选择

对List实现类的选择，主要是：ArrayList或LinkedList。

如果不确定选择哪一个，最好就选择ArrayList，主要原因如下：

• 遍历元素以及用索引来访问元素，是ArrayList相比于LinkedList的优势。
• 虽然LinkedList在插入和删除元素的操作上效率更高，但现代硬件、CPU缓存和指针跟踪极大地削弱了链表这方面优于数组的能力。

更适合选择LinkedList的场景：

• LinkedList相比于ArrayList，访问第一个和最后一个元素的能力更强，即效率更高，因为LinkedList底层存储数据的链表结构有专门保存指向第一个元素和最后一个元素的指针。因此，如果应用程序需要后进先出(LIFO)堆栈，或先进先出(FIFO)等待队列，那么选择链表可能最佳选择。

4 List方法

List在Collection基础上，扩展了一些专门针对索引index的方法：

• void add(int index, E element)：该方法将指定元素插入到指定索引上。
  
  
• boolean addAll(int index, Collection<? extends E> c)：该方法将指定集合的所有元素插入到指定索引上。
  
  
• E get(int index)：该方法获取指定索引上的元素。注意，List对象与数组不同，虽然都有索引，其无法通过对象名[索引]的方式访问对应索引元素，而要通过该方法。
  
  
• E set(int index, E element) ：该方法将指定索引位置的元素替换为指定元素，并返回被替换的元素。
  
  
• E remove(int index)：该方法将指定索引位置的元素删除，并返回删除的元素。
  
  
• int indexOf(Object o)：该方法将从对应List对象中查找指定元素，找到则返回第一次出现该元素的索引，否则返回-1。
  
  
• int lastIndexOf(Object o)：是indexOf方法的从最后一个元素开始查找的版本。该方法将从对应List对象中查找指定元素，找到则返回最后一次出现该元素的索引，否则返回-1。
  
  
• List<E> subList(int fromIndex, int toIndex)：该方法会返回对应List对象的从fromIndex到toIndex，左闭右开，的所有元素组成的List对象。注意，该方法并没有生成新的List对象，实际上是返回了对应List对象指定的一部分元素，换句话说，对返回的List对象的改变会影响到原List对象，反之亦然。
  因此，如果想要清空对应List对象的一部分，可以使用代码：list.subList(from, to).clear();。
  
  

5 遍历List

对List对象中的元素的遍历，相比于Collection，除了能够使用Iterator和foreach方式，List还新增了一种方式，即使用ListIterator。

List存在两个构建对应ListIterator的方法：

• ListIterator<E> listIterator()：空参方法，该方法构造对应List对象对应的ListIterator对象，游标默认指向第一个位置的前一个位置。
  
• ListIterator<E> listIterator(int index)：该方法构造对应List对象对应的ListIterator对象，游标指向指定索引位置，参数index的有效范围为：0 < index < size()，这意味着可以指向最后一个位置的后一个位置。
  

ListIterator相比于Iterator，新增了以下方法：

• hasPrevious()和previous()：这两个方法与hasNext()和next()类比，就是判断当前位置的前一个位置是否存在可以遍历的元素，以及将指针前移并遍历元素（即返回元素）。
  
  
• nextIndex()和previousIndex()：这两个方法就是返回的是下一个或上一个元素的索引。注意，该方法不会移动游标。
  
  
• set(element)：该方法能够设置当前遍历的（即当前游标指向的）元素为指定元素，即修改元素操作。
  

总结：对于List的众多方法，主要要记住的就是关于：增、删、改、查、插、长度和遍历的方法。

Set接口

1 Set接口介绍

Set接口是Collection接口的子接口，指的是java.util Interface Set<E>，是关于存储无序、不可重复的数据。

Set接口在继承Collection接口的方法的基础上，没有扩展出新的其他方法。

Set的实现类包括：HashSet, LinkedHashSet, TreeSet。

Set接口存储数据的无序、不可重复性的理解：

• 无序。无序是指元素的存储顺序不是按照元素被add进的顺序存储的。在Set中元素存储的无序性在遍历上并没有一个明显的表现，因为对于HashSet对象，遍历其对应的元素，遍历顺序不是按照add进对应对象的顺序，每次遍历的顺序都是一样的。而对于LinkedHashSet对象，遍历其对应的元素，遍历的顺序是按照add进对应对象的顺序，对于TreeSet对象，遍历其对应的元素是按照一定的比较方法排好序遍历的。

• 不可重复性。不可重复性是指，Set对象中存储的数据没有重复数据。对重复的定义在不同的实现类中是不同的：

  • 对HashSet和LinkedHashSet，两个元素如果在equals()方法下为true，则是重复的。
  • 对TreeSet，两个元素如果在对应Comparable的compareTo()方法下或者对应Comparator的compare()方法下返回0，则是重复的。
    具体参照下面对各个实现类的介绍。

2 HashSet，LinkedHashSet和TreeSet

1) HashSet
HashSet是Set的主要实现类，是线程不安全的，可以存储null值。

HashSet内部是对HashMap的实例进行了封装。

HashSet底层存储数据的结构为：数组 + 链表。

HashSet存储的元素对应的类，应该要重写对应的hashCode()和equals()方法，因为HashSet存储或者说add元素时涉及到这两个方法，具体地：

• 当add一个元素时，首先根据该元素的hashCode()方法得到该元素对应的哈希码，
• 然后，将对应哈希码按照某种算法，计算出对应的在当前HashSet中的存储位置，

• 查看当前HashSet中的该存储位置上是否已经存储了元素：

  • 如果没有存储元素，则直接将该元素存储到该位置；

  • 如果存储了元素，则查看存储了的元素的哈希码与当前要add进的元素的哈希码是否相同：

    • 如果不相同，则以链表的方式将要add进的元素链接到存储了的元素上。在jdk7中，是将要add进的元素放到当前存储位置上，再将存储了的元素链接到要add进的元素上；在jdk8中，是直接将要add进的元素链接到存储了的元素上。
    • 如果相同，则将两个元素进行equals()，如果返回true，则判定要add进的元素为重复元素，不add该元素。否则，以链表方式添加该元素到当前位置。

HashSet按Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。

hashCode()和equals()方法重写注意点：
根据上述HashSet在进行元素存储时对这两个方法的利用，可以理解到两个元素equals()返回true的前提应该是hashCode()相等，但两个元素hashCode()得到的哈希经过某种算法得到存储位置相等，不意味着两个元素哈希码相等。
简单地说，hashCode()和equals()方法重写时要注意，hashCode()和equals()方法应该是一致的。也就是说，应该满足两个不重复的元素，其对应哈希码一定不同，同样地，两个重复的元素，其对应哈希码也相同。
一般来说，直接使用快捷键自带的重写hashCode()和equals()方法。

2) LinkedHashSet
LinkedHashSet是HashSet的子类，遍历其内部元素时，能够实现按照元素被add进的顺序遍历。

LinkedHashSet与HashSet类似，区别在于LinkedHashSet底层存储数据时，每个数据都有两个引用，分别引用该数据的前一个数据和后一个数据，前一个数据是指在当前数据前一个被add进的数据，后一个数据是指在当前数据后一个被add进的数据，这就是LinkedHashSet能够实现顺序遍历的原因。

本质上，仍然是存储着无序、不可重复的数据。

3) TreeSet
TreeSet是SortedSet和NavigableSet接口的实现类，SortedSet和NavigableSet接口都是Set接口的子接口。这里目前只讨论SortedSet。

TreeSet实现类存储数据的底层结构是红黑树，红黑树结构是二叉树结构，对于每个根节点元素，左孩子节点是比根节点元素小的元素，右孩子节点是比根节点元素大的元素。

TreeSet和后面要讲的TreeMap采用红黑树的存储结构，特点是有序，查询速度比List快。

SortedSet接口使得元素能够按照某种比较逻辑进行排序，具体实现：

• 在构建TreeSet时，提供Comparator，即重写对应的compare()方法，TreeSet有传入Comparator对象作为参数的构造器；
• 或者对TreeSet存储的元素对应的类实现对应的Comparable，即重写对应的compareTo()方法；
• 如果TreeSet存储的元素对应的类既实现了对应的Comparable，又在构建对应TreeSet时，提供Comparator，这时优先使用Comparator的比较逻辑。

在TreeSet中存储不重复元素时，对重复的定义不同于HashSet和LinkedHashSet，即不是看equals()方法的返回值，而是看其比较逻辑，即此时对应的Comparable的compareTo()方法或者对应的Comparator对应的compare()方法的返回值是否为0，为0则表示是重复数据，否则不是重复数据。

因此，对于TreeSet中存储的元素，要么定义了自然排序，要么提供定制排序，否则会报错。同时，要求存储到同一个TreeSet中的元素是可比的，具体地：

• 如果使用自然排序，那么TreeSet中存储的元素必须是相同类型的，之所以不能对compareTo()方法改动为多个类型可比较，因为只有自定义的类可以修改其对应的compareTo()方法，而Java中预定义的类无法修改其内部的compareTo()方法，即使自定义的类其对应的compareTo()方法能够与其他类型进行比较，Java中预定义的类其对应的compareTo()方法却无法与其他类型进行比较。
• 如果使用定制排序，那么TreeSet中存储的元素要么是相同类型的，要么compare()方法使得对应不同类型可比较。
  
  
  

SortedSet接口为Set接口新增了以下方法，即TreeSet具有以下新方法：

• public E first()：返回最小元素。
  
  
• public E last()：返回最大元素。
  
  
• headSet(toElement) and tailSet(fromElement)：返回小于toElement的元素组成的子集，或者返回大于等于fromElement的元素组成的子集。
  
  
• subSet(fromElement, toElement)：返回大于fromElement并小于toElement的元素组成的子集，左闭右开。
  

注意，以上三个返回子集的方法并没有生成新的SortedSet，只是主SortedSet对象一部分元素的展示，也就是说，对这些子集的改变，会导致主SortedSet对象中元素的改变。
因此，可以利用上述三个子集相关方法来改变主SortedSet对象中的元素。

Map接口

1 Map接口的介绍

Map接口是指java.util Interface Map<K,V>，是maps层次结构的root接口，它建模key-value对集合。

Map接口的实现类包括：

• HashMap：是Map接口的主要实现类，是线程不安全的，能够存储key或value为null的数据。
  HashMap的底层：1)在jdk7及以前，为数组+链表；2)在jdk8及之后，为数组+链表+红黑树。
• LinkedHashMap：是HashMap的子类，能够按照元素添加的顺序遍历元素。
  LinkedHashMap的底层：其在HashMap基础上，存储每个元素的结构都有两个指针，一个指向当前元素前一个添加进的元素，一个指向当前元素后一个添加进的元素。
  正是由于LinkedHashMap存储的数据都有两个指针分别指向前后元素的特点，使得在频繁遍历元素的场景下，其效率高于HashMap。
• TreeMap：能够按照一定的比较逻辑，对添加的key-value元素进行排序，实现排序遍历。排序针对的是key，因此考虑的是key的自然排序或定制排序。
  TreeMap底层：红黑树。
• Hashtable：是线程安全的，效率相对较低，不能存储key或value为null的数据。
• Properties：是Hashtable的子类，其key和value为String类型，常用于处理配置文件。
  
  

对Map存储的key-value对的理解：

• Map接口存储的数据是key-value对；
• Map接口中的一对key-value构成了该Map的一个entry对象；
• 一个key只能对应一个value；
• 同一个value可以对应多个key；
• Map中的key是无序、不可重复的，对应于Set结构来存储；
• Map中的value是无序、可重复的，对应于Collection结构存储
• Map中的key-value对，或者说entry是无序、不可重复的，对应于Set结构存储。

2 HashMap的底层实现原理

1) HashMap源码中的重要常量

2) jdk7及之前

• 首先实例化HashMap，既可以通过空参构造器直接实例化HashMap，也可以通过参数指定capacity或者也同时指定loadfactor来实例化HashMap：

  • a.确定要构建的底层数组的大小：源码显示是根据initialCapacity局部变量来确定的，而initialCapacity的值的确定存在两种情况：1)对于空参构造器实例化HashMap，initialCapacity的值为16；2)对于指定capacity实例化HashMap，那么initialCapacity的值为指定的值。
    根据不同构造器使用情况初步确定了initialCapacity后，还需考虑特殊情况，按照以下算法最终确定initialCapacity：

    • 如果initialCapacity的值非法，比如小于0，则报错；
    • 如果initialCapacity的值大于预设的最大值，则initialCapacity的值更新为预设的最大值；
      最终确定initialCapacity的值后，根据initialCapacity的值，计算出大于或等于该值的2次幂对应的值，以该2次幂的值作为要构建的底层数组的大小。
      总的来说，就是两种情况：
    • 如果以空参构造器实例化HashMap，构建的底层数组的大小为预设的默认大小16；
    • 如果指定capacity实例化HashMap，假设指定值合法，构建的底层数组的大小为大于或等于该指定值对应的2次幂对应的值。

  • b.确定填充因子：源码显示根据loadfactor局部变量来确定，而loadfactor的值的确定存在两种情况：1)对于空参构造器实例化HashMap，loadfactor的值为0.75；2)对于指定loadfactor实例化HashMap，那么loadfactor的值为指定的值。
    根据不同构造器使用情况初步确定了loadfactor后，分两种情况确定填充因子的值：

    • 如果loadfactor的值非法，比如小于等于0，则报错；
    • 如果loadfactor的值合法，则直接作为填充因子的值。
  • c.确定临界容量：容量和填充因子确定后就可以确定临界容量，临界容量 = 容量 * 填充因子。极端情况下，根据容量和填充因子得出的临界容量比预设的最大容量+1还大，此时临界容量 = 预设的最大容量 + 1。
  • d.构建对应HashMap的底层数组：确定了容量可以直接构建对应的底层数组，其类型为Entry。
    

• 然后对实例化的HashMap进行添加key-value操作，即put()方法对应的操作：

  • a.首先如果key的值为null，如果本来不存在key为null的元素，则直接添加，如果已存在，则直接对key为null的元素的value更新为当前put的value。可以简单地都理解为，添加的key-value不管是否重复，以最新的为准。

  • b.如果key的值不为null，则调用对应的hashCode()方法得到对应的哈希码，再根据其哈希码，按照一定的算法，得到确定存储位置的哈希值。根据源码可知，并不是直接根据key的hashCode()方法得到对应的哈希码来确定存储位置，而是进一步处理对应的哈希码再得到一个确定位置的哈希值。

    • 根据确定位置的哈希值，按照一定的算法，得到该key在HashMap底层数组中的存储位置。
    • 如果对应存储位置上没有存储数据，则直接添加成功；
    • 如果对应存储位置上已经存在数据（可能有多个），则比较已存在的数据和当前数据对应的哈希值是否相同：1)如果都不相同，则添加进该位置，此时是新加的数据存在当前位置，而已存在的数据以单链表的形式作为新加数据的next。2)如果存在相同，则再进行equals()比较：1)如果返回false，则同上，以单链表形式添加成功，2)如果返回true，则更新已存在的数据的value为加的数据的value，看似是更新数据，可以理解为“添加成功，以最新的为准”。
      
      

• 扩容操作，在给HashMap进行添加元素过程中，可能会触发扩容操作，每次完成添加数据之前，都会做一个扩容操作的检查，得到的结果要么是先扩容再完成添加数据，要么是不需要扩容，直接完成添加数据：

  • a.扩容的条件：根据源码可知，如果当前元素数量大于或等于临界容量，并且当前要添加的数据对应的准备存储的位置上是已经存在数据的（可以理解为完成这次添加需要生成链表），这两个条件同时满足时，就触发扩容操作。也就是说，只是达到临界容量也不一定会扩容，还要满足完成这次添加需要生成链表。
  • b.扩容操作：如果满足了扩容条件，此时会将底层数组大小扩容为原来大小的两倍。然后在扩容的数组上继续完成上添加操作，此时要根据要添加的数据已经确定的哈希值再在当前扩容的数组的基础上，按照一定的算法，再计算出一个对应于扩容后数组的哈希值，然后根据该哈希值按照一定的算法确定对应的存储位置，最后完成添加操作。
    
• 添加完成操作。完全确定要添加对应的key-value后，根据其对应的key-value、哈希值以及确定的存储位置，在底层数组对应的存储位置上存储该key-value，如果存在已有数据，再将已有数据作为新数据的next（单链表形式）。
  
• Entry元素。底层数组中每个key-value构成对应HashMap的一个Entry对象。每个Entry对象存有自己对应的key, value, hash(哈希值)和next。
  

3) jdk8
jdk8与jdk7及以前的不同：

• jdk8时，实例化HashMap并不会在刚开始就创建好底层数组，而是在首次put时，创建底层数组，默认就是大小为16的数组；
• jdk8时，Entry替换为Node，即创建的数组也为Node类型。
  
• jdk8时，底层结构为数组+链表+红黑树，当put元素时，导致数组中某一位置的链表长度大于或等于8，并且整个数组的长度大于64时，此时该位置上的所有数据就会转换为红黑树结构存储，这样存取、查询元素相比于之前仅用链表会更高效。这里的链表长度8即预设的触发转换为红黑树的条件，数组长度为64也是预设的转换为红黑树的条件，是最小红黑树大小。

3 LinkedHashMap的底层实现原理

LinkedHashMap是HashMap的子类，其特点是能够按照元素添加的顺序来遍历元素。

LinkedHashMap在底层上与HashMap的区别在于，其存储每个元素的结构多了两个指针，一个指向该元素前一个被添加的元素，另一个指向该元素后一个被添加的元素，正是这两个指针，使得LinkedHashMap具有按照元素添加顺序顺序遍历元素的特点。

在HashMap中，存储一对key-value的是一个Node对象，在进行put操作时，会将确定要put进的元素生成其对应的Node对象，再将对应Node对象添加进对应的存储位置。

在LinkedHashMap中，存储一对key-value的是一个Entry对象，该对象是在继承了HashMap的Node对象基础上多了两个属性before, after，分别用来保存对应元素的前一个元素和后一个元素。
在进行put操作时，会将确定要put进的元素生成其对应的Entry对象，并调整原有元素以及添加进的元素的before和after，从而完成元素与元素之间按照添加顺序的link。

4 Map中的常用方法

1) 增加（修改）

• V put(K key, V value)：该方法将指定的key-value对添加到对应的Map中，如果对应Map中已经存在指定的key对应的key-value元素，则用新的value更新已存在的value。该方法会返回之前的value，也就是说，如果对应Map中本来不存在指定key对应的元素，则返回null，否则返回原value。
  
  
• void putAll(Map<? extends K,? extends V> m)：该方法将指定的Map中的所有key-value元素添加到对应的Map中，等同于将指定的Map中的每个key-value元素依次put进对应的Map中。
  
  
• default V putIfAbsent(K key, V value)：java8引入的方法，该方法会将指定的key对应的值为null的value更新为指定的value。换句话说，只有当指定key在对应Map中不存在，或者指定key在对应Map中的对应的value值为null时，该操作才会有效，即更新对应的value值。该方法会返回指定key的原value值，即如果更新成功则返回null，否则返回对应的非null的value。
  
  

2) 删除

• V remove(Object key)：该方法会删除对应Map中指定key对应的元素，即key-value对。该方法会返回指定的key在Map中对应的value。
  
  
• default boolean remove(Object key, Object value)：java8引入该重载方法，因为有可能你不知道你要删除的key对应的value。该方法会删除对应Map中指定的key-value对。
  
  
• void clear()：该方法会清空对应Map中的所有元素。
  
  

3) 查找

• 根据key查询对应的value：

  • V get(Object key)：该方法会返回对应Map中指定key对应的value。
    
    
  • default V getOrDefault(Object key, V defaultValue)：java8引入，该方法能够返回指定key对应的value，如果对应Map中不存在该指定的key对应的元素，此时会返回指定的默认defaultValue。
    
    

• 查询指定的key或value是否存在：

  • boolean containsKey(Object key)：该方法判断对应Map中是否存在指定的key对应的元素。
    
    
  • boolean containsValue(Object value)：该方法判断对应Map中是否存在指定的value对应的元素。
    
    

• 查询对应Map的内容：

  • boolean isEmpty()：该方法判断对应Map中元素数量是否为0。
  • int size()：该方法返回对应Map中存储的元素数量，即key-value对对数。

4) 得到对应Map的Keys, Values或Entries的视图：

• Set<K> keySet()：得到对应Map对应的所有key组成的Set。可以通过该方法来遍历对应Map的所有key。注意，该方法并没有生成一个Set对象，返回的只是对应Map中的一部分对应的视图，因此原Map或该返回值进行改变会互相影响。
  可以利用该方法的返回值来改变原Map，但只支持删除操作，不支持增加操作，如果进行增加操作会报错UnsupportedOperationException。
  
  
  
• Collection<V> values()：得到对应Map对应的所有value组成的Collection。可以通过该方法来遍历对应Map的所有value。注意，该方法并没有生成一个Collection对象，返回的只是对应Map中的一部分对应的视图，因此原Map或该返回值进行改变会互相影响。
  可以利用该方法的返回值来改变原Map，但只支持删除操作，不支持增加操作，如果进行增加操作会报错UnsupportedOperationException。
  
  

注意，keySet()和values方法对一个Map操作，返回的key的集合和value的集合的顺序是一致的，即一一对应的。

• Set<Map.Entry<K,V>> entrySet()：该方法会返回对应Map对应的所有key-value组成的Set。在任何Map实现类中对应的key-value存储的结构，比如Node或者Entry都是实现了Map中的Interface Map.Entry<K,V>接口，即每个key-value都是Map.Entry对象。而Map.Entry存在getKey()和getValue()方法来得到对应Map.Entry对象的key和value。
  可以通过该方法得到的Set来实现对Map中元素的遍历。
  另外，该方法和keySet()和values()具有相同的注意点。
  
  
  
  

5 TreeMap

TreeMap是SortedMap的实现类，其特点是能够按照一定的比较逻辑对Map中的元素进行比较排序，按照比较结果，实现排序遍历。

TreeMap对元素进行比较，比的是key-value对的key，因此要求TreeMap中的元素对应的key必须是可比较的，一般来说，就是同一类型的。注意，TreeMap无法针对元素的value进行排序。

另外，使用TreeMap必须提供对应的比较逻辑，存在两种方式实现：

• TreeMap中key-value的key对应的类实现了Comparable接口，即重写了对应的compareTo()方法，这就是提供了自然排序逻辑；
• 创建带有Comparator的TreeMap，即使用带有Comparator参数的TreeMap对应的构造器，这就是提供了定制排序；
• 如果既存在自然排序逻辑，又存在定制排序逻辑，此时以定制排序逻辑为准。

示例：

• 当User类没有实现Comparable接口，且创建的TreeMap没有Comparator参数：
  
• 当User类实现了Comparable接口，创建的TreeMap没有Comparator参数：
  
  
• 当创建的TreeMap有Comparator参数：
  
  

6 Properties

Properties是Hashtable的子类，用于处理属性文件。由于属性文件中的key, value都是字符串类型，因此Properties里的key和value都是字符串类型。

存取数据时，建议使用setProperty(String key, String value)和getProperty(String key)方法。

示例：

Collections工具类

Collections工具类提供了专门操作或者返回集合(Collection或Map)的静态方法。

1) 其中常用方法如下：

• public static void reverse(List<?> list)：该方法会将指定的List中的元素进行逆序处理。
  
  
• public static void shuffle(List<?> list)：该方法会将指定的List中的元素进行随机打乱处理。
  
• public static <T extends Comparable<? super T>> void sort(List<T> list)：该方法会将指定的List中的元素按照其自然排序逻辑进行排序。
  
• public static <T> void sort(List<T> list, Comparator<? super T> c)：该方法会将指定的List中的元素按照指定的定制排序逻辑进行排序。
  
• public static void swap(List<?> list, int i, int j)：该方法会将指定的List中指定两个索引位置的元素进行交换。
  
• public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)：该方法会返回指定Collection中的按照元素自然排序逻辑的最大元素。
  
• public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)：该方法会返回指定Collection中的按照定制排序逻辑的最大元素。
  
• public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)：该方法会返回指定Collection中的按照元素自然排序逻辑的最小元素。
  
• public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)：该方法会返回指定Collection中的按照定制排序逻辑的最小元素。
  
• public static int frequency(Collection<?> c, Object o)：该方法会返回指定Collection中指定元素的出现次数。
  
• public static <T> void copy(List<? super T> dest, List<? extends T> src)：该方法会将指定的List复制到另一个指定的List中。注意该方法并没有生成List，可以理解为用指定List的所有元素，替换另一个指定List中的元素，因此该方法要求目标Listdest本身的size即包含的元素数，要比被复制的Listsrc的size大或者相等。
  
  
• public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)：该方法会将指定List中指定的元素，全部（可能有多个）替换为指定的新元素。
  

Collections还有许多其他操作集合或者返回集合的方法，之后需要操作集合或者返回集合可以先去Collections中查阅是否存在相关API直接使用。

2) Collections还提供了得到Collection和Map一些线程不安全的实现类的安全版本的方法。