【Java基础系列教程】第十九章 Java集合框架详解

柔光的暖阳◎ 2024-04-28 13:15 98阅读 0赞

## 一、Java集合框架概述 ##

### 1.1 集合框架概述 ###

早在 JDK1.2 之前，Java 就提供了特设类。比如：Dictionary，Vector，Stack 和 Properties 这些类用来存储和操作对象组。虽然这些类都非常有用，但是它们缺少一个核心的，统一的主题。由于这个原因，使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。

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

从下面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16][]

Java集合框架（Java Collections Framework，JCF）是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。  
对外的接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象。  
实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。  
算法：是在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法，例如查找、排序等。这些算法通常是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上，算法是可复用的函数。如果你学过C++，那C++中的标准模版库（STL）你应该不陌生，它是众所周知的集合框架的绝好例子。

除了集合，该框架也定义了几个 Map 接口和类。Map 里存储的是键/值对。尽管 Map 不是集合，但是它们完全整合在集合中。

**集合框架体系如图所示**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

### 1.2 集合框架设计背景 ###

一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而Java 集合就像一种容器，可以动态地把多个对象的引用放入容器中。

数组在内存存储方面的特点：  
数组初始化以后，长度就确定了。  
数组声明的类型，就决定了进行元素初始化时的类型。

数组在存储数据方面的弊端：  
数组初始化以后，长度就不可变了，不便于扩展。  
数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。比如：同时无法直接获取存储元素的个数  
数组存储的数据是有序的、可以重复的。---->存储数据的特点单一  
  
Java 集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的关联数组。

### 1.3 集合与数组 ###

数组是程序语言中最常用的数据结构。在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来，这些按序排列的同类数据元素的集合称为数组。一个数组包含多个数组元素，这些数组元素可以是基本数据类型也可以是对象类型。  
int arr\[\] = new int\[5\]; 只能存储5个int类型的数据，基本数据类型

数组都是以下标来存储：  
class Student\{\}  
Student stus\[\] = new Student\[5\]; 只能存储5个Student类型的数据,引用数据类型

Java集合框架标准化了Java处理对象组的方式。Java集合框架在JDK1.2版本提出，在JDK1.5版本进行了修改(引入了泛型、自动装箱/拆箱以及for-each格式循环)。  
  
集合只能存储对象，对象类型可以不一样,而且长度可变，可在多数情况下使用。

**区别:**

一、数组声明了它容纳的元素的类型，而集合不声明；简而言之: 数组必须指明存储类型，但是集合可以指明也可以不指明其存储类型；(如果集合没有指明其存储类型Object，如果想要指明其存储类型，可以使用我们学过的泛型)

二、数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。而集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。

三、数组的存放的类型只能是一种（基本类型/引用类型）,集合存放的类型可以不是一种(不加泛型时添加的类型是Object)。（与Java数组不同，Java集合中不能存放基本类型数据，而只能存放对象的引用）

四、数组是java语言中内置的数据类型,是线性排列的,执行效率或者类型检查都是最快的。

### 1.4 集合的使用场景 ###

客户端和服务器数据交互；

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_11_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 2][]

## 二、集合框架层次结构 ##

### 2.1 层次图 ###

首先我们先来看看一个集合框架的总图,有一个清晰的脉络结构,非常重要,因为不管我们学习那知识点,思路很重要。说明一下颜色含义：  
黄色：代表接口；  
绿色：代表抽象类；  
蓝色：代表实现类；  
  
Java 集合可分为 Collection 和 Map 两种体系。  
Collection接口：单列数据，定义了存取一组对象的方法的集合。  
List：元素有序、可重复的集合。  
Set：元素无序、不可重复的集合。  
Map接口：双列数据，保存具有映射关系“key-value对”的集合。

核心掌握:  
6个接口: Collection接口，List接口，Set接口，Map接口，Iterator接口，ListIterator接口  
9个类: ArrayList类，LinkedList类，Vector类，HashSet类，LinkedHashSet类，TreeSet类，HashMap类，LinkedHashMap类，TreeMap类

**Collection体系结构：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 3][]

**Map体系结构：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 4][]

### 2.2 6个接口 ###

这是两个集合框架接口的总体图分为两个集合接口，分别是Collection接口和Map接口，Collection集合是单列集合，而Map集合是双列集合。

**Collection接口**

Collection 接口是集合层次结构中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List）实现。  
  
接口的定义:  
public interface Collection<E> extends Iterable<E>  
  
Iterable 接口，实现此接口允许对象成为“for-each loop”语句的目标。  
该接口里面只有一个方法，Iterator<T> iterator() 返回一个在一组 T 类型的元素上进行迭代的迭代器。

**List接口**

List 接口是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。

接口的定义:  
public interface List<E> extends Collection<E>

**Set接口**

Set 接口是无序的，不能包含重复的元素。

接口的定义:  
public interface Set<E> extends Collection<E>

**Iterator接口**

Collection所有的集合类，都依赖了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：  
1、hasNext() 是否还有下一个元素。  
2、next() 返回下一个元素。  
3、remove() 删除当前元素。

接口的定义:  
public interface Iterator<E>

**ListIterator接口**

ListIterator接口是列表迭代器，允许按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。  
  
接口的定义:  
public interface ListIterator<E> extends Iterator<E>

**Map接口**

Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。

接口的定义:  
public interface Map<K,V>

### 2.3 9个类 ###

ArrayList类，LinkedList类，Vector类都实现了List接口；  
  
HashSet类，LinkedHashSet类，TreeSet类都实现了Set接口;

HashMap类，LinkedHashMap类，TreeMap类实现了Map接口;

<table> 
 <thead> 
  <tr> 
   <th><strong>接口</strong></th> 
   <th><strong>实现类</strong></th> 
   <th><strong>是否有序</strong></th> 
   <th><strong>是否允许元素重复</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Collection</td> 
   <td></td> 
   <td>否</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>List</td> 
   <td>ArrayList</td> 
   <td>是</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>LinkedList</td> 
   <td>是</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>Vector</td> 
   <td>是</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>Set</td> 
   <td>AbstractSet</td> 
   <td>否</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>HashSet</td> 
   <td>否</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>TreeSet</td> 
   <td>是（用二叉排序树）</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>Map</td> 
   <td>AbstractMap</td> 
   <td>否</td> 
   <td>使用key-value来映射和存储数据，key必须唯一，value可以重复</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>HashMap</td> 
   <td>否</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>TreeMap</td> 
   <td>是（用二叉排序树）</td> 
   <td>使用key-value来映射和存储数据，key必须唯一，value可以重复</td> 
  </tr> 
 </tbody> 
</table>

#### 2.3.1 List 接口 ####

List是一个继承于Collection的接口，即List是集合中的一种。

List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次 + 1。和Set不同，List中允许有重复的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

**ArrayList**

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量：

private static final int DEFAULT\_CAPACITY = 10;

随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

ArrayList擅长于随机访问。同时ArrayList是非同步的。

**LinkedList**

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。  
注:LinkedList功能比ArrayList更加完善,但是不代表肯定就使用LinkedList;

由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端，节约一半时间）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：  
List list = Collections.synchronizedList(new LinkedList(…));

**Vector**

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。  
  
注: Vector基本上不用；https://www.cnblogs.com/Kinghao0319/p/14486040.html

**Stack**

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

**为什么Stack会继承自Vector？**

这是设计上典型的滥用继承的问题，Stack应该只有push，pop等和栈相关的方法，但由于继承了Vector，Stack就额外增加了一些和Vector相关的方法，比如addElement，removeElement等。

Stack应该持有Vector的一个引用对象，采用静态代理的方式来实现栈，这样就能避免原始设计上的缺陷。

#### 2.3.2 Set 接口 ####

Set是一个继承于Collection的接口，Set是一种不包括重复元素的Collection。

它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样运行null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，关于API方面。

Set的API和Collection完全一样。实现了Set接口的集合有：HashSet、TreeSet、LinkedHashSet、EnumSet。

**HashSet**

HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的。集合元素可以是null,但只能放入一个null。

它内部元素的顺序是由哈希码来决定的，所以它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。

**TreeSet**

TreeSet 是二叉树实现的，基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现，不允许放入null值。

它是使用元素的自然顺序对元素进行排序，或者根据创建Set时提供的 Comparator 进行排序，具体取决于使用的构造方法。

**LinkedHashSet**

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

#### 2.3.3 Map 接口 ####

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。

在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。

实现map的集合有：HashMap、HashTable、TreeMap、WeakHashMap。

**HashMap**

以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry\[\] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。

**HashTable**

也是以哈希表数据结构实现的，解决冲突时与HashMap也一样也是采用了散列链表的形式。  
  
HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。  
  
每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。Map是”key-value键值对”接口。 HashTable采用”拉链法”实现哈希表不过性能比HashMap要低。

**TreeMap**

有序散列表，实现SortedMap接口，底层通过红黑树实现。

### 2.4 总结 ###

1、List、Set都是继承自Collection接口，Map则不是。

2、List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）

3、Set和List对比：  
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。  
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

4、Map适合储存键值对的数据。

5、线程安全集合类与非线程安全集合类:  
LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;  
HashMap是非线程安全的，HashTable是线程安全的;  
StringBuilder是非线程安全的，StringBuffer是线程安全的。

## 三、Collection接口方法 ##

Collection 接口是 List、Set 和 Queue 接口的父接口，该接口里定义的方法既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。

JDK不提供此接口的任何直接实现，而是提供更具体的子接口(如：Set和List)实现。

在 Java5.0 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都当成 Object 类型处理；从 JDK 5.0 增加了泛型以后，Java 集合可以记住容器中对象的数据类型。

boolean add(E e)	确保此 collection 包含指定的元素（可选操作）。 
    
    	boolean addAll(Collection<? extends E> c)	将指定 collection 中的所有元素都添加到此 collection 中（可选操作）。
    
    	void clear()	移除此 collection 中的所有元素（可选操作）。 
    
    	boolean contains(Object o)	如果此 collection 包含指定的元素，则返回 true。 
    
    	boolean containsAll(Collection<?> c)	如果此 collection 包含指定 collection 中的所有元素，则返回 true。
    
    	boolean equals(Object o)	比较此 collection 与指定对象是否相等。 
    
    	int hashCode()	返回此 collection 的哈希码值。 
    
    	boolean isEmpty()	如果此 collection 不包含元素，则返回 true。 
    
    	Iterator<E> iterator()		返回在此 collection 的元素上进行迭代的迭代器。 
            
        boolean remove(Object o)	从此 collection 中移除指定元素的单个实例，如果存在的话（可选操作）。
            
        boolean removeAll(Collection<?> c)	移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。 
    
    	boolean retainAll(Collection<?> c)	仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。 
            
        int size()	返回此 collection 中的元素数。 
            
       	Object[] toArray()	返回包含此 collection 中所有元素的数组。 
            
        <T> T[] toArray(T[] a)	返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。

**示例代码：**

import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.List;
    
    /**
     * Collection接口中声明的方法的测试
     * 结论：
     * 向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals().
     */
    
    public class CollectionTest {
    
        @Test
        public void test1() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            /*Person p = new Person("Jerry",20);
            coll.add(p);*/
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
            //1.contains(Object obj):判断当前集合中是否包含obj
            //我们在判断时会调用obj对象所在类的equals()。
            boolean contains = coll.contains(123);
            System.out.println(contains);
            System.out.println(coll.contains(new String("Tom")));
            //System.out.println(coll.contains(p));//true
            System.out.println(coll.contains(new Person("Jerry", 20)));//false -->true
    
            //2.containsAll(Collection coll1):判断形参coll1中的所有元素是否都存在于当前集合中。
            Collection coll1 = Arrays.asList(123, 4567);
            System.out.println(coll.containsAll(coll1));
        }
    
        @Test
        public void test2() {
            //3.remove(Object obj):从当前集合中移除obj元素。
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            coll.remove(1234);
            System.out.println(coll);
    
            coll.remove(new Person("Jerry", 20));
            System.out.println(coll);
    
            //4. removeAll(Collection coll1):差集：从当前集合中移除coll1中所有的元素。
            Collection coll1 = Arrays.asList(123, 456);
            coll.removeAll(coll1);
            System.out.println(coll);
        }
    
        @Test
        public void test3() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //5.retainAll(Collection coll1):交集：获取当前集合和coll1集合的交集，并返回给当前集合
            /*Collection coll1 = Arrays.asList(123,456,789);
            coll.retainAll(coll1);
            System.out.println(coll);*/
    
            //6.equals(Object obj):要想返回true，需要当前集合和形参集合的元素都相同。
            Collection coll1 = new ArrayList();
            coll1.add(456);
            coll1.add(123);
            coll1.add(new Person("Jerry", 20));
            coll1.add(new String("Tom"));
            coll1.add(false);
    
            System.out.println(coll.equals(coll1));
    
    
        }
    
        @Test
        public void test4() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //7.hashCode():返回当前对象的哈希值
            System.out.println(coll.hashCode());
    
            //8.集合 --->数组：toArray()
            Object[] arr = coll.toArray();
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }
    
            //拓展：数组 --->集合:调用Arrays类的静态方法asList()
            List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
            System.out.println(list);
    
            List arr1 = Arrays.asList(new int[]{123, 456});
            System.out.println(arr1.size());//1
    
            List arr2 = Arrays.asList(new Integer[]{123, 456});
            System.out.println(arr2.size());//2
    
            //9.iterator():返回Iterator接口的实例，用于遍历集合元素。
    
        }
    }

import java.util.Objects;
    
    public class Person {
    
        private String name;
        private int age;
    
        public Person() {
        }
    
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            System.out.println("Person equals()....");
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return age == person.age &&
                    Objects.equals(name, person.name);
        }
    
        @Override
        public int hashCode() {
    
            return Objects.hash(name, age);
        }
    }

## 四、Iterator迭代器接口 ##

### 4.1 使用 Iterator 接口遍历集合元素 ###

Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。

GOF给迭代器模式的定义为：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、“空姐”。

Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。

Iterator 仅用于遍历集合，Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。

集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Collection所有的集合类，都依赖了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：  
1、boolean hasNext() 如果仍有元素可以迭代，则返回 true。  
2、E next() 返回迭代的下一个元素。  
3、void remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。

注意：  
在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。

Iterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，不是集合对象的remove方法。  
  
如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用remove都会报IllegalStateException。

**迭代器的执行原理：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 5][]

**示例代码：**

import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Iterator;
    
    /**
     * 集合元素的遍历操作，使用迭代器Iterator接口
     * 1.内部的方法：hasNext() 和  next()
     * 2.集合对象每次调用iterator()方法都得到一个全新的迭代器对象，
     * 默认游标都在集合的第一个元素之前。
     * 3.内部定义了remove(),可以在遍历的时候，删除集合中的元素。此方法不同于集合直接调用remove()
     */
    public class IteratorTest {
    
        @Test
        public void test1() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            Iterator iterator = coll.iterator();
            //方式一：
            /*System.out.println(iterator.next());
            System.out.println(iterator.next());
            System.out.println(iterator.next());
            System.out.println(iterator.next());
            System.out.println(iterator.next());
            //报异常：NoSuchElementException
            System.out.println(iterator.next());*/
    
            //方式二：不推荐
            /*for(int i = 0;i < coll.size();i++){
                System.out.println(iterator.next());
            }*/
    
            //方式三：推荐
            hasNext():判断是否还有下一个元素
            while (iterator.hasNext()) {
                //next():①指针下移 ②将下移以后集合位置上的元素返回
                System.out.println(iterator.next());
            }
    
        }
    
        @Test
        public void test2() {
    
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //错误方式一：
            // 间隔输出，每调用一次next()，游标就移到下一个元素。
            /*Iterator iterator = coll.iterator();
            while((iterator.next()) != null){
                System.out.println(iterator.next());
            }*/
    
            //错误方式二：
            //集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
            /*while (coll.iterator().hasNext()) {
                System.out.println(coll.iterator().next());
            }*/
    
        }
    
        //测试Iterator中的remove()
        //如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，
        // 再调用remove都会报IllegalStateException。
        @Test
        public void test3() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //删除集合中"Tom"
            Iterator iterator = coll.iterator();
            while (iterator.hasNext()) {
                // iterator.remove();
                Object obj = iterator.next();
                if ("Tom".equals(obj)) {
                    iterator.remove();
                    // iterator.remove();
                }
    
            }
            //遍历集合
            iterator = coll.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    }

### 4.2 使用 foreach 循环遍历集合元素 ###

Java 5.0 提供了 foreach 循环迭代访问 Collection和数组。

遍历操作不需获取Collection或数组的长度，无需使用索引访问元素。

遍历集合的底层调用Iterator完成操作。

foreach还可以用来遍历数组。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_15_color_FFFFFF_t_70_g_se_x_16][]

import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.Collection;
    
    /**
     * jdk 5.0 新增了foreach循环，用于遍历集合、数组
     */
    public class ForTest {
    
        @Test
        public void test1() {
            Collection coll = new ArrayList();
            coll.add(123);
            coll.add(456);
            coll.add(new Person("Jerry", 20));
            coll.add(new String("Tom"));
            coll.add(false);
    
            //for(集合元素的类型 局部变量 : 集合对象)
            //内部仍然调用了迭代器。
            for (Object obj : coll) {
                System.out.println(obj);
            }
        }
    
        @Test
        public void test2() {
            int[] arr = new int[]{1, 2, 3, 4, 5, 6};
            //for(数组元素的类型 局部变量 : 数组对象)
            for (int i : arr) {
                System.out.println(i);
            }
        }
    }

**练习：判断输出结果为何？**

public class ForTest {
        public static void main(String[] args) {
            String[] str = new String[]{"张三","李四","王五","马六","田七"};
            for (String myStr : str) {
                myStr = "hello";
                System.out.println(myStr);
            }
            for (int i = 0; i < str.length; i++) {
                System.out.println(str[i]);
            }
        }
    }

## 五、Collection子接口之一：List接口 ##

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组。

List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引，List关注的是索引，拥有一系列和索引相关的方法，查询速度快。因为往list集合里插入或删除数据时，会伴随着后面数据的移动，所有插入删除数据速度慢。

JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

### 5.1 List接口方法 ###

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。
    
    	void add(int index, E element)	在列表的指定位置插入指定元素（可选操作）。 
    
    	boolean addAll(int index, Collection<? extends E> c)	将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）。 
    
    	E get(int index)	返回列表中指定位置的元素。 
    
    	int indexOf(Object o)	返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。 
    
    	int lastIndexOf(Object o)	返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1。 
    
    	ListIterator<E> listIterator()	返回此列表元素的列表迭代器（按适当顺序）。 
    
    	ListIterator<E> listIterator(int index)		返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。 
    
    	E remove(int index)		移除列表中指定位置的元素（可选操作）。 
    
    	E set(int index, E element)		用指定元素替换列表中指定位置的元素（可选操作）。 
    
    	List<E> subList(int fromIndex, int toIndex)		返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分视图。

**示例代码：**

import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Iterator;
    import java.util.List;
    
    public class ListTest {
    
        @Test
        public void test3() {
            ArrayList list = new ArrayList();
            list.add(123);
            list.add(456);
            list.add("AA");
    
            //方式一：Iterator迭代器方式
            Iterator iterator = list.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
    
            System.out.println("***************");
    
            //方式二：增强for循环
            for (Object obj : list) {
                System.out.println(obj);
            }
    
            System.out.println("***************");
    
            //方式三：普通for循环
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
    
        }
    
    
        @Test
        public void test2() {
            ArrayList list = new ArrayList();
            list.add(123);
            list.add(456);
            list.add("AA");
            list.add(new Person("Tom", 12));
            list.add(456);
            //int indexOf(Object obj):返回obj在集合中首次出现的位置。如果不存在，返回-1.
            int index = list.indexOf(4567);
            System.out.println(index);
    
            //int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置。如果不存在，返回-1.
            System.out.println(list.lastIndexOf(456));
    
            //Object remove(int index):移除指定index位置的元素，并返回此元素
            Object obj = list.remove(0);
            System.out.println(obj);
            System.out.println(list);
    
            //Object set(int index, Object ele):设置指定index位置的元素为ele
            list.set(1, "CC");
            System.out.println(list);
    
            //List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开区间的子集合
            List subList = list.subList(2, 4);
            System.out.println(subList);
            System.out.println(list);
    
        }
    
        @Test
        public void test1() {
            ArrayList list = new ArrayList();
            list.add(123);
            list.add(456);
            list.add("AA");
            list.add(new Person("Tom", 12));
            list.add(456);
    
            System.out.println(list);
    
            //void add(int index, Object ele):在index位置插入ele元素
            list.add(1, "BB");
            System.out.println(list);
    
            //boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
            List list1 = Arrays.asList(1, 2, 3);
            list.addAll(list1);
    //        list.add(list1);
            System.out.println(list.size());//9
    
            //Object get(int index):获取指定index位置的元素
            System.out.println(list.get(0));
    
        }
    
    }

### 5.1 List实现类之一：ArrayList ###

ArrayList是基于数组的，在初始化ArrayList时，会构建空数组（Object\[\] elementData=\{\}）。

ArrayList 是 List 接口的典型实现类、主要实现类，本质上，ArrayList是对象引用的一个”变长”数组。

ArrayList是一个有序的，它是按照添加的先后顺序排列，当然，他也提供了sort方法，如果需要对ArrayList进行排序，只需要调用这个方法，提供Comparator比较器即可。

ArrayList的JDK1.8之前与之后的实现区别?  
JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组。  
JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组。

Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合。

@Test
    public void test1(){
        // Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合。
        // Arrays.asList(); 主要是用来把数组转换为List集合；
        List<String> list = Arrays.asList(new String[]{"x", "y", "z"}); // 把数组里面的每一个值取出来,放到一个集合里面;
        System.out.println(list.size()); // 3
    
        // 集合里面存储的都是引用类型,但是如果你传递的是一个基本数据类型的数组,它把整个数组当成了一个对象 (注意的事项一)
        List<int[]> ints = Arrays.asList(new int[]{1, 2, 3, 4, 5,});
        System.out.println(ints.size()); // 1
    
    
        List<Integer> integers = Arrays.asList(new Integer[]{1, 2, 3, 4, 5,}); // 因为数组的Integer类型,把1-5的值都自动装箱为包装类
        System.out.println(integers.size()); // 5
    
        // static <T> List<T> asList(T... a) 返回一个受指定数组支持的固定大小的列表。
        List<String> list1 = Arrays.asList("qq", "dd", "wx", "msn");
        System.out.println(list1.size()); // 4
    
        // 注意事项二
        List<Integer> integers1 = Arrays.asList(11, 22, 33, 44, 55); // 如果我们写的是可变参数,那么会把所有的类型都认为是引用类型
        System.out.println(integers1.size());
    
        // 如果以后我们想要使用集合存储固定个数的数据,可以使用asList； （注意事项三）
        list1.add("xiaoming");
        System.out.println(list1.size()); // 4
    
    }

#### 5.1.1 构造函数 ####

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

ArrayList() 构造一个初始容量为 10 的空列表。

ArrayList(Collection<? extends E> c) 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。  
  
ArrayList(int initialCapacity) 构造一个具有指定初始容量的空列表。

import java.util.ArrayList;
    import java.util.List;
    
    public class Test_ArrayList_01 {
    
        public static void main(String[] args) {
            // ArrayList() 构造一个初始容量为 10 的空列表（底层就是数组）。
            // ArrayList list = new ArrayList();   //尽量都使用上溯造型写法
            List list = new ArrayList(); 
    
            // 向集合中添加元素
            list.add("x"); 
            list.add("y"); 
            // size() 获取集合中的元素个数
            System.out.println("list集合中的元素个数是:"+list.size()); 
    
            // ArrayList(Collection<? extends E> c) 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
            // Collection -->只要是Collection的实现类都可以作为参数传递过来
            // 相当于把list里面的一个个元素放在list1里面,而不是作为整体存储的;
            List list1 = new ArrayList(list); 
            System.out.println("list1集合中的元素个数是:"+list1.size());
    
            // ArrayList(int initialCapacity) 构造一个具有指定初始容量的空列表。
            // 在特定情况下(确定存储的元素个数的时候),我们最好使用这个构造函数；比如分页的例子
            // 以后只要是传递进来的参数,都要进行判定
            List list2 = new ArrayList(20);
    
            List<String> list3 = new ArrayList<String>();
            list3.add("x");
    
            /*
    		 * Type safety: The method add(Object) belongs to the raw type List. 
    		 * References to generic type List<E> should be parameterized
    		 * 
    		 * 类型安全：这个add()方法属于List的原始类型,应该使用参数化的类型
    		 * 解决方法: 只需要使用泛型就没有这种问题
    		 */
        }
    }

#### 5.1.2 方法摘要 ####

ArrayList的方法 = Collection接口方法 + List接口方法，剩下几个不重要的方法。

void ensureCapacity(int minCapacity) 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。

protected void removeRange(int fromIndex, int toIndex) 移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。

void trimToSize() 将此 ArrayList 实例的容量调整为列表的当前大小。

**添加操作简单分析：**

1）如果是第一次添加元素，数组的长度被扩容到默认的capacity，也就是10.

2) 当发觉同时添加一个或者是多个元素，数组长度不够时，就扩容，这里有两种情况：  
只添加一个元素，例如：原来数组的capacity为10，size已经为10，不能再添加了。需要扩容，新的capacity=old capacity+old capacity>>1 = 10+10/2 = 15.即新的容量为15。

当同时添加多个元素时，原来数组的capacity为10，size为10，当同时添加6个元素时。它需要的min capacity为16，而按照capacity=old capacity+old capacity>>1=10+10/2=15。new capacity小于min capacity，则取min capacity。

对于添加，如果不指定下标，就直接添加到数组后面，不涉及元素的移动，如果要添加到某个特定的位置，那需要将这个位置开始的元素往后挪一个位置，然后再对这个位置设置。

**删除操作简单分析：**

Remove提供两种，按照下标和value。  
1）remove(int index)：首先需要检查Index是否在合理的范围内。其次再调用System.arraycopy将index之后的元素向前移动。

2）remove(Object o)：首先遍历数组，获取第一个相同的元素，获取该元素的下标。其次再调用System.arraycopy将index之后的元素向前移动。

**获取操作简单分析：**

这个比较简单，直接对数组进行操作即可。

**经典面试题：**

@Test
    public void testListRemove() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);// [1,2]
    }
    private static void updateList(List list) {
        list.remove(2);
    }

#### 5.1.3 泛型的使用 ####

**示例代码:**

import java.util.ArrayList;
    import java.util.List;
    
    public class Test_ArrayList_03 {
        public static void main(String[] args) {
            // List泛型用法
            List<Integer> list = new ArrayList<>();// 类型推断
    
            list.add(100);
            list.add(88);
            list.add(77);
            list.add(66);
    
            List<String> sList = new ArrayList<String>();
    
            sList.add("x");
            // sList.add(100);
    
        }
    }

**泛型遍历示例代码:**

import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    public class Test_ArrayList_04 {
    
        public static void main(String[] args) {
            List<String> list = new ArrayList<String>();
            list.add("小黑");
            list.add("小张");
            list.add("abc");
            list.add("小红");
            // 如果非泛型写法,那么get(index)得到的是Object类型
            // 如果泛型写法,那么get(index)得到是泛型类型
            // 1.普通for循环遍历,需要使用到size()以及get(index)
            for(int i = 0;i < list.size();i++) {
                System.out.println(list.get(i));
            }
    
            System.out.println("------------------------------");
    
            // 2.for each遍历
            for(String str:list) {
                System.out.println(str);
            }
            System.out.println("------------------------------");
            // 3.迭代器遍历方式
            /*
    		 * 从类 java.util.AbstractList 继承的方法iterator, listIterator
    		 * 	Iterator<E> iterator()	返回以恰当顺序在此列表的元素上进行迭代的迭代器。 
    		 */
            Iterator<String> iterator = list.iterator(); 
            /*
    		 * Iterator里面的方法:
    		 * 	boolean hasNext() 	如果仍有元素可以迭代，则返回 true。 
    		 * 	E next() 	返回迭代的下一个元素。 
    		 */
            while(iterator.hasNext()) {
                //只要迭代器里面还有元素可以迭代,那么就取迭代器里面的下一个元素
                System.out.println(iterator.next());
            }
        }
    }

### 5.2 List实现类之二：LinkedList ###

LinkedList是基于链表的，它是一个双向链表，每个节点维护了一个prev和next指针。

同时对于这个链表，维护了first和last指针，first指向第一个元素，last指向最后一个元素。LinkedList是一个无序的链表，按照插入的先后顺序排序，不提供sort方法对内部元素排序。

对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高。

LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：  
prev变量记录前一个元素的位置  
next变量记录下一个元素的位置

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 6][]

#### 5.2.1 构造函数 ####

LinkedList() 构造一个空列表。

LinkedList(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。

#### 5.2.2 方法摘要 ####

LinkedList除了Collection接口方法 和 List接口方法中继承了方法之外，还多了一些操作首尾元素的方法。
    
    	void addFirst(E e) 		将指定元素插入此列表的开头。 
    
        void addLast(E e) 		将指定元素添加到此列表的结尾。 
    
        Iterator<E> descendingIterator() 	返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 
    
        E element() 	获取但不移除此列表的头（第一个元素）。 
    
        E getFirst() 		返回此列表的第一个元素。 
    
        E getLast() 		返回此列表的最后一个元素。 
    
        boolean offer(E e) 	将指定元素添加到此列表的末尾（最后一个元素）。 
    
        boolean offerFirst(E e) 	在此列表的开头插入指定的元素。 
    
        boolean offerLast(E e) 		在此列表末尾插入指定的元素。 
    
        E peek() 		获取但不移除此列表的头（第一个元素）。 
    
        E peekFirst() 	获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 
    
        E peekLast() 	获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 
    
        E poll() 	获取并移除此列表的头（第一个元素） 
    
        E pollFirst() 	获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 
    
        E pollLast() 	获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 
    
        E pop() 	从此列表所表示的堆栈处弹出一个元素。 
    
        void push(E e) 		将元素推入此列表所表示的堆栈。 
    
        E remove() 		获取并移除此列表的头（第一个元素）。 
    
        E removeFirst() 	移除并返回此列表的第一个元素。 
    
        boolean removeFirstOccurrence(Object o) 	从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。 
    
        E removeLast() 		移除并返回此列表的最后一个元素。 
    
        boolean removeLastOccurrence(Object o) 		从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

**添加元素：**

LinkedList提供了几个添加元素的方法：addFirst、addLast、addAll、add等。

**删除元素：**

LinkedList提供了几个移除元素的方法：removeFirst、removeLast、removeFirstOccurrence、remove等，时间复杂度为O(1)。

**获取元素：**

根据给定的下标index，判断它first节点、last直接距离，如果index < size（数组元素个数)/2,就从first开始。如果大于，就从last开始。这个和我们平常思维不太一样，也许按照我们的习惯，从first开始。这也算是一点小心的优化吧。

**示例代码：**

import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Test_LinkedList_01 {
    
        public static void main(String[] args) {
            // LinkedList() 构造一个空列表。
            LinkedList<String> list = new LinkedList<String>();
    
            //LinkedList(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。
    
            /*
    		 * 这些方法和ArrayList功能一致,不再演示
    		 * 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 
    		 * E get(int index) 返回此列表中指定位置处的元素。 
    		 * int indexOf(Object o) 返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。 
    		 * int lastIndexOf(Object o) 返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。 
    		 * E remove(int index) 移除此列表中指定位置处的元素。
    		 * E set(int index, E element) 将此列表中指定位置的元素替换为指定的元素。 
    		 * int size() 返回此列表的元素数。 
    		 * Object[] toArray() 返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组。 
    		 * 
    		 */
            list.add("x");
            list.add("y");
            list.add("z");
    
            // void addFirst(E e) 将指定元素插入此列表的开头。 
            // 上溯造型:可以使用父类的共性,以及子类的特性;但是不能使用子类的扩展
            // 这个addFirst()输出LinkedList的扩展,上溯造型写法不能调用
            list.addFirst("hello");
    
            // void addLast(E e) 将指定元素添加到此列表的结尾。 
            list.addLast("xxx");
    
            // Iterator<E> descendingIterator() 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
            Iterator<String> iterator = list.descendingIterator();
            while(iterator.hasNext()) {
                System.out.println(iterator.next());
            }
    
            // E element() 获取但不移除此列表的头（第一个元素）。 
            System.out.println("列表的第一个元素是:"+list.element());
            
            //E getFirst() 返回此列表的第一个元素。 
            System.out.println("列表的第一个元素是:"+list.getFirst());
    
            //E getLast() 返回此列表的最后一个元素。 
            System.out.println("列表的最后一个元素是:"+list.getLast());
    
            //boolean offer(E e) 将指定元素添加到此列表的末尾（最后一个元素）。  --> add(E e)
            list.offer("dd"); //底层调用的是add(e),不是addLast()
    
            //boolean offerFirst(E e) 在此列表的开头插入指定的元素。  --> addFirst(E e)
            list.offerFirst("第一"); //叠层调用的是addFirst(),无非就是多了一个返回值
    
            //boolean offerLast(E e) 在此列表末尾插入指定的元素。  --> addLast(E e)
            list.offerLast("最后");
    
            // E peek() 获取但不移除此列表的头（第一个元素）。 和peekFirst()一模一样
            // LinkedList<String> list1 = new LinkedList<String>();
            String peek = list.peek();
            System.out.println("第一个元素是:"+peek);
    
            // E peekFirst() 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 
            String peekFirst = list.peekFirst();
            System.out.println("第一个元素是:"+peekFirst);
    
            // E peekLast() 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 
            String peekLast = list.peekLast();
            System.out.println("最后一个元素是:"+peekLast);
    
            // E poll() 获取并移除此列表的头（第一个元素）  和pollFirst()一模一样
            String poll = list.poll();
            System.out.println("第一个元素是:"+poll);
    
            // E pollFirst() 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 
            //list.pollFirst();
    
            // E pollLast() 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 
            String pollLast = list.pollLast();
            System.out.println("最后一个元素是:"+pollLast);
    
            // E pop() 从此列表所表示的堆栈处弹出第一个元素。 底层是removeFirst()
            String pop = list.pop();
            System.out.println("获取一个元素:"+pop);
    
            // void push(E e) 将元素推入此列表所表示的堆栈。 底层是addFirst(e);
            list.push("push");
    
            // E remove() 获取并移除此列表的头（第一个元素）。 底层是removeFirst()
            list.remove();
    
            // boolean removeFirstOccurrence(Object o) 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。 
            list.add(3, "x");
    
            // list.removeFirstOccurrence("x");
    
            // E removeLast()  移除并返回此列表的最后一个元素。 
            // list.removeLast();
            list.removeLastOccurrence("x");
    
            System.out.println(list);
    
            /*for(int i = 0;i < list.size();i++) {
    			System.out.println(list.get(i));
    		}*/
    
            /*for(String str:list) {
    			System.out.println(str);
    		}*/
        }
    }

### 5.3 List 实现类之三：Vector ###

Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。

在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。  
  
注: Vector基本上不用；https://www.cnblogs.com/Kinghao0319/p/14486040.html

## 六、Collection子接口之二： Set接口 ##

Set接口是Collection的子接口，Set接口没有提供额外的方法。

Set里存放的对象是无序，不能重复的，集合中的对象不按特定的方式排序，只是简单地把对象加入集合中。

Set所谓的没有顺序指的是没有按照我们的存储顺序；按照我们之前学习List的经验来说，List是先存储的，先获取到；但是对于Set来说，你先存储的,可能不是先获取的;

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 set 抽象。

注意：Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。

### 6.1 HashSet详解 ###

HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类。HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。

HashSet是基于HashMap来实现的，操作很简单，更像是对HashMap做了一次“封装”，而且只使用了HashMap的key来实现各种特性，而HashMap的value始终都是PRESENT。  
private static final Object PRESENT = new Object();

HashSet不允许重复（HashMap的key不允许重复，如果出现重复就覆盖），允许null值，非线程安全。

HashSet 具有以下特点：  
不能保证元素的排列顺序；  
HashSet 不是线程安全的；  
集合元素可以是 null；

HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。

对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

#### 6.1.1 构造函数 ####

HashSet() 构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。

HashSet(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的新 set。

HashSet(int initialCapacity) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。

HashSet(int initialCapacity, float loadFactor) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。

**示例代码：**

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    
    public class Test_HashSet_01 {
    	public static void main(String[] args) {
    		// HashSet() 构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。
    		// 加载因子:75%,当存储容量达到75%,会自动扩容
    		HashSet<String> set = new HashSet<String>();
    		
    		/*
    		 * 问题: HashSet底层是HashMap,HashMap是双列集合,但是HashSet的单列集合
    		 * 那么底层使用的HashMap,HashSet在存储数据的时候,是存在了key上还是value上?
    		 * Set集合的特性来思考:
    		 *	Set存储的无序,唯一的数据
    		 *
    		 * Map集合的特性:
    		 * 	Map存储的key和value的映射,key唯一,value不唯一
    		 * 
    		 * HashSet的数据是存储在HashMap的key上,那么它的value到底存储啥呢?
    		 * 	PRESENT --> Object对象
    		 */
    	
    		//HashSet(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的新 set。
    		//Collection——> List Set都可以
    		
    		List<String> list = new ArrayList<String>(); //[张三,c,天]
    		list.add("张三");
    		list.add("c");
    		list.add("天");
    		
    		HashSet<String> set01 = new HashSet<String>(list);
    		
    		
    		System.out.println(set01);
    		
    		
    		//HashSet(int initialCapacity) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
    		//我们昨天在说ArrayList的时候,已经提到了,如果存储的元素数量比较确定,那么我们在定义ArrayList的时候,一定要指定初始容量,这样的话可以节省开销
    		
    		
    		//HashSet(int initialCapacity, float loadFactor) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。
    		//虽说加载因子可以去指定,但是大部分情况下,不推荐大家去更改
    		
    	}
    }

#### 6.1.2 方法摘要 ####

boolean add(E e) 	如果此 set 中尚未包含指定元素，则添加指定元素。 
    
        void clear() 		从此 set 中移除所有元素。 
    
        Object clone() 		返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。 
    
        boolean contains(Object o) 		如果此 set 包含指定元素，则返回 true。 
    
        boolean isEmpty() 		如果此 set 不包含任何元素，则返回 true。 
    
        Iterator<E> iterator() 		返回对此 set 中元素进行迭代的迭代器。 
    
        boolean remove(Object o) 		如果指定元素存在于此 set 中，则将其移除。 
    
        int size() 			返回此 set 中的元素的数量（set 的容量）。

**示例代码:**

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Test_HashSet_02 {
    
    	public static void main(String[] args) {
    		Set<String>  set= new HashSet<String>();
    		
    		// boolean add(E e) 如果此 set 中尚未包含指定元素，则添加指定元素。 
    		// 如果不包含指定元素,那么添加;如果包含呢?是覆盖呢还是不添加?
    		boolean add = set.add("xyz");
    		
    		set.add("ddd");
    		set.add("小明");
    		set.add("小黑");
    		set.add("李磊");
    		
    		// void clear() 从此 set 中移除所有元素。 
    		// set.clear();
    		
    		// boolean contains(Object o) 如果此 set 包含指定元素，则返回 true。 
    		// boolean isEmpty() 	如果此 set 不包含任何元素，则返回 true。 
    		// boolean remove(Object o) 如果指定元素存在于此 set 中，则将其移除。 Set里面的remove方法不涉及下标.因为set是无序的
    		set.remove("xyz");
    		// int size() 返回此 set 中的元素的数量（set 的容量）。 
    		
    		// boolean removeAll(Collection<?> c)从此 set 中移除包含在指定 collection 中的所有元素（可选操作）。
    		List<String> removeList = new ArrayList<String>();
    		removeList.add("小黑");
    		removeList.add("李磊");
    		
    		// removeAll是参数集合里面有的,则移除掉
    		// set.removeAll(removeList);
    		
    		// retainAll是参数集合里面有的,则保留
    		set.retainAll(removeList);
    		
    		System.out.println("set中是否包含xyz字符串:"+set.contains("xyz"));
    		System.out.println("set是否为空:"+set.isEmpty());
    		System.out.println("set集合元素的个数是:"+set.size());
    		System.out.println(set);
    		
    		// 现在学生有一个唯一标识符就是id,id、name、age都一样了,我们就可以认为是一个学生
    		Student stu1 = new Student(1001,"张三",12);
    		Student stu2 = new Student(1001,"张三",12);
    		
    		Set<Student> stuSet = new HashSet<Student>();
    		stuSet.add(stu1);
    		stuSet.add(stu2);
    		
    		// HashSet是根据哈希吗来存储的
    		// 问题:怎么样才能让其内容完全一致的时候,只能存储一个呢?
    		System.out.println(stu1.hashCode());
    		System.out.println(stu2.hashCode());
    		
    		System.out.println(stuSet);
    	}
    }
    
    class Student{
    	int id;
    	String name;
    	int age;
    	public Student(int id,String name,int age) {
    		this.id = id;
    		this.name = name;
    		this.age = age;
    	}
    	@Override
    	public int hashCode() {
    		final int prime = 31;
    		int result = 1;
    		result = prime * result + age;
    		result = prime * result + id;
    		result = prime * result + ((name == null) ? 0 : name.hashCode());
    		return result;
    	}
    	@Override
    	public boolean equals(Object obj) {
    		if (this == obj)
    			return true;
    		if (obj == null)
    			return false;
    		if (getClass() != obj.getClass())
    			return false;
    		Student other = (Student) obj;
    		if (age != other.age)
    			return false;
    		if (id != other.id)
    			return false;
    		if (name == null) {
    			if (other.name != null)
    				return false;
    		} else if (!name.equals(other.name))
    			return false;
    		return true;
    	}
    	
    }

**遍历示例代码:**

import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedHashSet;
    import java.util.Set;
    import java.util.TreeMap;
    
    public class Test_HashSet_03 {
    	public static void main(String[] args) {
    		// 我们在讲解List的时候,使用了三种方法进行遍历
    		// 但是Set都适用吗?
    		
    		/*
    		 * List遍历的三种方式:
    		 * 	1.普通for循环,通过size()/get(index)来实现List遍历
    		 *  2.forEach循环
    		 *  3.迭代器实现
    		 */
    		Set<String> set = new HashSet<String>();
    		set.add("xx");
    		set.add("李磊");
    		set.add("小黑");
    		set.add("小明");
    		
    		for(String str:set) {
    			System.out.println(str);
    		}
    		
    		System.out.println("-------------------------------");
    		Iterator<String> iterator = set.iterator();
    		while(iterator.hasNext()) {
    			System.out.println(iterator.next());
    		}
    		
    		/*
    		 * HashSet着重练习
    		 * 对于LinkedHashSet里面的方法都不需要关注.因为和HashSet是一样的
    		 * 如果有时间,可以简单练习下TreeSet里面的方法;
    		 */
    	}
    }

#### 6.1.3 添加元素的过程 ####

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）  
  
如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。

如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 7][]

public class HashSetTest {
        /*
        一、Set：存储无序的、不可重复的数据
        以HashSet为例说明：
        1. 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
    
        2. 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。
    
        二、添加元素的过程：以HashSet为例：
            我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，
            此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断
            数组此位置上是否已经有元素：
                如果此位置上没有其他元素，则元素a添加成功。 --->情况1
                如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：
                    如果hash值不相同，则元素a添加成功。--->情况2
                    如果hash值相同，进而需要调用元素a所在类的equals()方法：
                           equals()返回true,元素a添加失败
                           equals()返回false,则元素a添加成功。--->情况3
    
            对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
            jdk 7 :元素a放到数组中，指向原来的元素。
            jdk 8 :原来的元素在数组中，指向元素a
            总结：七上八下
    
            HashSet底层：数组+链表的结构。
         */
        @Test
        public void test1() {
            Set set = new HashSet();
            set.add(456);
            set.add(123);
            set.add(123);
            set.add("AA");
            set.add("CC");
            set.add(new User("Tom", 12));
            set.add(new User("Tom", 12));
            set.add(129);
    
            Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    }
    
    public class User {
        private String name;
        private int age;
    
        public User() {
        }
    
        public User(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "User{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            System.out.println("User equals()....");
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
    
            User user = (User) o;
    
            if (age != user.age) return false;
            return name != null ? name.equals(user.name) : user.name == null;
        }
    
        @Override
        public int hashCode() { //return name.hashCode() + age;
            int result = name != null ? name.hashCode() : 0;
            result = 31 * result + age;
            return result;
        }
    }

**重写 hashCode() 方法的基本原则：**

在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。  
  
当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等。

对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

**Eclipse/IDEA工具里hashCode()的重写：**

以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals和hashCode。问题：为什么用Eclipse/IDEA复写hashCode方法，有31这个数字？

选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）  
  
并且31只占用5bits,相乘造成数据溢出的概率较小。

31可以 由i\*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效率）

31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除！(减少冲突)

**经典面试题：**

// 试写出下列代码的运行结果：
    HashSet set = new HashSet();
    Person p1 = new Person(1001,"AA");
    Person p2 = new Person(1002,"BB");
    
    set.add(p1);
    set.add(p2);
    p1.name = "CC";
    set.remove(p1);
    System.out.println(set);
    
    set.add(new Person(1001,"CC"));
    System.out.println(set);
    
    set.add(new Person(1001,"AA"));
    System.out.println(set);
    
    // Person类如下
    public class Person {
        public int id;
        public String name;
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return id == person.id &&
                Objects.equals(name, person.name);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(id, name);
        }
    
        @Override
        public String toString() {
            return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", hashCode='"+hashCode()+'\''+
                '}';
        }
    
        public Person(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

解析：https://blog.csdn.net/hhmy77/article/details/105068513

这道题目告诉我们，尽量不要对set，map中的对象进行修改；

### 6.2 LinkedHashSet ###

LinkedHashSet 是 HashSet 的子类。  
  
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

LinkedHashSet 不允许集合元素重复。

它的成员方法和构造方法和HashSet基本一致;

public class LinkedHashSetTest {
    
        //LinkedHashSet的使用
        //LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个
        //数据和后一个数据。
        //优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet
        @Test
        public void test1() {
            Set set = new LinkedHashSet();
            set.add(456);
            set.add(123);
            set.add(123);
            set.add("AA");
            set.add("CC");
            set.add(new User("Tom", 12));
            set.add(new User("Tom", 12));
            set.add(129);
    
            Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    }

**LinkedHashSet底层结构：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 8][]

### 6.3 TreeSet ###

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

TreeSet底层使用红黑树结构存储数据。

新增的方法如下： (了解)  
Comparator comparator()  
Object first()  
Object last()  
Object lower(Object e)  
Object higher(Object e)  
SortedSet subSet(fromElement, toElement)  
SortedSet headSet(toElement)  
SortedSet tailSet(fromElement)

TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

TreeSet和后面要讲的TreeMap采用红黑树的存储结构。特点：有序，查询速度比List快。  
红黑树具体不说：有兴趣的可以参看：https://www.jianshu.com/p/4cd37000f4e3，对红黑树的讲解写得不错。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 9][]

#### 6.3.1 自然排序 ####

自然排序：TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列。

如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口。实现 Comparable 的类必须实现compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。  
  
Comparable 的典型实现：  
BigDecimal、BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较；  
Character：按字符的 unicode值来进行比较；  
Boolean：true 对应的包装类实例大于 false 对应的包装类实例；  
String：按字符串中字符的 unicode 值进行比较；  
Date、Time：后边的时间、日期比前面的时间、日期大；

向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。

因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。

对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。

当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果：如果两个对象通过equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。否则，让人难以理解。

#### 6.3.2 定制排序 ####

TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。

利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。

要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。

此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。

使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

#### 6.3.4 示例代码 ####

import org.junit.Test;
    
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.TreeSet;
    
    
    public class TreeSetTest {
    
        /*
        1.向TreeSet中添加的数据，要求是相同类的对象。
        2.两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator）
    
    
        3.自然排序中，比较两个对象是否相同的标准为：compareTo()返回0.不再是equals().
        4.定制排序中，比较两个对象是否相同的标准为：compare()返回0.不再是equals().
         */
        @Test
        public void test1() {
            TreeSet set = new TreeSet();
    
            //失败：不能添加不同类的对象
            /*set.add(123);
            set.add(456);
            set.add("AA");
            set.add(new User("Tom",12));*/
    
            //举例一：
            /*set.add(34);
            set.add(-34);
            set.add(43);
            set.add(11);
            set.add(8);*/
    
            //举例二：
            set.add(new User("Tom", 12));
            set.add(new User("Jerry", 32));
            set.add(new User("Jim", 2));
            set.add(new User("Mike", 65));
            set.add(new User("Jack", 33));
            set.add(new User("Jack", 56));
    
    
            Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
    
        }
    
        @Test
        public void test2() {
            Comparator com = new Comparator() {
                //按照年龄从小到大排列
                @Override
                public int compare(Object o1, Object o2) {
                    if (o1 instanceof User && o2 instanceof User) {
                        User u1 = (User) o1;
                        User u2 = (User) o2;
                        return Integer.compare(u1.getAge(), u2.getAge());
                    } else {
                        throw new RuntimeException("输入的数据类型不匹配");
                    }
                }
            };
    
            TreeSet set = new TreeSet(com);
            set.add(new User("Tom", 12));
            set.add(new User("Jerry", 32));
            set.add(new User("Jim", 2));
            set.add(new User("Mike", 65));
            set.add(new User("Mary", 33));
            set.add(new User("Jack", 33));
            set.add(new User("Jack", 56));
    
    
            Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    
    }

public class User implements Comparable{
        private String name;
        private int age;
    
        public User() {
        }
    
        public User(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public String toString() {
            return "User{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
            System.out.println("User equals()....");
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
    
            User user = (User) o;
    
            if (age != user.age) return false;
            return name != null ? name.equals(user.name) : user.name == null;
        }
    
        @Override
        public int hashCode() { //return name.hashCode() + age;
            int result = name != null ? name.hashCode() : 0;
            result = 31 * result + age;
            return result;
        }
    
        //按照姓名从大到小排列,年龄从小到大排列
        @Override
        public int compareTo(Object o) {
            if(o instanceof User){
                User user = (User)o;
    //            return -this.name.compareTo(user.name);
                int compare = -this.name.compareTo(user.name);
                if(compare != 0){
                    return compare;
                }else{
                    return Integer.compare(this.age,user.age);
                }
            }else{
                throw new RuntimeException("输入的类型不匹配");
            }
    
        }
    }

## 七、Map接口 ##

Map与Collection并列存在。用于保存具有映射关系的数据:key-value。 Map 中的 key 和 value 都可以是任何引用类型的数据。

Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法。

任何类都可以作为Map的“键”，常用String类作为Map的“键”。

key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value。

Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是 Map 接口使用频率最高的实现类。

### 7.1 Map接口方法 ###

#### 7.1.1 添加、删除、修改操作 ####

V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）。

void putAll(Map<? extends K,? extends V> m) 从指定映射中将所有映射关系复制到此映射中（可选操作）。

V remove(Object key) 如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。

void clear() 从此映射中移除所有映射关系（可选操作）。

@Test
    public void test1(){
        Map map = new HashMap();
        //添加
        map.put("AA",123);
        map.put(45,123);
        map.put("BB",56);
        //修改
        map.put("AA",87);
    
        System.out.println(map);
    
        Map map1 = new HashMap();
        map1.put("CC",123);
        map1.put("DD",123);
    
        map.putAll(map1);
    
        System.out.println(map);
    
        //remove(Object key)
        Object value = map.remove("CC");
        System.out.println(value);
        System.out.println(map);
    
        //clear()
        map.clear();//与map = null操作不同
        System.out.println(map.size());
        System.out.println(map);
    }

#### 7.1.2 元素查询的操作 ####

boolean containsKey(Object key) 如果此映射包含指定键的映射关系，则返回 true。  
  
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true。  
  
V get(Object key) 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。

boolean equals(Object o) 比较指定的对象与此映射是否相等。

boolean isEmpty() 如果此映射未包含键-值映射关系，则返回 true。

int size() 返回此映射中的键-值映射关系数。

@Test
    public void test2(){
        Map map = new HashMap();
        map.put("AA",123);
        map.put(45,123);
        map.put("BB",56);
        // Object get(Object key)
        System.out.println(map.get(45));
        //containsKey(Object key)
        boolean isExist = map.containsKey("BB");
        System.out.println(isExist);
    
        isExist = map.containsValue(123);
        System.out.println(isExist);
    
        map.clear();
    
        System.out.println(map.isEmpty());
    
    }

#### 7.1.3 元视图操作的方法 ####

Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的 Set 视图。

Collection<V> values() 返回此映射中包含的值的 Collection 视图。  
  
Set<K> keySet() 返回此映射中包含的键的 Set 视图。

@Test
    public void test3(){
        Map map = new HashMap();
        map.put("AA",123);
        map.put(45,1234);
        map.put("BB",56);
    
        //遍历所有的key集：keySet()
        Set set = map.keySet();
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        System.out.println();
        //遍历所有的value集：values()
        Collection values = map.values();
        for(Object obj : values){
            System.out.println(obj);
        }
        System.out.println();
        //遍历所有的key-value
        //方式一：entrySet()
        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            //entrySet集合中的元素都是entry
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());
    
        }
        System.out.println();
        //方式二：
        Set keySet = map.keySet();
        Iterator iterator2 = keySet.iterator();
        while(iterator2.hasNext()){
            Object key = iterator2.next();
            Object value = map.get(key);
            System.out.println(key + "=====" + value);
    
        }
    
    }

### 7.2 Map实现类之一：HashMap ###

HashMap是 Map 接口使用频率最高的实现类。

允许使用null键和null值，与HashSet一样，不保证映射的顺序。

所有的key构成的集合是Set:无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()。

所有的value构成的集合是Collection:无序的、可以重复的。所以，value所在的类要重写：equals()。

所有的entry构成的集合是Set:无序的、不可重复的。

HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。

HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。

数组方式存储key/value，线程非安全，允许null作为key和value，key不可以重复，value允许重复，不保证元素迭代顺序是按照插入时的顺序，key的hash值是先计算key的hashcode值，然后再进行计算，每次容量扩容会重新计算所以key的hash值，会消耗资源，要求key必须重写equals和hashcode方法

默认初始容量16，加载因子0.75，扩容为旧容量乘2，查找元素快，如果key一样则比较value，如果value不一样，则按照链表结构存储value，就是一个key后面有多个value；

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 10][]

#### 7.2.1 存储结构 ####

JDK 7及以前版本：HashMap是数组+链表结构（即为链地址法）。

JDK 8版本发布以后：HashMap是数组+链表+红黑树实现。

**JDK 7及以前版本：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 11][]

HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量（Capacity），在这个数组中可以存放元素的位置我们称之为“桶”（bucket），每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。而且新添加的元素作为链表的head。

添加元素的过程:  
向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值（根据key所在类的hashCode()计算得到），此哈希值经过处理以后，得到在底层Entry\[\]数组中要存储的位置i。  
如果位置i上没有元素，则entry1直接添加成功。如果位置i上已经存在entry2（或还有链表存在的entry3，entry4），则需要通过循环的方法，依次比较entry1中key和其他的entry。如果彼此hash值不同，则直接添加成功。如果hash值相同，继续比较二者是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素。

HashMap的扩容:  
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？  
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)\*loadFactor时，就会进行数组扩容,loadFactor的默认值(DEFAULT\_LOAD\_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT\_INITIAL\_CAPACITY)为16，那么当HashMap中元素个数超过16\*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

**JDK 8版本发布以后：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 12][]

HashMap的内部存储结构其实是数组+链表+树的结合。当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。  
  
那么HashMap什么时候进行扩容和树形化呢？  
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)\*loadFactor 时 ，就会进行数组扩容，loadFactor 的默认 值(DEFAULT\_LOAD\_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT\_INITIAL\_CAPACITY)为16，那么当HashMap中元素个数超过16\*0.75=12（这个值就是代码中的threshold值，也叫做临界值）时候，就把数组的大小扩展为 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。

关于映射关系的key是否可以修改？答案：不要修改。  
映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。

**总结：JDK1.8相较于之前的变化：**

1、HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组。  
  
2、当首次调用map.put()时，再创建长度为16的数组；  
  
3、数组为Node类型，在jdk7中称为Entry类型；  
  
4、形成链表结构时，新添加的key-value对在链表的尾部（七上八下）；  
  
5、当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。

#### 7.2.2 源码中的重要常量 ####

DEFAULT\_INITIAL\_CAPACITY : HashMap的默认容量，16。  
  
MAXIMUM\_CAPACITY ： HashMap的最大支持容量，2^30。  
  
DEFAULT\_LOAD\_FACTOR：HashMap的默认加载因子，0.75。  
  
TREEIFY\_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树，8。  
  
UNTREEIFY\_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，6，转化为链表。  
  
MIN\_TREEIFY\_CAPACITY：桶中的Node被树化时最小的hash表容量，64。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN\_TREEIFY\_CAPACITY时，此时应执行resize扩容操作这个MIN\_TREEIFY\_CAPACITY的值至少是TREEIFY\_THRESHOLD的4倍。）  
  
table：存储元素的数组，总是2的n次幂。  
  
entrySet：存储具体元素的集。  
  
size：HashMap中存储的键值对的数量。  
  
modCount：HashMap扩容和结构改变的次数。  
  
threshold：扩容的临界值，=容量\*填充因子。  
  
loadFactor：填充因子。

#### 7.2.3 构造函数 ####

HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。

HashMap(Map<? extends K,? extends V> m) 构造一个映射关系与指定 Map 相同的新 HashMap。

import java.util.HashMap;
    
    public class Test_HashMap_01 {
    
        public static void main(String[] args) {
            // HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
            HashMap<String, Integer> map01 = new HashMap<String, Integer>();
            map01.put("x", 100); //向map里面存储数据
            map01.put("y", 100);
            map01.put(null, null);
            // 因为已经存在key为x的数据,那么这个操作只是把x对应的value给其覆盖了
            map01.put("x", 300); //在map中key唯一,value不唯一
    
            System.out.println(map01);
    
            // HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
    
            // HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。
    
            // HashMap(Map<? extends K,? extends V> m) 构造一个映射关系与指定 Map 相同的新 HashMap
            HashMap<String, Integer> map02 = new HashMap<String, Integer>(map01);
            System.out.println(map02.size());
    
        }
    }

#### 7.2.4 方法摘要 ####

HashMap没有新增方法，和Map接口一致；

#### 7.2.5 遍历方式 ####

import java.util.Collection;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map.Entry;
    import java.util.Set;
    
    public class Test_HashMap_03 {
    
        public static void main(String[] args) {
            // HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
            HashMap<String, Integer> map01 = new HashMap<String, Integer>();
    
            // V put(K key, V value) 在此映射中关联指定值与指定键。 
            map01.put("x", 100); //向map里面存储数据
            map01.put("y", 100);
            map01.put(null, null);
            map01.put("d", null);
    
            // 第一种方式:可以获取到key和value
            // keySet() 返回此映射中所包含的键的 Set 视图。
            // keySet()得到的是所有键的Set集合,那么我们只需要遍历这个set集合,然后根据遍历的key获取对应的value即可
            Set<String> keySet = map01.keySet();
            Iterator<String> iterator = keySet.iterator(); //这个迭代器里面是所有的key
            while(iterator.hasNext()) {
                //iterator.next() 得到的就是下一个key
                String next = iterator.next();
                System.out.println("key是:"+next+",value是:"+map01.get(next));
            }
            System.out.println("----------------------");
            
            // 第二种方式: 只能获取到value
            // values() 返回此映射所包含的值的 Collection 视图。
            // 因为Collection的父接口是Iterable，实现这个接口允许对象成为 "foreach" 语句的目标。 
            Collection<Integer> values = map01.values();
            for(Integer it:values) {
                System.out.println(it);
            }
            System.out.println("----------------------");
            
            // 第三种方式:可以获取到key和value
            // Set<Map.Entry<K,V>> entrySet() 返回此映射所包含的映射关系的 Set 视图。 
            Set<Entry<String, Integer>> entrySet = map01.entrySet(); //通过entrySet得到的是一个Set视图
    
            // Set的泛型是Entry<String, Integer>,我们都指定Set肯定是可以forEach
            /*
    		 * public static interface Map.Entry<K,V>
    		 * 		映射项（键-值对）。  代表一个映射对
    		 * 
    		 */
            for(Entry<String, Integer> entry:entrySet) {
                //一个Entry对象里面只存储了一个键值映射
                //K getKey() 	返回与此项对应的键。 
                //V getValue() 返回与此项对应的值。 
                System.out.println(entry.getKey()+"\t"+entry.getValue());
            }
    
        }
    
    }

### 7.3 Map实现类之二：LinkedHashMap ###

LinkedHashMap 是 HashMap 的子类。

在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。

与LinkedHashSet类似，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致。

LinkedHashMap保存了记录的插入顺序，在用Iteraor遍历LinkedHashMap时，先得到的记录肯定是先插入的，在遍历的时候会比HashMap慢，有HashMap的全部特性。  
  
在我们进行选择使用的时候,一般使用的是HashMap,不太考虑LinkedHashMap;

**HashMap中的内部类：Node：**

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }

**LinkedHashMap中的内部类：Entry：**

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

### 7.4 Map实现类之三：TreeMap ###

TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

TreeSet底层使用红黑树结构存储数据。

TreeMap 的 Key 的排序：  
自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException。

定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口。

TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。

基于红黑二叉树的NavigableMap的实现，线程非安全，不允许null，key不可以重复，value允许重复，存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口，会按照排序后的顺序迭代元素，两个相比较的key不得抛出classCastException。

主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按排序顺序输出；

public class TreeMapTest {
    
        //向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
        //因为要按照key进行排序：自然排序 、定制排序
        //自然排序
        @Test
        public void test1(){
            TreeMap map = new TreeMap();
            User u1 = new User("Tom",23);
            User u2 = new User("Jerry",32);
            User u3 = new User("Jack",20);
            User u4 = new User("Rose",18);
    
            map.put(u1,98);
            map.put(u2,89);
            map.put(u3,76);
            map.put(u4,100);
    
            Set entrySet = map.entrySet();
            Iterator iterator1 = entrySet.iterator();
            while (iterator1.hasNext()){
                Object obj = iterator1.next();
                Map.Entry entry = (Map.Entry) obj;
                System.out.println(entry.getKey() + "---->" + entry.getValue());
    
            }
        }
    
        //定制排序
        @Test
        public void test2(){
            TreeMap map = new TreeMap(new Comparator() {
                @Override
                public int compare(Object o1, Object o2) {
                    if(o1 instanceof User && o2 instanceof User){
                        User u1 = (User)o1;
                        User u2 = (User)o2;
                        return Integer.compare(u1.getAge(),u2.getAge());
                    }
                    throw new RuntimeException("输入的类型不匹配！");
                }
            });
            User u1 = new User("Tom",23);
            User u2 = new User("Jerry",32);
            User u3 = new User("Jack",20);
            User u4 = new User("Aim",18);
    
            map.put(u1,98);
            map.put(u2,89);
            map.put(u3,76);
            map.put(u4,100);
    
            Set entrySet = map.entrySet();
            Iterator iterator1 = entrySet.iterator();
            while (iterator1.hasNext()){
                Object obj = iterator1.next();
                Map.Entry entry = (Map.Entry) obj;
                System.out.println(entry.getKey() + "---->" + entry.getValue());
    
            }
        }
    }

### 7.5 Map实现类之四：Hashtable ###

Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的。

Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。

与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value。

与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序。

### 7.6 Map实现类之五：Properties ###

Properties 类是 Hashtable 的子类，该对象用于处理属性文件。  
  
由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型。  
  
存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法。

## 八、集合总结 ##

### 8.1 Vector和ArrayList ###

1、Vector是线程同步的，所以它也是线程安全的，而Arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。

2、如果集合中的元素的数目大于目前集合数组的长度时，Vector增长率为目前数组长度的100%，而Arraylist增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据，用vector有一定的优势。

3、如果查找一个指定位置的数据，Vector和Arraylist使用的时间是相同的，如果频繁的访问数据，这个时候使用Vector和Arraylist都可以。而如果移动一个指定位置会导致后面的元素都发生移动，这个时候就应该考虑到使用Linkedlist,因为它移动一个指定位置的数据时其它元素不移动。

ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快，插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快。

### 8.2 ArrayList和LinkedList ###

ArrayList： 底层用数组实现，由于数组可以通过下标直接访问指定索引的元素，因此，ArrayList通过索引查询元素非常快。但由于插入和删除元素时都会进行数组的重新排列，因此，ArrayList的插入和删除操作比较慢。

LinkedList：底层用链表实现，由于链表没有具体的下标，因此，访问某个索引的节点时需要遍历该节点前面的所有元素，速度比较慢。由于插入和删除元素时只需要更新相应元素的指针（或引用），不用重新排列元素，因此，LinkedList对插入和删除操作比较快。

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为ArrayList要移动指针。

3.对于插入和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Test_01 {
    
    	public static void main(String[] args) {
    		/*
    		 * 比较ArrayList和LinkedList的执行效率
    		 * 	随机访问get和set，ArrayList觉得优于LinkedList
    		 * 	于新增和删除操作add和remove，LinekdList比较占优势，因为ArrayList要移动数据
    		 */
    		long aBegin = System.currentTimeMillis();
    		List<Integer> arrList = new ArrayList<Integer>();
    		
    		//我们给ArrayList插入100000条数据
    		for(int i = 0;i < 100000;i++) {
    			arrList.add(0, i);
    		}
    		long aEnd = System.currentTimeMillis();
    		System.out.println("ArrayList插入100000条数据耗时:"+(aEnd-aBegin));
    		
    		long lBegin = System.currentTimeMillis();
    		List<Integer> linkedList = new LinkedList<Integer>();
    		//我们给LinkedList插入100000天数据
    		for(int i = 0;i < 100000;i++) {
    			linkedList.add(0, i);
    		}
    		long lEnd = System.currentTimeMillis();
    		System.out.println("LinkedList插入100000条数据耗时:"+(lEnd-lBegin));
    		
    		/*
    		 * 结论: 如果是频繁的添加(插入)或删除操作,那么我们推荐LinkedList;
    		 */
    	}
    
    }
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Test_02 {
    
    	public static void main(String[] args) {
    		/*
    		 * 比较ArrayList和LinkedList的执行效率
    		 * 	随机访问get和set，ArrayList觉得优于LinkedList
    		 * 	于新增和删除操作add和remove，LinekdList比较占优势，因为ArrayList要移动数据
    		 */
    		
    		List<Integer> arrList = new ArrayList<Integer>();
    		List<Integer> linkedList = new LinkedList<Integer>();
    		//我们给ArrayList和linkedList插入10000条数据
    		for(int i = 0;i < 10000;i++) {
    			arrList.add(0, i);
    			linkedList.add(0,1);
    		}
    		
    		long aBegin = System.currentTimeMillis();
    		for(int i = 0;i < arrList.size();i++) {
    			System.out.print(arrList.get(i));
    		}
    		
    		long aEnd = System.currentTimeMillis();
    		System.out.println("获取所有Arraylist数据的时间是:"+(aEnd-aBegin));
    		
    		long lBegin = System.currentTimeMillis();
    		for(int i = 0;i < linkedList.size();i++) {
    			System.out.print(linkedList.get(i));
    		}
    		
    		long lEnd = System.currentTimeMillis();
    		System.out.println();
    		System.out.println("获取所有linkedList数据的时间是:"+(lEnd-lBegin));
    		
    		/*
    		 * 结论: 如果是频繁的获取或设置,那么我们推荐使用ArrayList
    		 */
    	}
    
    }

### 8.3 HashSet和TreeSet ###

HashSet基于HashMap，用键来存放HashSet的值，由于HashMap的键不能重复，因此，HashSet的值也不会重复，这是集合的一个特点。

TreeSet基于TreeMap，也是用键来存放TreeSet的值。TreeMap的底层实现是红黑树，其根据键排序，可以得到排好序的数据。

### 8.4 HashMap与TreeMap ###

1、 HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

2、在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。

两个map中的元素一样，但顺序不一样，导致hashCode()不一样。

同样做测试：  
在HashMap中，同样的值的map,顺序不同，equals时，false;  
而在treeMap中，同样的值的map,顺序不同,equals时，true，说明，treeMap在equals()时是整理了顺序了的。

### 8.5 Hashtable与HashMap ###

1、同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的。

2、HashMap允许存在一个为null的key，多个为null的value 。

3、Hashtable的key和value都不允许为null。

## 九、线程安全集合类 ##

### 9.1 CopyOnWriteArrayList ###

CopyOnWriteArrayList是线程同步的数组集合。CopyOnWriteArrayList使用场景主要是多线程环境下，查询、遍历操作明显多于增加、删除操作。

CopyOnWriteArrayList默认容量是0，从0开始

CopyOnWriteArrayList没有规定最大容量(适合在查询操作频繁的场景下使用，容量变化不大)

CopyOnWriteArrayList扩容机制，每次+1

### 9.2 ArrayBlockingQueue ###

ArrayBlockingQueue是基于数组实现的线程安全的有界队列。它的容量是用户传递进来的。(内部使用ReentrantLock实现线程同步).

### 9.3 ConcurrentLinkedQueue ###

ConcurrentLinkedQueue是基于单链表实现的线程安全的无界队列。(内部使用CAS实现线程同步是乐观锁)

DelayQueue、PriorityQueue 非线程安全的无界队列。

### 9.4 LinkedBlockingQueue ###

LinkedBlockingQueue是基于单链表实现的线程安全的无界队列。(内部使用takeLock和putLock读写分离锁实现)

Map相关的默认容量以及扩容机制。

### 9.5 LinkedBlockingQueue和ArrayBlockingQueue的区别？ ###

LinkedBlockingQueue底层使用链表来存放数据，而ArrayBlockingQueue底层使用数组来存放数据。
    
    	二者的相同点是提供了一个阻塞式容器，生产者可以往里面存放数据，消费者可以从里面获取数据。当容器中没有数据时，如果有消费者试图获取数据，那么消费者线程将阻塞，直到有某个生产者存放了数据。
    当容器已满时，如果有生产者试图存放数据，那么生产者线程将阻塞，直到有某个消费者取出了数据。

## 十、Comparable 和 Comparator ##

在Java中经常会涉及到对象数组和集合的排序问题，那么就涉及到对象之间的比较问题。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 13][]

Java实现对象排序的方式有两种：  
自然排序：java.lang.Comparable  
定制排序：java.util.Comparator  
  
Comparable 和 Comparator都是用于比较数据的大小的；  
Comparable：可比较的 Comparator：比较器  
  
实现Comparable接口需要重写compareTo方法，实现Comparator接口需要重写compare方法，这两个方法的返回值都是int，用int类型的值来确定比较结果；

在Arrays/Collections工具类中有一个排序方法sort，此方法可以之传一个数组，另一个重载版本是传入数组和比较器，前者默认使用的就是Comparable中的compareTo方法，后者使用的便是我们传入的比较器Comparator，java的很多类已经实现了Comparable接口，比如说String，Integer等类。

而我们其实也是基于这些实现了Comparator或者Comparable接口的原生类来比较我们自己的类；

### 10.1 Comparable ###

Comparable接口强行对实现它的每个类的对象进行整体排序，这种排序被称为类的自然排序，接口的compareTo方法被称为其自然比较方法。  
  
Comparable接口中只有一个方法：  
public int compareTo(T o) 将此对象与指定的对象进行比较以进行排序。  
  
实现 Comparable 的类必须实现 compareTo(Object obj) 方法，两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。如果当前对象this大于形参对象obj，则返回正整数，如果当前对象this小于形参对象obj，则返回负整数，如果当前对象this等于形参对象obj，则返回零。  
  
实现Comparable接口的对象列表（和数组）可以通过 Collections.sort 或Arrays.sort进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。  
  
对于类 C 的每一个 e1 和 e2 来说，当且仅当 e1.compareTo(e2) == 0 与 e1.equals(e2) 具有相同的 boolean 值时，类 C 的自然排序才叫做与 equals 一致。建议（虽然不是必需的）最好使自然排序与 equals 一致。  
  
Comparable 的典型实现：(默认都是从小到大排列的)  
String：按照字符串中字符的Unicode值进行比较。  
Character：按照字符的Unicode值来进行比较。  
数值类型对应的包装类以及BigInteger、BigDecimal：按照它们对应的数值大小进行比较。  
Boolean：true 对应的包装类实例大于 false 对应的包装类实例。  
Date、Time等：后面的日期时间比前面的日期时间大。

@Test
    public void test1(){
        String[] arr = new String[]{"AA","CC","KK","MM","GG","JJ","DD"};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

调用此方法的对象，也就是this和o进行比较，若返回值大于0则this大于o，返回值等于0则是this等于o，返回值小于0则是this < o,而这个Comparable是直接在我们的自定义类Goods上实现，因为this是需要一个明确的比较对象的，也就是一般情况下我们会在定义Goods类的时候有排序的需求，就要实现此接口。

public class Goods implements Comparable<Goods>{
        // 商品名
        private String name;
        // 商品价格
        private double price;
    
        public Goods(){}
    
        public Goods(String name, double price) {
            this.name = name;
            this.price = price;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public double getPrice() {
            return price;
        }
    
        public void setPrice(double price) {
            this.price = price;
        }
    
        @Override
        public String toString() {
            return "Goods{" +
                    "name='" + name + '\'' +
                    ", price=" + price +
                    '}';
        }
    
        // 我们在compareTo中进行比较的时候，其实比较的就是对象的某个字段；
        // 比较字段要满足的需求：如果当前对象this大于形参对象obj，则返回正整数，如果当前对象this小于形参对象obj，则返回负整数，如果当前对象this等于形参对象obj，则返回零。
        /*
         * 排序一：
         *  按照价格从低到高排序，那么在compareTo里面就比较当前对象的price和参数对象的price
         *  return Double.compare(this.price,o.price);
         * 排序二:
         *  按照价格从高到低排序，那么在compareTo里面就比较当前对象的price和参数对象的price
         *  return -Double.compare(this.price,o.price);
         * 排序三：
         *  按照价格从低到高排序，如果价格相等，按照名称从高到低排序；
         */
        @Override
        public int compareTo(Goods o) {
            // 方式一: 自己写比较逻辑
            /*if(this.price > o.price){
                return 1;
            }else if(this.price < o.price){
                return -1;
            }else{
                return 0;
            }*/
    
            // 方式二: 调用包装类的比较方法
            // return Double.compare(this.price,o.price);
    
            // 按照价格从低到高排序，如果价格相等，按照名称从高到低排序；
            int compare = Double.compare(this.price, o.price);
            if(compare != 0){
                return compare;
            }else{
                return -this.name.compareTo(o.name);
            }
        }
    }

@Test
    public void test2(){
        Goods[] arr = new Goods[5];
        arr[0] = new Goods("lenovoMouse",34);
        arr[1] = new Goods("dellMouse",43);
        arr[2] = new Goods("xiaomiMouse",12);
        arr[3] = new Goods("huaweiMouse",65);
        arr[4] = new Goods("microsoftMouse",43);
    
        Arrays.sort(arr);
    
        System.out.println(Arrays.toString(arr));
    }

### 10.2 Comparator ###

当元素的类型没有实现java.lang.Comparable接口而又不方便修改代码，或者实现了java.lang.Comparable接口的排序规则不适合当前的操作，那么可以考虑使用 Comparator 的对象来排序，强行对多个对象进行整体排序的比较。

重写compare(Object o1,Object o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。

还可以使用 Comparator 来控制某些数据结构（如有序 set或有序映射）的顺序，或者为那些没有自然顺序的对象 collection 提供排序。  
  
比较功能，对一些对象的集合施加了一个整体排序，可以将比较器传递给排序方法（如Collections.sort或Arrays.sort ），以便对排序顺序进行精确控制。  
  
Comparator接口中方法很多，但是我们只需要实现一个，也是最重要的一个compare，也许有的人会好奇为什么接口中的方法可以不用实现，因为这是JDK8以后的新特性，在接口中用default修饰的方法可以有方法体，在实现接口的时候可以不用重写，可以类比抽象类。  
compare(T o1, T o2) 比较其两个参数的顺序

/*
         * 我们去实现Comparable接口，可以满足我们大部分的业务场景；那么为什么还要使用Comparator接口呢?
         *  1、当元素的类型没有实现java.lang.Comparable接口而又不方便修改代码;比如JDK里面的Demo类，我们要要对它进行比较，但是我们没有办法修改源码；
         *  2、实现了java.lang.Comparable接口的排序规则不适合当前的操作；比如String和Integer都是按照从小到大进行比较的，我们想要想要从大到小比较；
         * @author Jimbo
         * @date 2022/1/17 10:22
         */
    @Test
    public void test4(){
        // 当我们使用Comparator接口的时候,重写compare(Object o1,Object o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
        // Integer类或String类的比较规则都是从小到大,我们想要想要改为从大到小,那么就使用定制排序Comparator；
        String[] strings = new String[]{"DD","AA","QQ","CC","WW"};
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -o1.compareTo(o2);
            }
        });
        System.out.println(Arrays.toString(strings));
    
    }

compare比较的o1和o2，返回值大于0则o1大于o2，依次类推，对于compare；来说this是谁不重要，所比较的两个对象都已经传入到方法中，所有Comparator就是有个外部比较器，在我们设计Goods初时，并不需要它有比较功能，在后期扩展业务是，Comparator的存在可以使我们在不修改源代码的情况下来完成需求，只需要新定义一个比较器来实现Comparator，重写compare方法并将Goods对象传进去。

@Test
        public void test5(){
            // Goods排序的规则：按照价格从低到高排序，如果价格相等，按照名称从高到低排序；
            // 我们不想用它里面定义的默认排序规则，那么我们就使用定制排序Comparator；
            // 按照名称从大到小排列；
            Goods[] goods = new Goods[6];
    
            goods[0] = new Goods("LenovoMouse",32);
            goods[1] = new Goods("HuaweiMouse",42);
            goods[4] = new Goods("XiaoMiMouse",12);
            goods[3] = new Goods("MicMouse",68);
            goods[2] = new Goods("AimMouse",12);
            goods[5] = new Goods("RazerMouse",108);
    
            Arrays.sort(goods, new Comparator<Goods>() {
                @Override
                public int compare(Goods o1, Goods o2) {
                    return -o1.getName().compareTo(o2.getName());
                }
            });
            System.out.println(Arrays.toString(goods));
        }

### 10.3 结论 ###

Java中大部分我们常用的数据类型的类都实现了Comparable接口，而仅仅只有一个抽象类RuleBasedCollator实现了Comparator接口 ，还是我们不常用的类，这并不是要用Comparable而不要使用Comparator，在设计初时有需求就选择Comparable，若后期需要扩展或增加排序需求是，再增加一个比较器Comparator，毕竟能写Arrays.sort(arg1),没人乐意写Arrays.sort(arg1,arg2)。

1、Comparator 和 Comparable 相同的地方  
他们都是java的一个接口, 并且是用来对自定义的class比较大小的。

2、Comparator 和 Comparable 不同的地方  
Comparable 定义在类的内部，我们称之为内部比较器；Comparator 是定义在类的外部，我们称之为外部比较器；  
Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器；我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。  
在设计初时有需求就选择Comparable，若后期需要扩展或增加排序需求是，再增加一个比较器Comparator；

## 十一、Collections工具类 ##

Collections 是一个操作 Set、List 和 Map 等集合的工具类。

Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。

它包含有各种有关集合操作的静态多态方法。此类不能实例化，服务于Java的Collection框架。

### 11.1 排序操作 ###

static void reverse(List<?> list) 反转指定列表中元素的顺序。

static void shuffle(List<?> list) 使用默认随机源对指定列表进行置换（随机排序）。

static <T extends Comparable<? super T>> void sort(List<T> list) 根据元素的自然顺序对指定列表按升序进行排序。

static <T> void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序。

static void swap(List<?> list, int i, int j) 在指定列表的指定位置处交换元素。

**示例代码：**

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    
    public class CollectionsTest {
        public static void main(String[] args) {
            ArrayList nums =  new ArrayList();
            nums.add(8);
            nums.add(-3);
            nums.add(2);
            nums.add(9);
            nums.add(-2);
            System.out.println(nums);
            
            Collections.reverse(nums);
            System.out.println(nums);
            
            Collections.sort(nums);
            System.out.println(nums);
            
            Collections.shuffle(nums);
            System.out.println(nums);
            
            //下面只是为了演示定制排序的用法，将int类型转成string进行比较
            Collections.sort(nums, new Comparator() {
    
                @Override
                public int compare(Object o1, Object o2) {
                    // TODO Auto-generated method stub
                    String s1 = String.valueOf(o1);
                    String s2 = String.valueOf(o2);
                    return s1.compareTo(s2);
                }
    
            });
            System.out.println(nums);
        }
    }

**执行结果：**

\[8, -3, 2, 9, -2\]  
\[-2, 9, 2, -3, 8\]  
\[-3, -2, 2, 8, 9\]  
\[9, -2, 8, 2, -3\]  
\[-2, -3, 2, 8, 9\]

### 11.2 查找和替换操作 ###

static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) 使用二分搜索法搜索指定列表，以获得指定对象。

static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 使用二分搜索法搜索指定列表，以获得指定对象。

static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) 根据元素的自然顺序，返回给定 collection 的最大元素。

static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) 根据指定比较器产生的顺序，返回给定 collection 的最大元素。

static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) 根据元素的自然顺序 返回给定 collection 的最小元素。

static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) 根据指定比较器产生的顺序，返回给定 collection 的最小元素。

static <T> void fill(List<? super T> list, T obj) 使用指定元素替换指定列表中的所有元素。

static int frequency(Collection<?> c, Object o) 返回指定 collection 中等于指定对象的元素数。  
  
static <T> void copy(List<? super T> dest, List<? extends T> src) 将所有元素从一个列表复制到另一个列表。

static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) 使用另一个值替换列表中出现的所有某一指定值。

**示范简单用法：**

package collection.collections;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    public class CollectionsTest {
        public static void main(String[] args) {
            ArrayList num =  new ArrayList();
            num.add(3);
            num.add(-1);
            num.add(-5);
            num.add(10);
            System.out.println(num);
            System.out.println(Collections.max(num));
            System.out.println(Collections.min(num));
            Collections.replaceAll(num, -1, -7);
            System.out.println(Collections.frequency(num, 3));
            Collections.sort(num);
            System.out.println(Collections.binarySearch(num, -5));
        }
    }

**执行结果：**

\[3, -1, -5, 10\]  
10  
\-5  
1  
1

### 11.3 同步控制 ###

Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。

static <T> Collection<T> synchronizedCollection(Collection<T> c) 返回指定 collection 支持的同步（线程安全的）collection。  
  
static <T> List<T> synchronizedList(List<T> list) 返回指定列表支持的同步（线程安全的）列表。  
  
static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) 返回由指定映射支持的同步（线程安全的）映射。  
  
static <T> Set<T> synchronizedSet(Set<T> s) 返回指定 set 支持的同步（线程安全的）set。  
  
static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) 返回指定有序映射支持的同步（线程安全的）有序映射。  
  
static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) 返回指定有序 set 支持的同步（线程安全的）有序 set。

下面是Collections将普通集合包装成线程安全集合的用法。

import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    public class SynchronizedTest {
        public static void main(String[] args) {
            Collection c = Collections.synchronizedCollection(new ArrayList());
            List list = Collections.synchronizedList(new ArrayList());
            Set s = Collections.synchronizedSet(new HashSet());
            Map m = Collections.synchronizedMap(new HashMap());
        }
    }

## 十二、面试题 ##

**1、什么是集合框架?**  
Java集合框架（Java Collections Framework，JCF）是为表示和操作集合而规定的一种统一的标准的体系结构。

**2、集合的三大块内容?**  
任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。  
对外的接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象。  
实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。  
算法：是在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法，例如查找、排序等。这些算法通常是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上，算法是可复用的函数。如果你学过C++，那C++中的标准模版库（STL）你应该不陌生，它是众所周知的集合框架的绝好例子。

**3、数组和集合的区别?**  
集合和数组都是容器,都可以用来存储和操作数据。  
一、数组声明了它容纳的元素的类型，而集合不声明；简而言之: 数组必须指明存储类型，但是集合可以指明也可以不指明其存储类型；(如果集合没有指明其存储类型Object，如果想要指明其存储类型，可以使用我们学过的泛型)  
二、数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。而集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。  
三、数组可以存储基本数据类型，也可以存储引用数据类型。而集合只能存储引用类型；  
四、数组是java语言中内置的数据类型,是线性排列的,执行效率或者类型检查都是最快的。

**4、Java集合框架的6个接口和9个类（\*\*\*）?**  
6个接口:  
Collection接口:  
Collection 接口是集合层次结构中的根接口。Collection 是用来存储单列数据对象；  
一些 collection 存储有序、可以重复的元素（List），而另一些则存储无序、不可以重复的元素（Set）。  
JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List）实现。  
Collection接口继承Iterable接口  
public interface Collection<E> extends Iterable<E>;  
Iterable 接口,实现此接口允许对象成为“for-each loop”语句的目标。  
Collection接口依赖于Iterator接口;  
Iterator<E> iterator();

List接口:  
List 接口是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。  
List接口继承Collection接口；  
public interface List<E> extends Collection<E>

Set接口:  
Set 接口是无序的，不能包含重复的元素。  
Set接口继承Collection接口；  
public interface Set<E> extends Collection<E>

Iterator接口:  
Collection所有的集合类，都依赖了Iterator接口，这是一个用于遍历集合中元素的接口；  
public interface Iterator<E>

ListIterator接口:  
ListIterator接口是列表迭代器，允许按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。  
ListIterator接口继承Iterator接口;  
public interface ListIterator<E> extends Iterator<E>

Map接口:  
Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。  
Map包含了key-value对，Map不能包含重复的key，但是可以包含相同的value。  
public interface Map<K,V>

9个实现类:  
ArrayList类:  
ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。  
随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。  
ArrayList擅长于随机访问。同时ArrayList是非同步的。

LinkedList类:  
LinkedList是一个双向链表。  
LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端，节约一半时间）。  
这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。  
LinkedList也是非同步的。

Vector类:  
与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

HashSet类:  
HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的。集合元素可以是null,但只能放入一个null。  
它内部元素的顺序是由哈希码来决定的（根据哈希码,结合某种算法,得到存储元素的下标），所以它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。

LinkedHashSet类:  
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。  
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

TreeSet类:  
TreeSet 是二叉树实现的，基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现，不允许放入null值。  
它是使用元素的自然顺序对元素进行排序，或者根据创建Set时提供的 Comparator 进行排序，具体取决于使用的构造方法。  
TreeSet存储的元素是有序的。

HashMap类:  
以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry\[\] table），  
元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。

LinkedHashMap类:  
LinkedHashMap和HashMap存储类似，只是在HashMap的基础上引用了链表维护元素的次序。

TreeMap类:  
有序散列表，实现SortedMap接口，底层通过红黑树实现。

**5、List、Set、Map的区别（\*\*\*）?**  
List、Set都是继承自Collection接口，Map则不是；  
List特点：元素有放入顺序，元素可重复；  
Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉；  
Map特点：元素是以key-value形式存储数据，key不可以重复，value可以重复；

**6、Collection接口里面的contains方法的比较依据是什么?**  
通过equals来进行比较; 如果没有重写equals,比较的是地址; 如果重写了,一般来说比较的是内容;

**7、foreach遍历集合的底层实现?**  
foreach遍历集合的底层调用Iterator完成操作。

**8、ArrayList、LinkedList、Vector的区别（\*\*\*）?**  
ArrayList、LinkedList、Vector都是List接口的实现类;  
ArrayList底层是基于数组的,通过Object\[\] elementData来存储元素;ArrayList是对象引用的一个”变长”数组(自动扩容)，它是用来存储有序（按照添加的先后顺序排列），可以重复的元素；  
对于频繁的遍历/获取或修改元素的操作，建议使用ArrayList类，效率高。  
LinkedList底层是基于双向链表，存储的每个元素都在链表中作为一个节点存在，每个节点维护了一个prev和next指针。这个链表，维护了first和last指针，first指向第一个元素，last指向最后一个元素。  
对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高。  
Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程同步的，安全但是效率低。  
ArrayList和LinkedList都不是线程同步的，不安全，效率高。  
我们在使用List集合的时候，ArrayList是我们要优先考虑的；但是当插入、删除频繁时，使用LinkedList；  
如果我们考虑线程安全问题，那么也不适用Vector，而是使用Collections.synchronizedList(List<T> list) 来让ArrayList成为线程安全的即可 或 线程安全的集合类（java.util.concurrent）；  
ArrayList和Vector都会自动扩容，但是LinkedList不存在扩容；  
如果集合中的元素的数目大于目前集合数组的长度时，Vector增长率为目前数组长度的100%，而Arraylist增长率为目前数组长度的50%。

Vector和ArrayList的区别?  
Vector和ArrayList底层都是基于数组；  
1、Vector是线程同步的，所以它也是线程安全的，而Arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。  
2、如果集合中的元素的数目大于目前集合数组的长度时，Vector增长率为目前数组长度的100%，而Arraylist增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据，用vector有一定的优势。

ArrayList和LinkedList的区别?  
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于双向链表的数据结构。  
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为ArrayList要移动指针。  
3.对于插入和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

**9、数组和List相互转换?**  
把集合转换为数组:  
集合对象.toArray() 返回包含此 collection 中所有元素的数组。  
把数组转换为集合:  
Arrays.asList(数组) 把数组转换为List集合;

**10、ArrayList的JDK1.8之前与之后的实现区别?**  
JDK1.7：当我们通过无参构造器实例化ArrayList对象的时候,创建一个初始容量为10的数组。  
JDK1.8：当我们通过无参构造器实例化ArrayList对象的时候,一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组。

**11、ArrayList添加元素的过程(add方法的源码解析-jdk8)?**  
如果是第一次添加元素，数组的长度被扩容到默认的capacity，也就是10。  
当发觉同时添加一个或者是多个元素，数组长度不够时，就扩容，这里有两种情况：  
只添加一个元素，例如：原来数组的capacity为10，size已经为10，不能再添加了。需要扩容，新的capacity=old capacity+old capacity>>1 = 10+10/2 = 15.即新的容量为15。  
当同时添加多个元素时，原来数组的capacity为10，size为10，当同时添加6个元素时。它需要的min capacity为16，而按照capacity=old capacity+old capacity>>1=10+10/2=15。new capacity小于min capacity，则取min capacity。  
对于添加，如果不指定下标，就直接添加到数组后面，不涉及元素的移动，如果要添加到某个特定的位置，那需要将这个位置开始的元素往后挪一个位置，然后再对这个位置设置。

**12、ArrayList删除元素的过程(remove方法的源码解析)?**  
remove(int index)：首先需要检查Index是否在合理的范围内。其次再调用System.arraycopy将index之后的元素向前移动。  
remove(Object o)：首先遍历数组，获取第一个相同的元素，获取该元素的下标。其次再调用System.arraycopy将index之后的元素向前移动。

**13、List集合的遍历方式有哪些?**  
1）Iterator：迭代输出，是使用最多的输出方式。  
2）ListIterator：是Iterator的子接口，专门用于输出List中的内容。  
3）foreach输出：JDK1.5之后提供的新功能，可以输出数组或集合。  
4）for循环

**14、怎么理解Set集合是无序的，不可以重复的?**  
Set所谓的没有顺序指的是没有按照我们的存储顺序(片面)；按照我们之前学习List的经验来说，List是先存储的，先获取到；但是对于Set来说，你先存储的,可能不是先获取的;  
严谨的答案:  
无序: Set底层是数组来存储元素的，向Set存储元素，并不是按照下标顺序来存储元素的，而是通过元素的HashCode值，结合某种算法，得到存储元素的下标；  
不可重复：向Set集合存储元素，会先判断hashCode得到的哈希码是否相等，如果相等再通过equals()比较是否相等；如果equals()也是true,那么就不会向集合中添加；

**15、HashSet添加元素的过程?**  
我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，  
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），  
判断数组此位置上是否已经有元素：  
如果此位置上没有其他元素，则元素a添加成功。 --->情况1  
如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：  
如果hash值不相同，则元素a添加成功。--->情况2  
如果hash值相同，进而需要调用元素a所在类的equals()方法：  
equals()返回true,元素a添加失败  
equals()返回false,则元素a添加成功。--->情况3

对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。  
jdk 7 :元素a放到数组中，指向原来的元素。  
jdk 8 :原来的元素在数组中，指向元素a  
总结：七上八下

**16、HashSet和TreeSet的区别?**  
HashSet基于HashMap,用键来存放HashSet的值。  
TreeSet基于TreeMap,也是用键来存放TreeSet的值。

**17、HashMap、HashTable和TreeMap的区别（\*\*\*）?**  
HashSet是基于HashMap来实现的，HashMap底层是数组Node<K,V>\[\] table，更像是对HashMap做了一次“封装”，而且只使用了HashMap的key来实现各种特性，  
而HashMap的value始终都是PRESENT。HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。  
HashSet不允许重复，允许null值，非线程安全。  
底层扩容机制：原本容量的2倍；  
LinkedHashSet 是 HashSet 的子类。LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。  
简单来说：在HashSet的基础上,引入了链表来维护元素的次序；  
LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。  
TreeSet底层使用红黑树结构存储数据，TreeSet 可以确保集合元素处于排序状态。  
TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。  
  
**18、HashSet集合判断两个元素相等的标准?**  
两个对象通过 hashCode()得到的哈希值比较相等，并且两个对象的 equals() 方法返回值也相等。  
注意：对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

**19、Set集合的遍历方式有哪些?**  
1）Iterator：迭代输出，是使用最多的输出方式。  
2）foreach输出：JDK1.5之后提供的新功能，可以输出数组或集合。

**20、CopyOnWriteArrayList的理解（\*\*\*）?**  
CopyOnWriteArrayList是线程同步的数组集合。CopyOnWriteArrayList使用场景主要是多线程环境下,为了保证线程安全;  
CopyOnWriteArrayList默认容量是0,从0开始;  
CopyOnWriteArrayList没有规定最大容量;  
CopyOnWriteArrayList扩容机制,每次+1;  
CopyOnWriteArrayList里面的新增、修改、删除方法都是线程同步的,但是获取方法并没有线程同步,也不需要;

**21、请说出ArrayList和LinkedList里面中的常用方法?**  
boolean add(E e) 将指定的元素添加到此列表的尾部。  
void clear() 清除此列表中的所有元素。  
boolean contains(Object o) 如果此列表中包含指定的元素，则返回 true  
E get(int index) 返回此列表中指定位置上的元素。  
int indexOf(Object o) 返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。  
boolean isEmpty() 如果此列表中没有元素，则返回 true  
E remove(int index) 移除此列表中指定位置上的元素。  
E set(int index, E element) 用指定的元素替代此列表中指定位置上的元素。  
int size() 返回此列表中的元素数。

**22、ArrayList的add()和addAll()区别?**  
add()可以是任意数据类型的参数;addAll()只能是Collection类型的参数  
如果两种都是Collection类型参数,那么add()是把参数作为整体放进来,addAll()是把参数集合中的每个元素添加进来;

**23、Comparable 和 Comparator的异同?**  
Comparable和Comparator都是用于比较对象的大小的；  
Comparable位于java.lang，我们称之为自然排序；  
Comparator位于java.util，我们称之为定制排序；  
实现Comparable接口需要重写compareTo方法；  
实现Comparator接口需要重写compare方法；  
这两个方法的返回值都是int，用int类型的值来确定比较结果；  
如果返回值是正整数,那么表示当前对象大于参数对象;  
如果返回值是0,那么表示当前对象等于参数对象;  
如果返回值是负整数,那么表示当前对象小于参数对象;  
Comparable 定义在类的内部，我们称之为内部比较器；Comparator 是定义在类的外部，我们称之为外部比较器；  
在设计初时有需求就选择Comparable，若后期需要扩展或增加排序需求是，再增加一个比较器Comparator；

**24、HashMap和Hashtable的异同?**  
HashMap和Hashtable都实现了Map接口，都是用来存储双列数据的；  
HashMap的key和value，都可以存储null；Hashtable的key和value，都不可以存储null；  
HashMap是非线程同步的，效率高；Hashtable是线程同步的，效率低；

**25、HashMap、Hashtable、TreeMap、LinkedHashMap的区别?**  
HashMap、Hashtable、TreeMap、LinkedHashMap都实现了Map接口，都是用来存储双列数据的，key不可以重复，value允许重复；  
HashMap是 Map 接口使用频率最高的实现类。  
底层是Node<K,V>\[\]数组来存储数据；  
允许使用null键和null值，不保证映射的顺；  
线程非安全，效率高；  
扩容机制：旧容量 \* 2；  
Hashtable是个古老的 Map 实现类，JDK1.0就提供了。  
它和HashMap非常类似；  
底层是Entry<?,?>\[\]数组来存储数据；  
不允许使用null键和null值，不保证映射的顺；  
线程安全，效率低；  
LinkedHashMap 是 HashMap 的子类。  
在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。  
它是由内部类 Entry<K,V> extends HashMap.Node<K,V>来记录元素的添加顺序；  
TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。  
TreeSet底层使用红黑树结构存储数据。  
自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException。  
定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口。  
TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。

**26、Map集合的containsKey和containsValue的判断标准?**  
HashMap 判断两个 key 相等的标准是：hashCode 值相等，两个 key 通过 equals() 方法返回 true。  
HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。

**27、ArrayList底层实现原理（\*\*\*）?**  
ArrayList底层是一个动态自增的数组，该类封装了一个动态再分配的Object\[\] elementData数组；  
当调用无参空构造器实例化ArrayList的时候；  
JDK1.7：创建一个初始容量为10的数组。  
JDK1.8：一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组。  
当我们调用有参数构造器实例化ArrayList的时候，都是创建指定长度的数组；  
添加元素的过程:  
add(E e): 向数组的末尾添加元素(添加)  
每次调用add(),都会先判断底层数组的容量是否足够；  
第1次添加,会创建一个始容量为10的数组。  
第2-10次添加,都不会再进行扩容;  
第11次添加,会进行扩容;  
...  
最终元素都是按照下标顺序存储到数组里面；  
size++;  
add(int index, E element): 向指定下标添加元素(插入)  
先判断下标是否符合要求；  
再判断底层数组的容量是否足够；  
...  
插入需要把指定下标及其之后的元素都向后挪动一位，底层调用System.arraycopy();  
然后把要插入的元素放到指定下标;  
size++;  
addAll(): 和上述的add()类似,无非就是一次性添加多个而已;  
删除元素的过程:  
remove(int index): 根据下标删除元素  
先判断下标是否符合要求，只有参数大于最大小标才抛出异常；  
删除指定下标的元素，指定下标之后的每个元素都向前挪动一位，底层调用的System.arraycopy()，最后一位赋值为null；  
remove方法返回的是删除的元素；  
size--;  
remove(Object o): 删除集合里面第一次出现的元素；  
先判断参数是不是null；  
如果是null,则==循环判断是否存在；  
如果不是null，则equals循环判断是否存在；  
找到要删除的元素的下标，删除即可(和上述的remove(index)一致)；  
size--;  
clear(): 清空集合;  
把底层数组里面已经赋值的所有元素都赋值为null；  
size = 0;  
修改元素的过程:  
set(int index, E element): 修改指定下标的元素  
先判断下标是否符合要求；  
直接给数组指定下标重新赋值；  
set方法返回的是被替换掉的元素；  
查询元素的过程:  
get(int index): 获取指定下标的元素  
先判断下标是否符合要求；  
返回数组指定下标的元素；  
size(): 获取当前集合的元素个数  
返回成员遍历size的值；  
其他方法:  
indexOf(Object o): 获取指定元素在集合中首次出现的位置；  
lastIndexOf(Object o): 获取指定元素在集合中最后一次出现的位置；  
先判断要查找的元素是不是null;  
如果是null,==循环比较;如果不是null,equals循环比较；  
找到元素返回元素所在的下标索引,如果没有找到则返回-1;  
indexOf()是正向遍历; lastIndexOf()是反向遍历;

什么时候扩容?  
当数组存储满的时候,再向其添加元素,才会扩容;

扩容机制?  
ArrayList里面的grow()就是扩容的具体实现;  
1、默认的计算方式: 新容量 = 旧容量 \* 1.5,  
2、如果新的容量不满足最小容量,把最小容量作为新的容量；  
3、如果新的容量大于最大容量,新的容量Integer.MAX\_VALUE;  
4、通过Arrays.copyOf(elementData, newCapacity)进行扩容；

**28、Vector底层原理(源码分析)?**  
Vector 很多方法都跟 ArrayList 一样，只是多加了个 synchronized 来保证线程安全罢了。  
Vector底层是一个动态自增的数组，该类封装了一个动态再分配的Object\[\] elementData数组；  
调用Vector的任何一个构造器,都是创建一个指定容量的数组；  
Vector 比 ArrayList 多了一个属性：  
protected int capacityIncrement;这个属性是在扩容的时候用到的，它表示每次扩容只扩 capacityIncrement 个空间就足够了。该属性可以通过构造方法给它赋值。  
什么时候扩容?  
当数组存储满的时候,再向其添加元素,才会扩容;  
扩容机制?  
Vector里面的grow()就是扩容的具体实现;  
如果没有指定capacityIncrement(容量自增量),那么默认情况下,扩容后的容量 = 旧容量 \* 2;  
如果指定了capacityIncrement(容量自增量),那么扩容后的容量 = 旧容量 + capacityIncrement;  
Vector里面的添加、删除、修改、查询基本上和ArrayList类似；  
添加有一点区别: ArrayList在JDK8版本初始化的时候没有创建指定长度的数组,第一个添加的时候才创建长度为10的数组;Vector是初始化的时候就创建了指定长度的数组；

**29、LinkedList底层实现原理（\*\*\*）?**  
LinkedList底层是基于双向链表实现的。它也可以被当作堆栈、队列或双端队列进行操作。  
LinkedList 是非同步的。  
双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个 first 指针，指向头节点，和 last 指针，指向尾节点。  
LinkedList是基于双向链表的,不存在扩容问题；  
添加元素的过程:  
表头添加元素的过程:  
当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点;  
表尾添加元素的过程:  
当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last 指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点；  
指定节点插入元素的过程:  
判断要插入的下标是否满足需求；  
如果插入的下标==size,那么就是向尾部添加;  
当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点;  
删除元素的过程:  
删除操作与添加操作大同小异，需要把当前节点的前驱节点的后继修改为当前节点的后继，以及当前节点的后继结点的前驱修改为当前节点的前驱：  
删除头和尾很简单,和删除元素大同小异;本质就是解绑和重新绑定的过程;  
修改元素的过程:  
判断要修改的下标是否满足需求；  
找到指定下标的Node节点；  
把指定节点的item改为新的值即可；  
查询元素的过程:  
get(int index): 获取指定下标的元素；  
判断要查询的下标是否满足需求；  
到指定下标的Node节点，把Node节点的item值返回即可；  
getFirst()/getLast(): 获取头部的元素和尾部的元素；  
判断first和last是否为null，如果不为null，则直接获取first或last的item值即可；  
相比数组，链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的效率就不如数组那么高了。

**30、RandomAccess接口的作用（\*）?**  
这个是一个标记性接口,它的作用就是用来快速随机存取;  
实现此接口,那么使用普通的for循环来遍历,性能更高,例如ArrayList。  
没有实现该接口的话,使用Iterator来迭代,这样性能更高,例如LinkedList。

**31、Iterable接口的作用（\*）?**  
实现此接口允许的对象允许成为“for-each loop”语句的目标。

**32、transient关键字的作用（\*）?**  
将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会被序列化。

**33、数组复制的相关方法（\*\*\*）?**  
Arrays类 copyOf(U\[\] original, int newLength, 类<? extends T\[\]> newType) 复制指定的数组,用空值截断或填充（如有必要）,以便复制具有指定的长度。  
original - 要复制的数组  
newLength - 要返回的副本的长度  
newType - 要返回的副本的类  
注:生成一个新的数组

System类 arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 将指定源数组中的数组从指定位置复制到目标数组的指定位置。  
src - 源数组。  
srcPos - 源数组中的起始位置。  
dest - 目标数组。  
destPos - 目的地数据中的起始位置。  
length - 要复制的数组元素的数量。  
集合框架的底层扩容机制经常调用该方法;

**34、ArrayList中removeAll(collection c)和clear()的区别?**  
removeAll可以删除批量指定的元素,而clear是全是删除集合中的元素。

**35、HashMap底层原理(非常非常...重要)?**  
HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null 键和null 值，因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。  
影响 HashMap 性能的两个重要参数：“initial capacity”（初始化容量）和”load factor“（负载因子）。简单来说，容量就是哈希表桶的个数，负载因子就是键值对个数与哈希表长度的一个比值，当比值超过负载因子之后，HashMap 就会进行 rehash操作来进行扩容。  
JDK 7及以前版本：HashMap是数组+链表结构(即为链地址法)。  
当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。  
每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。而且新添加的元素作为链表的head。  
添加元素的过程:  
向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry\[\]数组中要存储的位置i。  
如果位置i上没有元素，则entry1直接添加成功。 - 情况一  
如果位置i上已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次比较entry1中key和其他的entry的key的hash值。  
如果彼此hash值都不同，则直接添加成功，entry1指向原有的entry元素。 - 情况二  
如果hash值相同，继续比较二者是否equals。  
如果遍历一遍以后，发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素。 - 情况三  
如果返回值为true，则使用entry1的value去替换equals为true的entry的value。

HashMap什么时候进行扩容呢?  
当HashMap中的元素个数(size)超过数组大小\*loadFactor时，就会进行数组扩容。

HashMap的扩容机制:  
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。  
扩容为原有长度的两倍；

JDK 8版本发布以后：HashMap是数组+链表+红黑树实现。  
当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。  
每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。  
添加元素的过程:  
向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry\[\]数组中要存储的位置i。  
如果位置i上没有元素，则entry1直接添加成功。 - 情况一  
如果位置i上已经存在entry2(或还有链表存在的entry3，entry4)，先和当前下标的存储的元素的key比较,如果hash和equals都一致,则使用新的value替换旧的value； - 情况三  
如果遍历一遍以后，发现所有的hash或equals返回都为false,则entry1仍可添加成功。原有的entry元素指向entry1。 - 情况二

HashMap什么时候进行扩容和树形化呢?  
当HashMap中的元素个数超过数组大小\*loadFactor 时，就会进行数组扩容。扩容为原有长度的两倍；  
当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。

删除元素的过程:  
先根据key的hash值去查找要删除元素所在的桶的下标；  
如果当前 key 映射到的桶不为空，从桶中根据key的hash和equals找对应的节点；  
如果桶中是红黑树结构，按照红黑树方式来查找；如果是链表则按照链表方式来查找；  
比对找到的 key 的 value 跟要删除的是否匹配：  
通过调用红黑树的方法来删除节点；  
使用链表的操作来删除节点；

获取元素的过程:  
1、通过 hash 值获取该 key 映射到的桶。  
2、桶上的 key 就是要查找的 key，则直接命中。  
3、桶上的 key 不是要查找的 key，则查看后续节点：  
（1）如果后续节点是树节点，通过调用树的方法查找该 key。  
（2）如果后续节点是链式节点，则通过循环遍历链查找该 key。  
4、如果找到key对应的节点，就把对应节点对应的value返回；

如果HashMap扩容了,是否需要重新计算元素存储的位置?  
HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

**36、HashMap JDK1.8相较于之前的变化?**  
1、HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组。  
2、当首次调用map.put()时，再创建长度为16的数组；  
3、数组为Node类型，在jdk7中称为Entry类型；  
4、形成链表结构时，新添加的key-value对在链表的尾部（七上八下）；  
5、当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。

**37、LinkedHashMap底层原理(源码分析)?**  
LinkedHashMap 是 HashMap 的子类。  
在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。  
它是由内部类 Entry<K,V> extends HashMap.Node<K,V>来记录元素的添加顺序；  
LinkedHashMap如何来维护有序性的?  
当我们使用put方法存储元素的时候,发现LinkedHashMap没有重写put(K key, V value),那么调用的是HashMap的put方法;  
put方法底层调用的是putVal(),发现LinkedHashMap也没有重写putVal方法,,那么调用的是HashMap的putVal方法;  
向Map集合存储元素,如果key不存在(hash和equals都为true才存在),则可以存储,那么存储元素调用的都是newNode();  
HashMap里面有newNode(),LinkedHashMap里面也重写了newNode(),那么肯定调用的LinkedHashMap类的newNode();  
在LinkedHashMap类的newNode()里面会创建LinkedHashMap.Entry,然后修改before和after的指针;  
通过这样的方式,就可以维护有序性;

为什么在HashMap中要定义三个afterNodeXxx()空方法?  
其实这三个方法表示的是在访问、插入、删除某个节点之后，进行一些处理，它们在 LinkedHashMap 都有各自的实现。  
LinkedHashMap 正是通过重写这三个方法来保证链表的插入、删除的有序性。  
把相同的行为定义在父类,把不同的特性提取出来为一个方法,然后子类去重写父类的方法即可; 重写之后子类再去调用,那么就是调用的子类的;

**38、Hashtable底层原理(源码分析)?**  
Hashtable我们可以认为是线程安全的HashMap，HashTable 是一个线程安全的哈希表，它通过使用synchronized 关键字来对方法进行加锁，从而保证了线程安全。  
底层数据结构就是数组+链表；  
但这也导致了在单线程环境中效率低下等问题。  
Hashtable 与 HashMap 不同，它不允许插入 null 值和 null 键。

**39、如果我们想要使用线程安全的集合类怎么办?**  
方式一: 使用Collections.synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。  
方式二: 使用java.util.concurrent包下的线程安全的集合类。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/31f1662f3ad5480eb47df9a24964f3ed.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/7b19d30bd82a4c28b9f8ecbab876fa10.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_11_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/e2823130667b4fae8b9873034541f11a.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/4d3e8cdca4f64eb0b0af9b2d3f4af59d.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/16a53e085b314a1e89c53c33a29074a3.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/e9d13240e4ea45388c686b5577c422b2.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/1f02e34ed611417fbe89dd87f15c6a23.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_15_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/55c0ce71ad8444ab95d9a1e53d1b6fd8.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/2c0ca75a471645599d4d44388db03181.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/ef7f0bfbc41744628d8bbd4f67f7498e.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/9e1bae14780b44918fbb26abbb9f65a0.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/6365ec468fe843f8b205b9a6c07d1d8b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/818eb947d7624b958f5cfc23822d231d.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/41f38fe2f35e4a8ca10b21fa8bc097a5.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 12]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/97aef0645066421585815275aa924e44.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oiR5piv5rOi5ZOp5Liq5rOi_size_16_color_FFFFFF_t_70_g_se_x_16 13]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/22b1c25ada5f47b2a81d2e03297c214f.png