集合框架

为什么使用集合框架？

假设，一个班级有30个人，我们需要存储学员的信息，是不是我们可以用一个一维数组就解决了？

那换一个问题，一个网站每天要存储的新闻信息，我们知道新闻是可以实时发布的，我们并不知道需要多大的空间去存储，如果设置一个很大的数组，要是没有存满，或者不够用，都会造成影响，前者浪费空间，后者影响了业务！

如果并不知道程序运行时会需要多少对象，或者需要更复杂的方式存储对象，就可以使用Java的集合框架！

Java集合框架概述

• 集合、数组都是对多个数据进行存储操作的结构，简称Java容器。
  • 此时的存储，主要是指内存层面的存储，不涉及持久化的存储。
• 一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。
• 另一方面，使用Array存储对象具有一些弊端，而Java集合就像一种容器，可以动态地把多个对象的引用放入容器中。
  • 数组在内存存储方面的特点：
    • 数组初始化以后，长度就确定了。
    • 数组声明的类型，就决定了进行元素初始化的类型。
  • 数组在存储数据方面的弊端：
    • 数组初始化以后，长度就不可变了，不便于拓展。
    • 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高；同时无法直接获取存储元素的个数。
    • 数组存储的元素是有序的、可重复的，对于无序、不可重复的存储需求，数组无法满足。 ——> 存储数据的特点单一
• Java集合类可以用于存储数量不等的多个对象，还可以用于保存具有映射关系的关联数组。

集合框架包含的内容

Java集合框架提供了一套性能优良，使用方便的接口和类，位于java.util包中。

【接口和具体类】

Java集合可分为Collection和Map两种体系

• Collection接口：单列数据，存储一组无序、可重复的对象
  • List接口：存储有序、可重复的的数据 —> “动态”数组
    • ArrayList：长度可变的数组，在内存中分配连续的空间；遍历元素和随机访问元素的效率比较高

  - LinkedList：**采用链表存储方式**。插入、删除元素时效率比较高

  - Vector

• Set接口：存储无序、不可重复的数据 —> 高中讲的“集合”
  • HashSet:采用哈希算法实现的Set
    • HashSet的底层是用HashMap实现的，因此查询效率较高，由于采用hashCode算法直接确定元素的内存地址，增删效率也挺高的。
  • LinkedHashSet
  • TreeSet
  • Map接口：双列数据，存储键值对象，保存具有映射关系的 “key - value对 ” 的集合
• HashMap
• LinkedHashMap
• TreeMap
• Hashtable
• Properties

Collection接口

• Collection接口是List、Set和Queue接口的父接口，该接口里定义的方法既可以用于操作Set集合，也可以用于操作List和Queue集合。
• JDK不提供此接口的任何直接实现，而是提供更具体的子接口（如：Set和List）实现。
• 在Java5之前，Java集合会丢失容器中所有对象的数据类型，把所有对象都当成Object类型处理；从JDK5.0增加了泛型以后，Java集合可以记住容器中对象的数据类型。

public void test(){
  Collection coll = new ArrayList();
  //add(object e):将元素e添加到集合Coll中；
  coll.add("AA");
  coll.add("BB");
  coll.add(123);//自动装箱
  coll.add(new Date());
  //size():获取添加的元素个数
  System.out.println(coll.size());//4
  //addAll(Collection coll1):将coll1集合中的元素添加到当前的集合中
  Collection coll1 = new ArrayList();
  coll1.add(456);
  coll1.add("CC");
  coll.addAll(coll1);
  System.out.println(coll1.size());//6
  //clear():清空集合元素
  coll.clear();
  //isEmpty():判断当前集合是否为空
  System.out.println(coll.isEmpty());
}

Collection接口中的方法：

• 添加
  • add(object e):将元素e添加到集合Coll中；
  • addAll(Collection coll1):将coll1集合中的元素添加到当前的集合中
• 获取有效元素个数
  • size():获取元素个数
• 清空集合
  • clear():清空集合元素
• 是否是空集合
  • isEmpty():判断当前集合是否为空
• 是否包含元素
  • contains(Object obj):通过元素的equals方法来判断是否包含obj
  • containsAll(Collection c):判断集合c中的所有元素是否都存在于当前集合中。调用元素的equals方法来比较，两个集合的元素挨个比较
• 删除
  • remove(Object obj):从当前集合中删除obj元素， 通过元素的equals方法判断是否是要删除的那个元素，只会删除找到的第一个元素
  • removeAll(Collection coll):从当前集合中移除集合coll中的所有元素，即取当前集合的差集
• 取两个集合的交集
  • retainAll(Collection coll):获取当前集合和集合coll的交集，把交集的结果返回给当前集合，不影响集合coll
• 集合是否相等
  • equals(Object obj): 要想返回true，需要当前集合和形参集合的元素都相同。
• 转成对象数组
  • toArray():将当前集合转化成数组。 （ 集合 —> 数组）

    拓展：数组 —> 集合：调用Arrays类的静态方法asList()；

List<String> list = Arrays.asList(new String[]{"AA","BB","CC"});

• 获取集合对象的哈希值
  • hashCode():返回当前对象的哈希值。
• 遍历
  • Iterator():返回迭代器对象，用于集合元素的遍历

iterator迭代器接口

• iterator对象称为迭代器（设计模式的一种），主要用于遍历Collection集合中的元素。
• GOF给迭代器模式的定义为：提供一种方法访问一个容器（container）对象中各个元素，而又不需要暴露该对象的内部细节。迭代器模式，就是为容器而生。
• Collection接口继承了java.lang.Iterator接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator方法，用以返回一个实现Iterator接口的对象
• Iterator仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象，则必须有一个被迭代的集合。
• 集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator迭代器接口定义了如下方法：

• boolean hashNext();//判断是否有元素没有被遍历
• Object next();//返回游标当前位置的元素并将游标移动到下一个位置
• void remove();//删除游标左边的元素，在执行完next之后该操作只能执行一次

1.迭代器的执行原理

• next()操作：
  • （1）指针下移；
  • （2）将下移以后集合位置上的元素返回；

    Iterator iterator = coll.iterator();
    while(iterator.hasNext()){
    System.out.println(iterator.next());
    }

2.迭代器中的remove()方法

• 内部定义了remove()方法，可以在遍历的时候，删除集合中的元素，此方法不同于集合直接调用remove()方法

  public void test(){
  Collection coll = new ArrayList();
  coll.add(123);
  coll.add(456);
  coll.add(new String("Tom"));
  coll.add(false);
  //删除集合中的“Tom”
  Iterator iterator = coll.iterator();
  while(iterator.hasNext()){
    Object obj = iterator.next();
    if("Tom".equals(obj)){
      iterator.remove();
    }
  }
  //遍历集合
  iterator = coll.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }
  }

注意：

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

3.使用for-each遍历集合元素-增强for循环

• Java5.0提供了for- each循环迭代访问Collection和数组
• 遍历操作不需要获取Collection或数组的长度，无需使用索引访问元素
• for-each循环遍历的底层调用Iterator完成操作
• for- each还可以用来遍历数组

//for(集合元素的类型 局部变量 ： 集合对象)
for(Object obj : coll){
  System.out.println(obj);
}

问题：如何遍历Map集合呢？
分析：

• 方法1：通过迭代器Iterator实现遍历

  • 获取Iterator ：Collection 接口的iterator()方法
  • Iterator的方法：
    • boolean hasNext(): 判断是否存在另一个可访问的元素
    • Object next(): 返回要访问的下一个元素

      Set keys=dogMap.keySet(); //取出所有key的集合
      Iterator it=keys.iterator(); //获取Iterator对象
      while(it.hasNext()){
      String key=(String)it.next(); //取出key
      Dog dog=(Dog)dogMap.get(key); //根据key取出对应的值
      System.out.println(key+"\t"+dog.getStrain());
      }

• 方法2：增强for循环

  for(元素类型t 元素变量x : 数组或集合对象){
          引用了x的java语句
  }

List接口

• 鉴于Java中数组用来存储数据的局限性，我们通常用List替代数组。
• List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
• JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

  面试题：ArrayList、LinkedList和Vector三者之间的异同？

  • 同：三个类都实现了List接口，存储数据的特点相同：存储有序的、可重复的数据。
  • 不同：
    • ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[]存储；
    • LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储；
    • Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[]存储；

List接口方法

• List除了从Collection集合继承的方法外，List集合里添加了一些根据索引来操作集合元素的方法。
  • add(int index,Object ele):在index位置插入ele元素
  • addAll(int index,Collection eles):从index位置开始将eles中的所有元素添加进来
  • get(int index):获取指定index位置的元素
  • indexOf(Object obj):返回obj在集合中首次出现的位置，如果不存在返回-1
  • lastIndexOf(Object obj):返回obj在集合中最后一次次出现的位置，如果不存在返回-1
  • remove(int index):移除指定index位置的元素，并返回此元素
  • set(int index,Object ele):设置指定index位置的元素为ele
  • subList(int formIndex,int toIndex):返回从formIndex到toIndex位置的子集合（左闭右开区间）

List实现类之一：ArrayList

问题：现在有4只小狗，如何存储它的信息、获取总数，并能逐条打印狗狗信息。
分析：通过List 接口的实现类ArrayList 实现该需求.

• 元素个数不确定
• 要求获得元素的实际个数
• 按照存储顺序获取并打印元素信息 ```java class Dog { private String name; //构造。。。set、get、。。。toString（） }

public class TestArrayList { public static void main(String[] args) {

//创建ArrayList对象 , 并存储狗狗
List dogs = new ArrayList();
dogs.add(new Dog("小狗一号"));
dogs.add(new Dog("小狗二号"));
dogs.add(new Dog("小狗三号"));
dogs.add(2,new Dog("小狗四号"));// 添加到指定位置
// .size() ： ArrayList大小
System.out.println("共计有" + dogs.size() + "条狗狗。");
System.out.println("分别是：");
// .get(i) ： 逐个获取个元素
for (int i = 0; i < dogs.size(); i++) {
  Dog dog = (Dog) dogs.get(i);
  System.out.println(dog.getName());
}

} }

问题联想：
-  删除第一个狗狗 ：remove（index） 
-  删除指定位置的狗狗 ：remove（object） 
-  判断集合中是否包含指定狗狗 ： contains（object） 
分析：使用List接口提供的remove()、contains()方法<br />【常用方法】<br />![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051541126.png#crop=0&crop=0&crop=1&crop=1&id=C9Ua5&originHeight=273&originWidth=516&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="5c1e650a"></a>
### 1、ArrayList概述
1.  ArrayList可以**动态**增长和缩减的索引序列，它是基于数组实现的List类。 
2.  该类封装了一个**动态再分配的Object[]数组**，每一个类对象都有一个capacity（容量）属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。 
3.  ArrayList的用法和Vector类似，但是Vector是一个较老的集合，具有很多缺点，不建议使用。 
另外，**ArrayList和Vector的区别**：
- ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性；
- Vector则是线程安全的。
**ArrayList和Collection的关系：**<br />![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051542118.png#crop=0&crop=0&crop=1&crop=1&id=V1IFk&originHeight=261&originWidth=346&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="9f859b25"></a>
### 2、ArrayList的数据结构
ArrayList的数据结构是：<br />![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051542390.png#crop=0&crop=0&crop=1&crop=1&id=sNJgi&originHeight=91&originWidth=403&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)<br />说明：底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。
<a name="aa1ee4db"></a>
### 3、ArrayList源码分析
<a name="23f115f1"></a>
#### 1）继承结构和层次关系
IDEA快捷键：Ctrl+H<br />![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051543525.png#crop=0&crop=0&crop=1&crop=1&id=Bc5Oh&originHeight=134&originWidth=326&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
```java
public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}

我们看一下ArrayList的继承结构：
ArrayList extends AbstractList
AbstractList extends AbstractCollection
所有类都继承Object ，所以ArrayList的继承结构就是上图这样。

【分析】

• 为什么要先继承AbstractList，而让AbstractList先实现List？而不是让ArrayList直接实现List？

  这里是有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList先实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁，就继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。
  一般看到一个类上面还有一个抽象类，应该就是这个作用。

• ArrayList实现了哪些接口？

1. List接口

在查看了ArrayList的父类 AbstractList也实现了List接口，那为什么子类ArrayList还是去实现一遍呢？ 开发这个collection 的作者Josh说：其实是一个mistake，因为写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。

2. RandomAccess接口

• 这个是一个标记性接口，通过查看api文档，它的作用就是用来快速随机存取，在实现了该接口的话，使用普通的for循环来遍历，性能更高，例如ArrayList。
• 而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。
• 所以这个标记性只是为了让我们知道用什么样的方式去获取数据性能更好。

3. Cloneable接口：实现了该接口，就可以使用Object.Clone()方法了。
4. Serializable接口：实现该序列化接口，表明该类可以被序列化。

什么是序列化？ 简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。

2）类中的属性

public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  // 版本号
  private static final long serialVersionUID = 8683452581122892189L;
  // 缺省容量
  private static final int DEFAULT_CAPACITY = 10;
  // 空对象数组
  private static final Object[] EMPTY_ELEMENTDATA = {};
  // 缺省空对象数组
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  // 元素数组
  transient Object[] elementData;
  // 实际元素大小，默认为0
  private int size;
  // 最大数组容量
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

3）构造方法

通过IDEA查看源码，看到ArrayList有三个构造方法：

• 无参构造方法

  /*
  Constructs an empty list with an initial capacity of ten.
  默认会给10的大小，所以一开始arrayList的容量是10.
  */
  //ArrayList中储存数据的其实就是一个数组，这个数组就是elementData.
  public ArrayList() {
  super(); //调用父类中的无参构造方法，父类中的是个空的构造方法
  this.elementData = EMPTY_ELEMENTDATA;
  //EMPTY_ELEMENTDATA：是个空的Object[]，将elementData初始化，elementData也是个Object[]类型。空的Object[]会给默认大小10。
  }

• 有参构造方法 1 ```java / Constructs an empty list with the specified initial capacity. 构造具有指定初始容量的空列表。 @param initialCapacity the initial capacity of the list 初始容量列表的初始容量 @throws IllegalArgumentException if the specified initial capacity is negative 如果指定的初始容量为负，则为IllegalArgumentException /

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { ////将自定义的容量大小当成初始化initialCapacity 的大小 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; //等同于无参构造方法 } else { ////判断如果自定义大小的容量小于0，则报下面这个非法数据异常 throw new IllegalArgumentException(“Illegal Capacity: “+ initialCapacity); } }

- 有参构造方法 2
```java
/*
Constructs a list containing the elements of the specified collection,
in the order they are returned by the collection's iterator.
按照集合迭代器返回元素的顺序构造包含指定集合的元素的列表。
@param c the collection whose elements are to be placed into this list
@throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray(); //转换为数组
  //每个集合的toarray()的实现方法不一样，需要判断一下。
  //如果不是Object[].class类型，需要使用ArrayList中的方法去改造一下。
    if ((size = elementData.length) != 0) {
      // c.toArray might (incorrectly) not return Object[] (see 6260652)
      if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
      // replace with empty array.
      this.elementData = EMPTY_ELEMENTDATA;
    }
}

【总结】
ArrayList的构造方法就做一件事情，即初始化一下储存数据的容器，本质上就是一个数组，在其中就叫elementData。

4）核心方法—add

• boolean add(E) ```java /**

• Appends the specified element to the end of this list.
• 添加一个特定的元素到list的末尾。
• @param e element to be appended to this list
• @return true (as specified by {@link Collection#add}) */

public boolean add(E e) { //确定内部容量是否够了，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1数组能否放得下，在方法中判断数组.length是否够用。 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; //在数据中正确的位置上放上元素e，并且size++ return true; }

【分析：`ensureCapacityInternal(xxx);` 确定内部容量的方法】
```java
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity)
{
  //判断初始化的elementData是不是空的数组，即没有长度
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    //如果是空的话，minCapacity=size+1；其实就是等于1，
    //空的数组没有长度存放不了，所以将minCapacity变成10，即默认大小，但在这，还没有真正的初始化elementData的大小。
      return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  //确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否够用
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  // overflow-conscious code
  //minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用，不够用那么就要增加elementData的length。这里有的同学就会模糊minCapacity到底是什么呢，这里给你们分析一下
  /*第一种情况：由于elementData初始化时是空的数组，那么第一次add的时候，
minCapacity=size+1；也就minCapacity=1，在上一个方法(确定内部容量
ensureCapacityInternal)就会判断出是空的数组，就会给将minCapacity=10，到这一步为止，还没有改变elementData的大小。
    第二种情况：elementData不是空的数组了，那么在add的时候,minCapacity=size+1；也就是minCapacity代表着elementData中增加之后的实际数据个数，拿着它判断elementData的length是否够用，如果length
不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。*/
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
//arrayList核心的方法，能扩展数组大小的真正秘密。
private void grow(int minCapacity) {
  // overflow-conscious code
  //将扩充前的elementData大小给oldCapacity
  int oldCapacity = elementData.length;
  //newCapacity就是1.5倍的oldCapacity
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  //适应于elementData是空数组时，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，在这就真正初始化elementData的大小了，即为10，前面的工作都是准备工作。
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  //如果newCapacity超过最大的容量限制，就调用hugeCapacity，即将能给的最大值给newCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  //新的容量大小已经确定好了，就copy数组，改变容量大小。
  elementData = Arrays.copyOf(elementData, newCapacity);
}
//用来赋最大值
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
//如果minCapacity都大于MAX_ARRAY_SIZE，那么将Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。
//因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。
//Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 
//也就是说最大也就能给到第一个数值。还是超过这个限制，就溢出。相当于arraylist给了两层防护。
    return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

• void add(int，E)

  public void add(int index, E element) {
  //检查index，即插入的位置是否合理。
  rangeCheckForAdd(index);
  ensureCapacityInternal(size + 1); // Increments modCount!!
  //用来在插入元素后，将index之后的元素都往后移一位，
  System.arraycopy(elementData, index, elementData, index + 1,
                   size - index);
  //在目标位置上存放元素
  elementData[index] = element;
  size++;
  }

【分析：rangeCheckForAdd(index)】

private void rangeCheckForAdd(int index) {
  //插入的位置肯定不能大于size和小于0
  if (index > size || index < 0)
    //如果是，就报这个越界异常
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

【System.arraycopy(...)：就是将elementData在插入位置后的所有元素，往后面移一位.】

【总结】
正常情况下会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。
当我们调用add方法时，实际上的函数调用如下：

说明：程序调用add，实际上还会进行一系列调用，可能会调用到grow，grow可能会调用hugeCapacity。

【举例】

List<Integer> lists = new ArrayList<Integer>;
lists.add(8);

说明：初始化lists大小为0，调用的ArrayList()型构造函数，那么在调用lists.add(8)方法时，会经过怎样的步骤呢？下图给出了该程序执行过程和最初与最后的elementData的大小。

说明：可以看到，在add方法之前开始elementData = {}；调用add方法时会继续调用，直至grow，最后elementData的大小变为10，之后再返回到add函数，把8放在elementData[0]中。

【举例说明二】

List<Integer> lists = new ArrayList<Integer>(6);
lists.add(8);

说明：可以知道，在调用add方法之前，elementData的大小已经为6，之后再进行传递，不会进行扩容处理。

5）核心方法—remove

fastRemove(int)方法是private的，是提供给remove(Object)这个方法用的。

• remove(int)：通过删除指定位置上的元素

  public E remove(int index) {
  rangeCheck(index);//检查index的合理性
  modCount++;//这个作用很多，比如用来检测快速失败的一种标志。
  E oldValue = elementData(index);//通过索引直接找到该元素
  int numMoved = size - index - 1;//计算要移动的位数。
  if (numMoved > 0)
    //这个方法也已经解释过了，就是用来移动元素的。
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  //将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
  elementData[--size] = null; // clear to let GC do its work
  //返回删除的元素。
  return oldValue;
  }

• remove(Object)：可以看出来，arrayList是可以存放null值的。

  //感觉这个不怎么要分析吧，都看得懂，就是通过元素来删除该元素，就依次遍历，如果有这个元素，就将该元素的索引传给fastRemobe(index)，使用这个方法来删除该元素，
  //fastRemove(index)方法的内部跟remove(index)的实现几乎一样，这里最主要是知道arrayList可以存储null值
  public boolean remove(Object o) {
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    for (int index = 0; index < size; index++)
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
  }

• clear()：将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉，所以叫clear

  public void clear() {
  modCount++;
  // clear to let GC do its work
  for (int i = 0; i < size; i++)
    elementData[i] = null;
  size = 0;
  }

• removeAll(collection c)

  public boolean removeAll(Collection<?> c) {
  return batchRemove(c, false);//批量删除
  }

• batchRemove(xx,xx)：用于两个方法，一个removeAll()：它只清楚指定集合中的元素，retainAll()用来测试两个集合是否有交集。 ```java //这个方法，用于两处地方，如果complement为false，则用于removeAll如果为true，则给retainAll()用，retainAll（）是用来检测两个集合是否有交集的。

private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; //将原集合，记名为A int r = 0, w = 0; //r用来控制循环，w是记录有多少个交集 boolean modified = false; try { for (; r < size; r++) //参数中的集合C一次检测集合A中的元素是否有， if (c.contains(elementData[r]) == complement) //有的话，就给集合A elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. //如果contains方法使用过程报异常 if (r != size) { //将剩下的元素都赋值给集合A， System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { //这里有两个用途，在removeAll()时，w一直为0，就直接跟clear一样，全是为null。 //retainAll()：没有一个交集返回true，有交集但不全交也返回true，而两个集合相等的时候，返回false，所以不能根据返回值来确认两个集合是否有交集，而是通过原集合的大小是否发生改变来判断，如果原集合中还有元素，则代表有交集，而元集合没有元素了，说明两个集合没有交集。

    // clear to let GC do its work
    for (int i = w; i < size; i++)
      elementData[i] = null;
  modCount += size - w;
  size = w;
  modified = true;
}

} return modified; }

**总结**：remove函数，用于移除指定下标的元素，此时会把指定下标到数组末尾的元素向前移动一个单位，并且会把数组最后一个元素设置为null，这样是为了方便之后将整个数组不被使用时，会被GC，可以作为小的技巧使用。
<a name="c30ba5d4"></a>
#### 6）其他方法
- **set()方法：设定指定下标索引的元素值**
```java
public E set(int index, E element) {
  // 检验索引是否合法
  rangeCheck(index);
  // 旧值
  E oldValue = elementData(index);
  // 赋新值
  elementData[index] = element;
  // 返回旧值
  return oldValue;
}

• indexOf()方法：从头开始查找与指定元素相等的元素。
  注意：可以查找null元素，意味着ArrayList中可以存放null元素。与此函数对应的lastIndexOf，表示从尾部开始查找。

  // 从首开始查找数组里面是否存在指定元素
  public int indexOf(Object o) {
  if (o == null) { // 查找的元素为空
   for (int i = 0; i < size; i++) // 遍历数组，找到第一个为空的元素，返回下标
     if (elementData[i]==null)
       return i;
  } else { // 查找的元素不为空
   for (int i = 0; i < size; i++) // 遍历数组，找到第一个和指定元素相等的元素，返回下标
     if (o.equals(elementData[i]))
       return i;
  }
  // 没有找到，返回空
  return -1;
  }

• get()方法

  public E get(int index) {
  // 检验索引是否合法
  rangeCheck(index);
  return elementData(index);
  }

说明：get函数会检查索引值是否合法（只检查是否大于size，而没有检查是否小于0），值得注意的是，在get函数中存在element函数，element函数用于返回具体的元素，具体函数如下：

E elementData(int index) {
  return (E) elementData[index];
}

说明：返回的值都经过了向下转型（Object -> E），这些是对我们应用程序屏蔽的小细节。

4、总结

• arrayList可以存放null。
• arrayList本质上就是一个elementData数组。
• arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。
• arrayList中removeAll(collection c)和clear()的区别：
  • removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。
• arrayList由于本质是数组，所以在数据的查询方面会很快，而在插入、删除方面，性能下降很多，要移动很多数据才能达到应有的效果
• arrayList实现了RandomAccess，所以在遍历的时候推荐使用for循环。

List实现类之二：LinkedList

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

1、引入

问题：在集合的任何位置（头部、中间、尾部）添加、获取、删除狗狗对象。
分析：插入、删除操作频繁时，可使用LinkedList来提高效率。

LinkedList提供对头部和尾部元素进行添加和删除操作的方法。

【LinkedList的特殊方法】

2、LinkedList源码分析

1）LinkedList概述

• LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，是基于双向链表实现的。
• LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，能对它进行队列操作。
• LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
• LinkedList 是非同步的。

2）LinkedList的数据结构

【基础知识补充】
单向链表：
element：用来存放元素
next：用来指向下一个节点元素
通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。

单向循环链表：
element、next 跟前面一样
在单向链表的最后一个节点的next会指向头节点，而不是指向null，这样存成一个环

双向链表：
element：存放元素
pre：用来指向前一个元素
next：指向后一个元素
双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null。

双向循环链表：
element、pre、next 跟前面的一样
第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。

【LinkedList的数据结构】

如上图所示，LinkedList底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着可从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。

3）LinkedList的特性

LinkedList的特性：

• 异步，即非线程安全

• 双向链表。由于实现了list和Deque接口，能够当作队列来使用。

   链表：查询效率不高，但是插入和删除这种操作性能好。

• 是顺序存取结构（注意和随机存取结构两个概念搞清楚）

4）继承结构和层次关系

【分析】
通过API我们会发现：
1）减少实现顺序存取（例如LinkedList）这种类的工作，通俗讲就是方便，抽象出类似LinkedList这种类的一些共同的方法
2）以后如果自己想实现顺序存取这种特性的类(链表形式)，就继承这个AbstractSequentialList抽象类，如果想像数组那样的随机存取的类，就去实现AbstracList抽象类。
3）这样的分层很符合抽象的概念，越在高处的类，就越抽象，往在底层的类，就越有自己独特的个性。
4）LinkedList的类继承结构很有意思，我们着重要看是Deque接口，Deque接口表示是一个双端队列，意味着LinkedList是双端队列的一种实现，所以，基于双端队列的操作在LinkedList中全部有效。

【接口实现分析】

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}

1）List接口：列表，add、set、等一些对列表进行操作的方法
2）Deque接口：有队列的各种特性，
3）Cloneable接口：能够复制，使用那个copy方法。
4）Serializable接口：能够序列化。
5）应该注意到没有RandomAccess：那么就推荐使用iterator，在其中有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。

5）类的属性

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  // 实际元素个数
  transient int size = 0;
  // 头结点
  transient Node<E> first;
  // 尾结点
  transient Node<E> last;
}

LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。
注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

6）构造方法

两个构造方法(两个构造方法都是规范规定需要写的）

【空参构造函数】

public LinkedList() {
}

【有参构造函数】

//将集合c中的各个元素构建成LinkedList链表。
public LinkedList(Collection<? extends E> c) {
  // 调用无参构造函数
  this();
  // 添加集合中所有的元素
  addAll(c);
}

说明：会调用无参构造函数，并且会把集合中所有的元素添加到LinkedList中。

7）内部类（Node）

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;
  }
}

说明：内部类Node就是实际的结点，用于存放实际元素的地方。

8）核心方法

• add()方法：用于向LinkedList中添加一个元素，并且添加到链表尾部。

  public boolean add(E e) {
  // 添加到末尾
  linkLast(e);
  return true;
  }

LinkLast(XXXXX)

/**
* Links e as last element.
*/
void linkLast(E e) {
  final Node<E> l = last; //临时节点l(L的小写)保存last，也就是l指向了最后一个节点
  final Node<E> newNode = new Node<>(l, e, null);//将e封装为节点，并且e.prev指向了最后一个节点
  last = newNode;//newNode成为了最后一个节点，所以last指向了它
  if (l == null) //判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它
        first = newNode;
  else //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点
        l.next = newNode;
  size++;//添加一个节点，size自增
  modCount++;
}

说明：对于添加一个元素至链表中会调用add方法 -> linkLast方法。

【举例一】

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);

首先调用无参构造函数，之后添加元素5，之后再添加元素6。具体的示意图如下：

上图的表明了在执行每一条语句后，链表对应的状态。

• addAll()方法

addAll有两个重载函数，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extendsE>)型。

public boolean addAll(Collection<? extends E> c) {
  return addAll(size, c);
}

addAll(size，c)：这个方法，能包含三种情况下的添加。

public boolean addAll(int index, Collection<? extends E> c) {
  //检查index这个是否为合理。
  checkPositionIndex(index);
  //将集合c转换为Object数组 a
  Object[] a = c.toArray();
  //数组a的长度numNew，也就是由多少个元素
  int numNew = a.length;
  if (numNew == 0)
    //集合c是个空的，直接返回false，什么也不做。
    return false;
  //集合c是非空的，定义两个节点(内部类)，每个节点都有三个属性，item、next、prev。注意：不要管这两个什么含义，就是用来做临时存储节点的。这个Node看下面一步的源码分析，Node就是linkedList的最核心的实现，可以直接先跳下一个去看Node的分析
  Node<E> pred, succ;
  //构造方法中传过来的就是index==size
  if (index == size) {
    //linkedList中三个属性：size、first、last。 size：链表中的元素个数。first：头节点 last：尾节点，就两种情况能进来这里
      //情况一、：构造方法创建的一个空的链表，那么size=0，last、和first都为null。linkedList中是空的。什么节点都没有。succ=null、pred=last=null
      //情况二、：链表中有节点，size就不是为0，first和last都分别指向第一个节点，和最后一个节点，在最后一个节点之后追加元素，就得记录一下最后一个节点是什么，所以把last保存到pred临时节点中。
      succ = null;
        pred = last;
  } else {
    //情况三、index！=size，说明不是前面两种情况，而是在链表中间插入元素，那么就得知道index上的节点是谁，保存到succ临时节点中，然后将succ的前一个节点保存到pred中，这样保存了这两个节点，就能够准确的插入节点了
   //举个简单的例子，有2个位置，1、2、如果想插数据到第二个位置，双向链表中，就需要知道第一个位置是谁，原位置也就是第二个位置上是谁，然后才能将自己插到第二个位置上。如果这里还不明白，先看一下文章开头对于各种链表的删除，add操作是怎么实现的。
      succ = node(index);
        pred = succ.prev;
  }
  //前面的准备工作做完了，将遍历数组a中的元素，封装为一个个节点。
  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    //pred就是之前所构建好的，可能为null、也可能不为null，为null的话就是属于情况一、不为null则可能是情况二、或者情况三
      Node<E> newNode = new Node<>(pred, e, null);
   //如果pred==null，说明是情况一，构造方法，是刚创建的一个空链表，此时的newNode就当作第一个节点，所以把newNode给first头节点
      if (pred == null)
        first = newNode;
    else
      //如果pred！=null，说明可能是情况2或者情况3，如果是情况2，pred就是last，那么在最后一个节点之后追加到newNode，如果是情况3，在中间插入，pred为原index节点之前的一个节点，将它的next指向插入的节点，也是对的
      pred.next = newNode;
    //然后将pred换成newNode，注意，这个不在else之中，请看清楚了。
    pred = newNode;
  }
  if (succ == null) {
    /*如果succ==null，说明是情况一或者情况二，
情况一、构造方法，也就是刚创建的一个空链表，pred已经是newNode了，
last=newNode，所以linkedList的first、last都指向第一个节点。
情况二、在最后节后之后追加节点，那么原先的last就应该指向现在的最后一个节点
了，就是newNode。*/
    last = pred;
  } else {
    //如果succ！=null，说明可能是情况三、在中间插入节点，举例说明这几个参数的意义，有1、2两个节点，现在想在第二个位置插入节点newNode，根据前面的代码，pred=newNode，succ= 2，并且1.next=newNode，已经构建好了，pred.next=succ，相当于在newNode.next = 2； succ.prev = pred，相当于 2.prev = newNode， 这样一来，这种指向关系就完成了。first和last不用变，因为头节点和尾节点没变
      pred.next = succ;
    //。。
    succ.prev = pred;
  }
  //增加了几个元素，就把 size = size +numNew 就可以了
  size += numNew;
  modCount++;
  return true;
}

说明：参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入。

在addAll函数中，addAll函数中还会调用到node函数，get函数也会调用到node函数，此函数是根据索引下标找到该结点并返回，具体代码如下：

Node<E> node(int index) {
  // 判断插入的位置在链表前半段或者是后半段
  if (index < (size >> 1)) { // 插入位置在前半段
    Node<E> x = first;
    for (int i = 0; i < index; i++) // 从头结点开始正向遍历
      x = x.next;
    return x; // 返回该结点
  } else { // 插入位置在后半段
    Node<E> x = last;
    for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历
      x = x.prev;
    return x; // 返回该结点
  }
}

说明：在根据索引查找结点时，会有一个小优化，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。

举例说明调用addAll函数后的链表状态：

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));

上述代码内部的链表结构如下：

addAll()中的一个问题：

在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？

从效果上两者是完全等价的，都可以达到遍历的效果。关于为什么要转化为数组的问题，我的思考如下：

1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。
2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合。说白了，就是有利于提高多线程访问该集合的效率，尽可能短时间的阻塞。

• remove(Object o) ```java /**

• Removes the first occurrence of the specified element from this list,
• if it is present. If this list does not contain the element, it is
• unchanged. More formally, removes the element with the lowest index
• {@code i} such that
• (o==null ? get(i)==null : o.equals(get(i)))
• (if such an element exists). Returns {@code true} if this list
• contained the specified element (or equivalently, if this list
• changed as a result of the call). *
• @param o element to be removed from this list, if present
• @return {@code true} if this list contained the specified element */ //首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值，那么我们会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做。 public boolean remove(Object o) { //这里可以看到，linkedList也能存储null if (o == null) { //循环遍历链表，直到找到null值，然后使用unlink移除该值。下面的这个else中也一样 for (Node x = first; x != null; x = x.next) {

  if (x.item == null) {
    unlink(x);
    return true;
  }

  } } else { for (Node x = first; x != null; x = x.next) {

  if (o.equals(x.item)) {
    unlink(x);
    return true;
  }

  } } return false; } ```

【unlink(xxxx)】

/**
* Unlinks non-null node x.
*/
//不能传一个null值过，注意，看之前要注意之前的next、prev这些都是谁。
E unlink(Node<E> x) {
  // assert x != null;
  //拿到节点x的三个属性
  final E element = x.item;
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;
  //这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。
  if (prev == null) {
    //说明移除的节点是头节点，则first头节点应该指向下一个节点
    first = next;
  } else {
    //不是头节点，prev.next=next：有1、2、3，将1.next指向3
    prev.next = next;
    //然后解除x节点的前指向。
    x.prev = null;
  }
  if (next == null) {
    //说明移除的节点是尾节点
    last = prev;
  } else {
    //不是尾节点，有1、2、3，将3.prev指向1. 然后将2.next=解除指向。
    next.prev = prev;
    x.next = null;
  }
  //x的前后指向都为null了，也把item为null，让gc回收它
  x.item = null;
  size--; //移除一个节点，size自减
  modCount++;
  return element; //由于一开始已经保存了x的值到element，所以返回。
}

• get(index)
  • get(index)查询元素的方法 ```java /**

• Returns the element at the specified position in this list. *
• @param index index of the element to return
• @return the element at the specified position in this list
• @throws IndexOutOfBoundsException {@inheritDoc} */ //这里没有什么，重点还是在node(index)中 public E get(int index) { checkElementIndex(index); return node(index).item; } ```

【node(index)】

/**
* Returns the (non-null) Node at the specified element index.
*/
//这里查询使用的是先从中间分一半查找
Node<E> node(int index) {
  // assert isElementIndex(index);
  //"<<":*2的几次方 “>>”:/2的几次方，例如：size<<1：size*2的1次方，
  //这个if中就是查询前半部分
  if (index < (size >> 1)) {//index<size/2
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else {//前半部分没找到，所以找后半部分
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

• indexOf(Object o) ```java //这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似，只是返回类型不一样。

public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }

<a name="f382a681"></a>
#### 9）LinkedList的迭代器
在LinkedList中除了有一个Node的内部类外，应该还能看到另外两个内部类，那就是ListItr，还有一个是DescendingIterator。
【ListItr内部类】
```java
private class ListItr implements ListIterator<E> {
}

看一下他的继承结构，发现只继承了一个ListIterator，到ListIterator中一看：

看到方法名之后，就发现不止有向后迭代的方法，还有向前迭代的方法，所以我们就知道了这个ListItr这个内部类干嘛用的了，就是能让linkedList不光能像后迭代，也能向前迭代。

看一下ListItr中的方法，可以发现，在迭代的过程中，还能移除、修改、添加值得操作。

【DescendingIterator内部类】

private class DescendingIterator implements Iterator<E> {
  //看一下这个类，还是调用的ListItr，作用是封装一下Itr中几个方法，让使用者以正常的思维去写代码，例如，在从后往前遍历的时候，也是跟从前往后遍历一样，使用next等操作，而不用使用特殊的previous。
  private final ListItr itr = new ListItr(size());
  public boolean hasNext() {
    return itr.hasPrevious();
  }
  public E next() {
    return itr.previous();
  }
  public void remove() {
    itr.remove();
  }
}

10）总结

• linkedList本质上是一个双向链表，通过一个Node内部类实现链表结构。
• 能存储null值
• 跟ArrayList相比较，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好
• 从源码中看，它不存在容量不足的情况
• linkedList不仅能向前迭代，还能向后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。
• linkedList不光能当链表，还能当队列使用，因为实现了Deque接口。

List实现类之三：Vector

注意在学习这一篇前，需要有多线程的知识：
1）锁机制：对象锁、方法锁、类锁

• 对象锁就是方法锁：就是在一个类中的方法上加上synchronized关键字，这就是给这个方法加锁了。
• 类锁：锁的是整个类，当有多个线程来声明这个类的对象的时候将会被阻塞，直到拥有这个类锁的对象被销毁或者主动释放了类锁。这时在被阻塞住的线程被挑选出一个占有该类锁，声明该类的对象。其他线程继续被阻塞住。
  • 例如：在类A上有关键字synchronized，那么就是给类A加了类锁，线程1第一个声明此类的实例，则线程1拿到了该类锁，线程2在想声明类A的对象，就会被阻塞。

2）在本文中，使用的是方法锁。
3）每个对象只有一把锁，有线程A，线程B，还有一个集合C类，线程A操作C拿到了集合中的锁(在集合C中有用synchronized关键字修饰的)，并且还没有执行完，那么线程A就不会释放锁，当轮到线程B去操作集合C中的方法时 ，发现锁被人拿走了，所以线程B只能等待那个拿到锁的线程使用完，然后才能拿到锁进行相应的操作。

1、Vector

• Vector是一个古老的实现类，JDK1.0就有了。大多数操作与ArrayList相同，区别在于Vector是线程安全的。
• 在各种List中，最好把ArrayList作为缺省选择。当插入、删除频繁是，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。
• 新增方法：
  • void addElement(Object obj)
  • void insertElementAt(Object obj,int index)
  • void setElementAt(Object obj,int index)
  • void removeElement(Object obj)
  • void removeAllElement()

1）Vector概述

通过API中可以知道：

1. Vector是一个可变化长度的数组
2. Vector增加长度通过的是capacity和capacityIncrement这两个变量，目前还不知道如何实现自动扩增的，等会源码分析
3. Vector也可以获得iterator和listIterator这两个迭代器，并且发生的是fail-fast，而不是fail-safe
4. Vector是一个线程安全的类，如果需要线程安全就使用Vector，如果不需要，就使用ArrayList
5. Vector和ArrayList很类似，就少许的不一样，从它继承的类和实现的接口来看，跟ArrayList一模一样。

注意：在开发中，建议不用vector，如果需要线程安全的集合类直接用java.util.concurrent包下的类。

2）Vector源码分析

【继承结构和层次关系】

public class Vector<E>
  extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}

我们发现Vector的继承关系和层次结构和ArrayList中的一模一样。

【构造方法】
一共有四个构造方法。最后两个构造方法是collection Framwork的规范要写的构造方法。

构造方法作用：

1. 初始化存储元素的容器，也就是数组，elementData，
2. 初始化capacityIncrement的大小，默认是0，这个的作用就是扩展数组的时候，增长的大小，为0则每次扩展2倍

【Vector()：空构造】

/**
* Constructs an empty vector so that its internal data array
* has size {@code 10} and its standard capacity increment is
* zero.
*/
//看注释，这个是一个空的Vector构造方法，所以让他使用内置的数组，这里还不知道什么是内置的数组，看它调用了自身另外一个带一个参数的构造器
public Vector() {
  this(10);
}

【Vector(int)】

/**
* Constructs an empty vector with the specified initial capacity and
* with its capacity increment equal to zero.
*
* @param initialCapacity the initial capacity of the vector
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
//注释说，给空的cector构造器用和带有一个特定初始化容量用的，并且又调用了另外一个带两个参数的构造器，并且给容量增长值(capacityIncrement=0)为0，查看vector中的变量可以发现capacityIncrement是一个成员变量
public Vector(int initialCapacity) {
  this(initialCapacity, 0);
}

【ector(int，int)】

/**
* Constructs an empty vector with the specified initial capacity and
* capacity increment.
*
* @param initialCapacity the initial capacity of the vector
* @param capacityIncrement the amount by which the capacity is
* increased when the vector overflows
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
//构建一个有特定的初始化容量和容量增长值的空的Vector，
public Vector(int initialCapacity, int capacityIncrement) {
  super();//调用父类的构造，是个空构造
  if (initialCapacity < 0)//小于0，会报非法参数异常：不合法的容量
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  this.elementData = new Object[initialCapacity];//elementData是一个成员变量数组，初始化它，并给它初始化长度。默认就是10，除非自己给值。
  this.capacityIncrement = capacityIncrement;//capacityIncrement的意思是如果要扩增数组，每次增长该值，如果该值为0，那数组就变为两倍的原长度，这个之后会分析到
}

【Vector(Collection<? extends E> c)】

/**
* Constructs a vector containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this
* vector
* @throws NullPointerException if the specified collection is null
* @since 1.2
*/
//将集合c变为Vector，返回Vector的迭代器。
public Vector(Collection<? extends E> c) {
  elementData = c.toArray();
  elementCount = elementData.length;
  // c.toArray might (incorrectly) not return Object[] (see 6260652)
  if (elementData.getClass() != Object[].class)
    elementData = Arrays.copyOf(elementData, elementCount,
                                Object[].class);
}

3）核心方法

• add()方法 ```java /**

• Appends the specified element to the end of this Vector. *
• @param e element to be appended to this Vector
• @return {@code true} (as specified by {@link Collection#add})
• @since 1.2 */

//就是在vector中的末尾追加元素。但是看方法，synchronized，明白了为什么vector是线程安全的，因为在方法前面加了synchronized关键字，给该方法加锁了，哪个线程先调用它，其它线程就得等着，如果不清楚的就去看看多线程的知识，到后面我也会一一总结的。

public synchronized boolean add(E e) { modCount++; //通过arrayList的源码分析经验，这个方法应该是在增加元素前，检查容量是否够用 ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }

【ensureCapacityHelper(int)】
```java
/**
* This implements the unsynchronized semantics of ensureCapacity.
* Synchronized methods in this class can internally call this
* method for ensuring capacity without incurring the cost of an
* extra synchronization.
*
* @see #ensureCapacity(int)
*/
//这里注释解释，这个方法是异步(也就是能被多个线程同时访问)的，原因是为了让同步方法都能调用到这个检测容量的方法，比如add的同时，另一个线程调用了add的重载方法，那么两个都需要同时查询容量够不够，所以这个就不需要用synchronized修饰了。因为不会发生线程不安全的问题
private void ensureCapacityHelper(int minCapacity) {
  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
    //容量不够，就扩增，核心方法
    grow(minCapacity);
}

【grow(int)】

//看一下这个方法，其实跟arrayList一样，唯一的不同就是在扩增数组的方式不一样，如果capacityIncrement不为0，那么增长的长度就是capacityIncrement，如果为0，那么扩增为2倍的原容量
private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                   capacityIncrement : oldCapacity);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  elementData = Arrays.copyOf(elementData, newCapacity);
}

就是在每个方法上比arrayList多了一个synchronized，其他都一样。

public synchronized E get(int index) {
  if (index >= elementCount)
    throw new ArrayIndexOutOfBoundsException(index);
  return elementData(index);
}

2、Stack

Vector的子类Stack，就是栈的意思。那么该类就是跟栈的用法一样了

class Stack<E> extends Vector<E> {}

通过查看他的方法和api文档，很容易知道他的特性；就几个操作，出栈，入栈等，构造方法也是空的，用的还是数组，父类中的构造，跟父类一样的扩增方式，并且它的方法也是同步的，所以也是线程安全。

3、总结Vector和Stack

Vector总结（通过源码分析）

1. Vector使线程安全的，因为它的方法都加了synchronized关键字
2. Vector的本质是一个数组，特点是能够自动扩增，扩增的方式跟capacityIncrement的值有关
3. 它也会fail-fast。

Stack的总结

1. 对栈的一些操作，先进后出
2. 底层也是用数组实现的，因为继承了Vector
3. 也是线程安全的

List接口总结

List接口方法

• List除了从Collection集合继承的方法外，List集合里添加了一些根据索引来操作集合元素的方法。
  • add(int index,Object ele):在index位置插入ele元素
  • addAll(int index,Collection eles):从index位置开始将eles中的所有元素添加进来
  • get(int index):获取指定index位置的元素
  • indexOf(Object obj):返回obj在集合中首次出现的位置，如果不存在返回-1
  • lastIndexOf(Object obj):返回obj在集合中最后一次次出现的位置，如果不存在返回-1
  • remove(int index):移除指定index位置的元素，并返回此元素
  • set(int index,Object ele):设置指定index位置的元素为ele
  • subList(int formIndex,int toIndex):返回从formIndex到toIndex位置的子集合（左闭右开区间）

总结：常用方法

• 增：add(Object obj);
• 删：remove(int index);/remove(Object obj);
• 改：set(int index,Object ele);
• 查：get(int index);
• 插：add(int index,Object ele);
• 长度：size();

• 遍历：

  • Iterator迭代器方式；
  • 增强for循环；
  • 普通的循环； ```java public void test(){ ArrayList list = new ArrayList(); list.add(123); list.add(456); list.add(“AA”);

  //方式1：Iterator迭代器方式； Iterator iterator = list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); }

  //方式2：增强for循环； for(Object obj : list){ System.out.println(obj); }

  //方式3：普通的循环； for(int i = 0;i < list.size();i++){ System.out.println(list.get(i)); }

}

<a name="49876ccc"></a>
### ArrayList、LinkedList、Vector区别
**面试题：ArrayList、LinkedList和Vector三者之间的异同？**
-  同：三个类都实现了List接口，存储数据的特点相同：存储有序的、可重复的数据。 
-  不同： 
   -  ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[]存储； 
   -  LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储； 
   -  Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[]存储； 
**ArrayList和LinkedList区别**
-  ArrayList底层是用数组实现的顺序表，是随机存取类型，可自动扩增，并且在初始化时，数组的长度是0，只有在增加元素时，长度才会增加。默认是10，不能无限扩增，有上限，在查询操作的时候性能更好。 
-  LinkedList底层是用链表来实现的，是一个双向链表，注意这里不是双向循环链表,顺序存取类型。在源码中，似乎没有元素个数的限制。应该能无限增加下去，直到内存满了在进行删除，增加操作时性能更好。 
-  两个都是线程不安全的，在iterator时，会发生fail-fast：快速失效。 
**ArrayList和Vector的区别**
-  ArrayList线程不安全，在用iterator，会发生fail-fast 
-  Vector线程安全，因为在方法前加了Synchronized关键字；也会发生fail-fast 
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204181512099.png#crop=0&crop=0&crop=1&crop=1&id=eQOQR&originHeight=790&originWidth=1472&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="6b4988c9"></a>
### 重写方法
**集合Collection中存储的如果是自定义类的对象，需要自定义类重写哪个方法？**
-  需要重写equals()方法 
   -  List：重写equals()方法 
   -  Set：（HashSet、LinkedHashSet为例）：重写equals()方法、hashCode()方法<br />            （TreeSet为例）：Comparable：compareTo(Object obj)<br />                                            Comparator：compare(Object o1,Object o2) 
**fail-fast（快速故障）和fail-safe（故障安全）区别和什么情况下会发生?**<br />简单的来说，在java.util下的集合都是发生fail-fast，而在java.util.concurrent下的发生的都是fail-safe。
- 1）fail-fast
快速失败，例如在ArrayList中使用迭代器遍历时，有另外的线程对ArrayList的存储数组进行了改变，比如add、delete等使之发生了结构上的改变，所以Iterator就会快速报一个`java.util.ConcurrentModificationException` 异常（并发修改异常），这就是快速失败。
- 2）fail-safe
安全失败，在`java.util.concurrent`下的类，都是线程安全的类，在迭代的过程中，如果有线程进行结构的改变，不会报异常，而是正常遍历，这就是安全失败。
**为什么在java.util.concurrent包下对集合有结构的改变，却不会报异常？**<br />    在concurrent下的集合类增加元素时使用Arrays.copyOf()来拷贝副本，在副本上增加元素，如果有其他线程在此改变了集合的结构，那也是在副本上的改变，而不是影响到原集合，迭代器还是照常遍历，遍历完之后，改变原引用指向副本。<br />    所以总的一句话就是，如果在此包下的类进行增加、删除，就会出现一个副本。所以能防止fail-fast，这种机制并不会出错，称这种现象为fail-safe。
**Vector也是线程安全的，为什么是fail-fast呢？**
- 并不是说线程安全的集合就不会报fail-fast，而是报fail-safe；
- 出现fail-safe是因为：他们在实现增删的底层机制不一样，就像上面说的，会有一个副本，而像ArrayList、LinekdList、Verctor等，他们底层就是对着真正的引用进行操作，所以才会发生异常。
**既然是线程安全的，为什么在迭代的时候，还会有别的线程来改变其集合的结构呢(也就是对其删除和增加等操作)？**
- 首先，迭代的时候，根本就没用到集合中的删除、增加，查询的操作，就拿Vector来说，都没有用那些加锁的方法，也就是方法锁放在那没人拿，在迭代的过程中，有人拿了那把锁也没有办法，因为那把锁就放在那边。
**【举例说明fail-fast和fail-safe的区别】**
- fail-fast
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051725809.png#crop=0&crop=0&crop=1&crop=1&id=wzjBV&originHeight=398&originWidth=653&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
- fail-safe
通过CopyOnWriteArrayList这个类来做实验，不用管这个类的作用，但是他确实没有报异常，并且还通过第二次打印，来验证了上面我们说创建了副本的事情。
原理是在添加操作时会创建副本，在副本上进行添加操作，等迭代器遍历结束后，会将原引用改为副本引用，所以我们在创建了一个list的迭代器，结果打印的就是123444了，证明了确实改变成为了副本引用，后面为什么是三个4，原因是我们循环了3次，不久添加了3个4吗。<br />![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051727906.png#crop=0&crop=0&crop=1&crop=1&id=CB8I6&originHeight=427&originWidth=509&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204051727992.png#crop=0&crop=0&crop=1&crop=1&id=bECwD&originHeight=230&originWidth=592&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
**为什么现在都不提倡使用vector了？**
-  1）vector实现线程安全的方法是在每个操作方法上加锁，这些锁并不是必须要的，在实际开发中，一般都是通过锁一系列的操作来实现线程安全，也就是说将需要同步的资源放一起加锁来保证线程安全。 
-  2）如果多个Thread并发执行一个已经加锁的方法，但是在该方法中，又有vector的存在，vector本身实现中已经加锁了，那么相当于锁上又加锁，会造成额外的开销。 
-  3）就如上面第三个问题所说的，vector还有fail-fast的问题，也就是说它也无法保证遍历安全，在遍历时又得额外加锁，又是额外的开销，还不如直接用arrayList，然后再加锁呢。 
**总结**：Vector在你不需要进行线程安全的时候，也会给你加锁，也就导致了额外开销，所以在jdk1.5之后就被弃用了，现在如果要用到线程安全的集合，都是从java.util.concurrent包下去拿相应的类。
<a name="5f3d8bd0"></a>
## Set接口
Set接口：存储无序、不可重复的数据
- HashSet:**采用哈希算法实现的Set** 
   - HashSet的底层是用HashMap实现的，因此查询效率较高，由于采用hashCode算法直接确定元素的内存地址，增删效率也挺高的。
   - 作为Set的主要实现类；线程不安全的，可以存储null值
- LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历
- TreeSet：**底层使用红黑树存储数据**；可以按照添加对象的指定属性，进行排序。
<a name="0dab6030"></a>
### 1、Set接口概述
-  Set：存储无序的、不可重复的数据 
   - 以HashSet为例说明： 
      - **无序性**：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值
      - **不可重复性**：保证添加的元素按照equals()判断时，不能返回true。即，相同的元素只能添加一个
-  **Set接口是Collection的子接口，set接口中没有提供额外的方法，使用的都是Collection中声明的方法。** 
-  **要求：** 
   - **向Set（主要指HashSet、LinkedHashSet）中添加的数据，其所在的类一定要重写hashCode()和equals()方法。**
   - **重写的hashCode()和equals()方法尽可能保持一致性。**
-  Set集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set集合中，则添加操作失败； 
-  Set判断两个对象是否相同不是使用==运算符，而是根据equals()方法判断。 
**添加元素的过程：以HashSet为例**<br />    我们向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与已经存在指定索引位置上的数据以链表的方式存储。
- JDK7：元素a放到数组中，指向原来的元素。
- JDK8：原来的元素放在数组中，指向元素a。
- 总结：（元素a）七上八下
<a name="21cfe445"></a>
### 2、Set实现类之一：HashSet
-  HashSet是Set接口的典型实现，大多数时候使用Set集合时都使用这个实现类。 
-  HashSet按Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。 
-  HashSet具有以下特点： 
   - 不能保证元素的排列顺序
   - HashSet不是线程安全的
   - 集合元素可以是null
-  **HashSet集合判断两个元素相等的标准**：两个对象通过hashCode()方法比较相等，并且两个对象的equals()方法返回值也相等。 
-  对于存放在Set容器中的对象，**对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即“相等的对象必须具有相等的散列码”。** 
-  **HashSet底层：数组+链表** 
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204152344645.png#crop=0&crop=0&crop=1&crop=1&id=g0Mxs&originHeight=562&originWidth=1010&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
**重写hashCode()方法的基本原则：**
- 在程序运行时，同一个对象多次调用hashCode()方法应该返回相同的值。
- 当两个对象的equals()方法比较返回true时，这两个对象的hashCode()方法的返回值也应相等。
- 对象中用作equals()方法比较的Field，都应该用来计算hashCode值。
**Eclipse/IDEA工具里hashCode()重写：**<br />以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals()方法和hashCode()方法。
问题：为什么用Eclipse/IDEA重写hashCode()方法，有31这个数字？
- 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）
- 并且31只占用5bits，相乘造成数据溢出的概率较小。
- 31可以由 i*31== (i << 5)-1来表示，现在很多虚拟机里面都有做相关优化。（提高算法效率）
- 31是一个素数，素数作用就是如果用一个数来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除。（减少冲突）
<a name="d5f74386"></a>
### 3、Set实现类之二：LinkedHashSet
- **LinkedHashSet是HashSet的子类**，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。
- LinkedHashSet**根据元素的hashCode值来决定元素的存储位置**，但它**同时使用双向链表维护元素的次序**，这使得元素看起来是以插入顺序保存的。
- **LinkedHashSet插入性能略低于hashSet，但对于频繁的遍历操作，LinkedHashSet效率高于hashSet。**
- LinkedHashSet不允许集合元素重复。
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204160010076.png#crop=0&crop=0&crop=1&crop=1&id=fQELx&originHeight=604&originWidth=1036&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="6681c2e5"></a>
### 4、Set实现类之三：TreeSet
- TreeSet是SortSet接口的实现类，TreeSet可以确保集合元素处于排序状态。
- **TreeSet底层使用红黑树结构存储数据。**
- 向TreeSet中添加的数据，要求是相同类的对象，不能添加不同类的对象。
- 新增的方法如下： 
   - `Comparator comparator()`
   - `Object first()`
   - `Object last()`
   - `Object lower(Object e)`
   - `Object higher(Object e)`
   - `SortedSet subSet(formElement,toElement)`
   - `SortedSet headSet(toElement)`
   - `SortedSet tailSet(formElement)`
- TreeSet两种排序方法：自然排序（实现Comparable接口）和定制排序（Comparator）。默认情况下，TreeSet采用自然排序。 
   - 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()。
   - 定制排序中，比较两个对象是否相同的标准为：compare()返回0，不再是equals()。
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204160030202.png#crop=0&crop=0&crop=1&crop=1&id=cZoMw&originHeight=506&originWidth=1096&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)<br />[红黑树详解](https://blog.csdn.net/u014454538/article/details/120120216)
<a name="a5cfb5e7"></a>
## Set接口总结
1、存储数据的特点：无序的、不可重复的元素
- 具体的：以HashSet为例说明：
- **无序性**：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值
- **不可重复性**：保证添加的元素按照equals()判断时，不能返回true。即，相同的元素只能添加一个
2、元素添加过程（以HashSet为例）<br />**添加元素的过程：以HashSet为例**<br />    我们向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与已经存在指定索引位置上的数据以链表的方式存储。
- JDK7：元素a放到数组中，指向原来的元素。
- JDK8：原来的元素放在数组中，指向元素a。
- 总结：（元素a）七上八下
HashSet底层：数组+链表结构 （前提：JDK7）
3、常用方法<br />**Set接口是Collection的子接口，set接口中没有提供额外的方法，使用的都是Collection中声明的方法。**
4、常用实现类<br />Set接口：存储无序、不可重复的数据
- HashSet:**采用哈希算法实现的Set** 
   - HashSet的底层是用HashMap实现的，因此查询效率较高，由于采用hashCode算法直接确定元素的内存地址，增删效率也挺高的。
   - 作为Set的主要实现类；线程不安全的，可以存储null值
- LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历 
   - 在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据
   - 对于频繁的遍历操作，LinkedHashSet效率高于HashSet。
- TreeSet：**底层使用红黑树存储数据**；可以按照添加对象的指定属性，进行排序。
5、存储对象所在类的要求：
-  HashSet/LinkedHashSet： 
   -  要求：向Set（主要指HashSet、LinkedHashSet）中添加的数据，其所在的类一定要重写hashCode()和equals()方法。 
   -  要求：重写的hashCode()和equals()方法尽可能保持一致性。 
-  TreeSet： 
   - 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()。
   - 定制排序中，比较两个对象是否相同的标准为：compare()返回0，不再是equals()。
6、TreeSet的使用<br />6.1 使用说明
-  向TreeSet中添加的数据，要求是相同类的对象，不能添加不同类的对象。 
-  TreeSet两种排序方法：自然排序（实现Comparable接口）和定制排序（Comparator）。默认情况下，TreeSet采用自然排序。 
6.2 常用的排序方式
- 自然排序（实现Comparable接口）
- 定制排序（Comparator）
<a name="ad43d5da"></a>
## Map接口
![](https://gitee.com/wang_jin0751/image-host/raw/master/202204171857267.png#crop=0&crop=0&crop=1&crop=1&id=ya3NM&originHeight=530&originWidth=1072&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
**1、Map实现类的结构**
- Map：双列数据，存储 key-value 对的数据 
   - HashMap：**作为Map的主要实现类**；线程不安全的，效率高；可以存储null的key和value 
      - LinkedHashMap ：保证在遍历Map元素时，可以按照添加的顺序实现遍历。 
         - 原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
         - 对于频繁的遍历操作，此类的指向效率要高于HashMap。
   - TreeMap：保证按照添加的key-value对进行遍历，实现排序遍历。此时考虑key的自然排序或定制排序。 
      - 底层使用红黑树数据结构进行存储。
   - Hashtable：作为古老的Map实现类；线程安全的，效率低；不能存储null的key和value 
      - Properties：常用来处理配置文件。key和value都是String类型。
HashMap底层结构：
- JDK7及之前：数组+链表
- JDK8：数组+链表+红黑树
**面试题：**
-  HashMap的底层实现原理。 
-  HashMap和Hashtable的异同。 
-  CurrentHashMap和Hashtable的异同。 
**2、Map结构的理解**![](https://gitee.com/wang_jin0751/image-host/raw/master/202204172015386.png#crop=0&crop=0&crop=1&crop=1&id=KxcFp&originHeight=554&originWidth=916&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
- Map中的Key：无序的、不可重复的，使用Set存储所有的key。    --->  key所在的类要重写equals()方法和hashCode()方法  （以HashMap为例 ）
- Map中的value：无序的、可重复的，使用Collection存储所有的value。--->  value所在的类要重写equals()方法  （以HashMap为例 ）
- 一个键值对：key-value构成了一个Entry对象
- Map中的Entry：无序的、不可重复的，使用Set存储所有的Entry。
<a name="6b2a4145"></a>
## Map实现类之一：HashMap
<a name="8e40ce72"></a>
### 1、HashMap引入
问题：建立国家英文简称和中文全名间的键值映射，并通过key对value进行操作，如何实现数据的存储和操作呢？<br />分析： Map接口专门处理键值映射数据的存储，可以根据键实现对值的操作。<br />最常用的实现类是HashMap。
<a name="1cbf1536"></a>
### 2、HashMap的数据结构
<a name="d370c484"></a>
#### 1）HashMap概述
HashMap是基于哈希表的Map接口实现的，它存储的是内容是键值对<key,value>映射。此类不保证映射的顺序，假定哈希函数将元素适当的分布在各桶之间，可为基本操作(get和put)提供稳定的性能。
在API中给出了相应的定义：
```java
//1、哈希表基于map接口的实现，这个实现提供了map所有的操作，并且提供了key和value，可以为null，(HashMap和HashTable大致上是一样的，除了hashmap是异步的，和允许key和value为null)，
//这个类不确定map中元素的位置，特别要提的是，这个类也不确定元素的位置随着时间会不会保持不变。
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key.
(The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map;
in particular, it does not guarantee that the order will remain constant over time.
//假设哈希函数将元素合适的分到了每个桶(其实就是指的数组中位置上的链表)中，则这个实现为基本的操作(get、put)提供了稳定的性能，迭代这个集合视图需要的时间跟hashMap实例(key-value映射的数量)的容量(在桶中)成正比。
//因此，如果迭代的性能很重要的话，就不要将初始容量设置的太高或者loadfactor设置的太低，【这里的桶，相当于在数组中每个位置上放一个桶装元素】
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
Iteration over collection views requires time proportional to the
"capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
//HashMap的实例有两个参数影响性能，初始化容量(initialCapacity)和loadFactor加载因子，在哈希表中这个容量是桶的数量【也就是数组的长度】，一个初始化容量仅仅是在哈希表被创建时容量，在容量自动增长之前加载因子是衡量哈希表被允许达到的多少的。
//当entry的数量在哈希表中超过了加载因子乘以当前的容量，那么哈希表被修改(内部的数据结构会被重新建立)所以哈希表有大约两倍的桶的数量.
An instance of HashMap has two parameters that affect its performance:
initial capacity and load factor. The capacity is the number of buckets in the hash table,
and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before
its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity,the hash table
is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
//通常来讲，默认的加载因子(0.75)能够在时间和空间上提供一个好的平衡，更高的值会减少空间上的开支但是会增加查询花费的时间（体现在HashMap类中get、put方法上），当设置初始化容量时，应该考虑到map中会存放entry的数量和加载因子，以便最少次数的进行rehash操作，如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup
cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken
into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of
entries divided by the load factor, no rehash operations will ever occur.
//如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting
it perform automatic rehashing as needed to grow the table

2）HashMap在JDK1.8以前数据结构和存储原理

【链表散列】
通过数组和链表结合在一起使用，就叫做链表散列。这其实就是hashmap存储的原理图。

【HashMap的数据结构和存储原理】
HashMap的数据结构就是用的链表散列。

HashMap底层的实现原理：（以JDK7为例说明）
分成两个部分：
第一步：HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key; //就是我们说的map的key
  V value; //value值，这两个都不陌生
  Entry<K,V> next;//指向下一个entry对象
  int hash;//通过key算过来的你hashcode值。
}

Entry的物理模型图：

第二步：构造好了entry对象，然后将该对象放入数组中。大概的一个存放过程是：通过entry对象中的hash值来确定将该对象存放在数组中的哪个位置上，如果在这个位置上还有其他元素，则通过链表来存储这个元素。

【Hash存放元素的过程】
通过key、value封装成一个entry对象，然后通过key的值来计算该entry的hash值，通过entry的hash值和数组的长度length来计算出entry放在数组中的哪个位置上面，每次存放都是将entry放在第一个位置。在这个过程中，就是通过hash值来确定将该对象存放在数组中的哪个位置上。

HashMap底层的实现原理：（以JDK7为例说明）
HashMap map = new HashMap();

• 在实例化以后，底层创建了长度是16的一位数组Entry[] table

  …可能已经执行过多次put…
  map.put(key1,value1);

• 首先，调用key1所在类的hashCode()方法计算key1的哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。

  • 如果此位置上的数据为空，此时的key1-value1添加成功。 —— 情况1
  • 如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据的哈希值：
    • 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。 —— 情况2
    • 如果key1的哈希值与已经存在的某一个数据（key2-value2）的哈希值相同，继续比较：调用key1所在类的equals(key2)
      • 如果equals()返回false：此时key1-value1添加成功。 —— 情况3
      • 如果equals()返回true：此时value1替换value2。

补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的形式存储。

在不断的添加过程中，会涉及到扩容问题，当超出临界值且要存放的位置非空时，进行扩容。默认的扩容方式：扩容为原来的2倍，并将原有的数据复制过来。

3）JDK1.8后HashMap的数据结构

上图很形象的展示了HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。

JDK8相较于JDK7在底层实现方面的不同：

• new HashMap();:底层没有创建一个长度为16的数组
• JDK8底层的数组是：Node[]类型数组，而非Entry[]类型数组
• 首次调用put()方法时，底层创建一个长度为16的数组
• JDK7底层结构只有 数组+链表，JDK8底层结构为：数组+链表+红黑树
  • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64 ，此时此索引位置上的索引数据改为使用红黑树存储。

HashMap源码中的重要常量

DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16
MAXIMUM_CAPACITY：HashMap的最大支持容量，2^30
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，= 0.75
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化成红黑树。 = 8
UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化成链表。
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：扩容的临界值，= 容量 * 填充因子，16*0.75=12
loadFactor：填充因子

4）HashMap的属性

HashMap的实例有两个参数影响其性能。

• 初始容量：哈希表中桶的数量
• 加载因子：哈希表在其容量自动增加之前可以达到多满，的一种尺度

当哈希表中条目数超出了当前容量加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。
Java中默认初始容量为16，加载因子为0.75。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

【loadFactor加载因子】
定义：loadFactor译为佳载因子。加载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。

loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，那么数组中存放的数据也就越稀，也就是可能数组中每个位置上就放一个元素。

把loadFactor变为1最好吗？存的数据很多，但是这样会有一个问题，就是在通过key拿到value时，是先通过key的hashcode值，找到对应数组中的位置，如果该位置中有很多元素，则需要通过equals()来依次比较链表中的元素，拿到value值，这样花费的性能就很高，如果能让数组上的每个位置尽量只有一个元素最好，就能直接得到value值。

如果把loadFactor变得很小，在数组中的位置就会太稀，即分散的太开，浪费很多空间，所以在hashMap中loadFactor的初始值就是0.75，一般情况下不需要更改它。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

【桶】
根据前面画的HashMap存储的数据结构图，数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素(entry)，这就是桶的意思。也就相当于把元素都放在桶中。

【capacity】
capacity译为容量，代表数组的容量，即数组的长度，同时也是HashMap中桶的个数。默认值是16。
一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

【size的含义】
size就是在该HashMap的实例中实际存储的元素的个数

【threshold的作用】

int threshold;

threshold = capacity * loadFactor，当 Size>=threshold 时，就要考虑对数组的扩增了，threshold是衡量数组是否需要扩增的一个标准。
注意这里说的是考虑，实际上要扩增数组，除了这个size>=threshold条件外，还需要另外一个条件。

什么时候会扩增数组的大小？
在put一个元素时先size>=threshold并且还要在对应数组位置上有元素，这才能扩增数组。

我们通过一张HashMap的数据结构图来分析：

3、HashMap源码分析

1）HashMap的层次关系与继承结构

【HashMap继承结构】

上面就继承了一个abstractMap，用来减轻实现Map接口的编写负担。

【实现接口】

public class HashMap<K,V> extends AbstractMap<K,V>
  implements Map<K,V>, Cloneable, Serializable {
}

Map：在AbstractMap抽象类中已经实现过的接口，这里又实现，实际上是多余的。但每个集合都有这样的错误，也没过大影响

• Cloneable：能够使用Clone()方法，在HashMap中，实现的是浅拷贝，即对拷贝对象的改变会影响被拷贝的对象。
• Serializable：能够使之序列化，即可以将HashMap对象保存至本地，之后可以恢复状态。

2）HashMap的类属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,
Cloneable, Serializable {
  // 序列号
  private static final long serialVersionUID = 362498820763181265L;
  // 默认的初始容量是16
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  // 最大容量
  static final int MAXIMUM_CAPACITY = 1 << 30;
  // 默认的填充因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  // 当桶(bucket)上的结点数大于这个值时会转成红黑树
  static final int TREEIFY_THRESHOLD = 8;
  // 当桶(bucket)上的结点数小于这个值时树转链表
  static final int UNTREEIFY_THRESHOLD = 6;
  // 桶中结构转化为红黑树对应的table的最小大小
  static final int MIN_TREEIFY_CAPACITY = 64;
  // 存储元素的数组，总是2的幂次倍
  transient Node<k,v>[] table;
  // 存放具体元素的集
  transient Set<map.entry<k,v>> entrySet;
  // 存放元素的个数，注意这个不等于数组的长度。
  transient int size;
  // 每次扩容和更改map结构的计数器
  transient int modCount;
  // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
  int threshold;
  // 填充因子
  final float loadFactor;
}

3）HashMap的构造方法

有四个构造方法，构造方法的作用就是记录一下16这个数给threshold（这个数值最终会当作第一次数组的长度。）和初始化加载因子。
注意，hashMap中table数组一开始就已经是个没有长度的数组了。

构造方法中，并没有初始化数组的大小，数组在一开始就已经被创建了，构造方法只做两件事情，一个是初始化加载因子，另一个是用threshold记录下数组初始化的大小。

【HashMap()】

//看上面的注释就已经知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75
//初始化容量：也就是初始化数组的大小
//加载因子：数组上的存放数据疏密程度。
public HashMap() {
  this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

【HashMap(int)】

public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

【HashMap(int,float)】

public HashMap(int initialCapacity, float loadFactor) {
  // 初始容量不能小于0，否则报错
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  // 初始容量不能大于最大值，否则为最大值
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  // 填充因子不能小于或等于0，不能为非数字
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  // 初始化填充因子
  this.loadFactor = loadFactor;
  // 初始化threshold大小
  this.threshold = tableSizeFor(initialCapacity);
}

【HashMap(Map<? extends K, ? extends V> m)】

public HashMap(Map<? extends K, ? extends V> m) {
  // 初始化填充因子
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  // 将m中的所有元素添加至HashMap中
  putMapEntries(m, false);
}

【putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中】

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  int s = m.size();
  if (s > 0) {
    // 判断table是否已经初始化
    if (table == null) { // pre-size
      // 未初始化，s为m的实际元素个数
      float ft = ((float)s / loadFactor) + 1.0F;
      int t = ((ft < (float)MAXIMUM_CAPACITY) ?
               (int)ft : MAXIMUM_CAPACITY);
      // 计算得到的t大于阈值，则初始化阈值
      if (t > threshold)
        threshold = tableSizeFor(t);
    }
    // 已初始化，并且m元素个数大于阈值，进行扩容处理
    else if (s > threshold)
      resize();
    // 将m中的所有元素添加至HashMap中
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
      K key = e.getKey();
      V value = e.getValue();
      putVal(hash(key), key, value, false, evict);
    }
  }
}

4）常用方法

Map接口常用方法：

• 添加、删除、修改操作
  • put(key,value)：将指定key-value添加到（或修改）当前Map对象中
  • putAll(Map m)：将m中的所有key-value对存放到当前map中
  • remove(key)：移除指定key的key-value对，并返回value
  • clear()：清空当前map中的所有数据
• 元素的查询操作
  • get(key)：获取指定key对应的value
  • containsKey(key)：是否包含指定的key
  • containsValue(value)：是否包含指定的value
  • size()：返回map中的key-value对的个数
  • isEmpty()：判断当前map是否为空
  • equals(obj)：判断当前map和参数对象obj是否相等

• 元视图 操作的方法

  • keySet()：返回所有key构成的Set集合
  • values()：返回所有value构成的Collection集合
  • entrySet()：返回所有key-value对构成的Set集合

• **put(K key,V value)**

  public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
  }

• **putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)**

  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // table未初始化或者长度为0，进行扩容
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点
  是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
  // 桶中已经存在元素
  else {
    Node<K,V> e; K k;
    // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      // 将第一个元素赋值给e，用e来记录
      e = p;
    // hash值不相等，即key不相等；为红黑树结点
    else if (p instanceof TreeNode)
      // 放入树中
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 为链表结点
    else {
      // 在链表最末插入结点
      for (int binCount = 0; ; ++binCount) {
        // 到达链表的尾部
        if ((e = p.next) == null) {
          // 在尾部插入新结点
          p.next = newNode(hash, key, value, null);
          // 结点数量达到阈值，转化为红黑树
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          // 跳出循环
          break;
        }
        // 判断链表中结点的key值与插入的元素的key值是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          // 相等，跳出循环
          break;
        // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
        p = e;
      }
    }
    // 表示在桶中找到key值、hash值与插入元素相等的结点
    if (e != null) {
      // 记录e的value
      V oldValue = e.value;
      // onlyIfAbsent为false或者旧值为null
      if (!onlyIfAbsent || oldValue == null)
        //用新值替换旧值
        e.value = value;
      // 访问后回调
      afterNodeAccess(e);
      // 返回旧值
      return oldValue;
    }
  }
  // 结构性修改
  ++modCount;
  // 实际大小大于阈值则扩容
  if (++size > threshold)
    resize();
  // 插入后回调
  afterNodeInsertion(evict);
  return null;
  }

  HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。

• **get(Object key)**

  public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
  }

• **getNode(int hash,Pbject key)**

  final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    // 桶中第一项(数组元素)相等
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    // 桶中不止一个结点
    if ((e = first.next) != null) {
      // 为红黑树结点
      if (first instanceof TreeNode)
        // 在红黑树中查找
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      // 否则，在链表中查找
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
  }

  HashMap并没有直接提供getNode接口给用户调用，而是提供的get函数，而get函数就是通过getNode来取得元素的。

• **resize()方法**

  final Node<K,V>[] resize() {
  // 当前table保存
  Node<K,V>[] oldTab = table;
  // 保存table大小
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  // 保存当前阈值
  int oldThr = threshold;
  int newCap, newThr = 0;
  // 之前table大小大于0
  if (oldCap > 0) {
    // 之前table大于最大容量
    if (oldCap >= MAXIMUM_CAPACITY) {
      // 阈值为最大整形
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // 容量翻倍，使用左移，效率更高
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      // 阈值翻倍
      newThr = oldThr << 1; // double threshold
  }
  // 之前阈值大于0
  else if (oldThr > 0)
    newCap = oldThr;
  // oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个
  元素会调用resize函数，会进入这一步）
    else {
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
  // 新阈值为0
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY
              ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  // 初始化table
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  // 之前的table已经初始化过
  if (oldTab != null) {
    // 复制元素，重新进行hash
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两
          个不同的链表，完成rehash
            do {
              next = e.next;
              if ((e.hash & oldCap) == 0) {
                if (loTail == null)
                  loHead = e;
                else
                  loTail.next = e;
                loTail = e;
              }
              else {
                if (hiTail == null)
                  hiHead = e;
                else
                  hiTail.next = e;
                hiTail = e;
              }
            } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
  }

  进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。