集合框架：

用于存储数据的容器。

Java 集合框架概述

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

数组在内存存储方面的特点：

数组初始化以后，长度就确定了。

数组声明的类型，就决定了进行元素初始化时的类型

数组在存储数据方面的弊端：

数组初始化以后，长度就不可变了，不便于扩展

数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数

数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

Java 集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的关联数组。

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

Collection接口：单列数据，定义了存取一组对象的方法的集合

List：元素有序、可重复的集合

Set：元素无序、不可重复的集合

Map接口：双列数据，保存具有映射关系“key-value对”的集合

Collection接口继承树

Map接口继承树

Collection 接口

Collection 接口内容

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

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

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

Collection 接口方法

1，添加：
add(object)：添加一个元素
addAll(Collection) ：添加一个集合中的所有元素。

2，获取：
int size()：集合中有几个元素。

3，清空集合
clear()：将集合中的元素全删除。

4，是否为空
boolean isEmpty()：集合中是否有元素。

5，判断是否包含指定元素：
boolean contains(obj) ：是通过元素的 equals，
     equals 方法来判断是否方法来判断是否是同一个对象 。
boolean containsAll(Collection) ：集合中是否包含指定的多个元素，
    也是调用元素的 equals方法来比较的。拿两个集合的元素挨比较 。。

6，删除：
remove(obj) ：删除集合中指定的对象。注意：删除成功，集合的长度会改变。
removeAll(collection) ：删除部分元素。部分元素和传入Collection一致。

7，取交集：
boolean  retainAll(Collection) ：对当前集合中保留和指定集合中的相同的元素。
如果两个集合元素相同，返回flase；如果retainAll修改了当前集合，返回true。

8，集合是否相等
boolean equals(Object obj)

9，获取集合对象的哈希值hashCode()
10，获取集合中所有元素：
  Iterator  iterator()：迭代器

11，将集合变成数组：
toArray();

Iterator迭代器接口：

迭代器：

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

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

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

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

Iterator接口的方法

boolean	hasNext()  如果仍有元素可以迭代，则返回 true。
E	next()   返回迭代的下一个元素。
void	remove()  从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。

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

@Test
public void IteratorTest01() {
    Collection coll = new ArrayList();
    coll.add("abc0");
    coll.add("abc1");
    coll.add("abc2");
    coll.add("Tom");
    //--------------方式1----------------------
    Iterator iter = coll.iterator();
    while(iter.hasNext()){
       Object obj= iter.next();
       if(obj.equals("Tom")){
           System.err.println(obj);
           iter.remove();
       }
    }
    //---------------方式2用此种----------------------
    for(Iterator it = coll.iterator();it.hasNext(); ){
       System.out.println(it.next());
    }
}

数组既可以存储基本数据类型，也可以存储引用类型。它存储引用类型的时候的数组就叫对象数组。

注意：

Iterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，不是集合对象的remove方法。

如果还未调用next()或在上一次调用next方法之后已经调用了remove方法，再调用remove都会报IllegalStateException。

List集合遍历

@Test
public void IteratorTest02() {
    ArrayList<String> coll = new ArrayList();
    coll.add("abc0");
    coll.add("abc1");
    coll.add("abc2");
    coll.add("Tom");

    //--------------方式1 迭代器遍历----------------------
    Iterator iter = coll.iterator();
    while(iter.hasNext()){
        Object obj= iter.next();
        System.out.println("方式1 迭代器遍历    "+obj);
    }

    //---------------方式2 普通for循环----------------------
    for(int i = 0; i<coll.size(); i++){
        System.err.println("方式2 普通for循环  "+coll.get(i));
    }

    //---------------方式3 增强for循环----------------------
    for(String s:coll){
        System.out.println("方式3 增强for循环  "+s);
    }
}

contains产生10个1-20之间的随机数，要求随机数不能重复

//产生10个1-20之间的随机数，要求随机数不能重复

@Test
public void IteratorTest03() {

    Random r = new Random();
    ArrayList<Integer> coll = new ArrayList();
    int count =0;

    while (count<10){
        int i = r.nextInt(20) + 1;
        if (!coll.contains(i)){
            coll.add(i);
            count++;
        }
    }
    System.out.println(coll.toString());
}

List接口：

List本身是Collection接口的子接口，具备了Collection的所有方法。现在学习List体系特有的共性方法，查阅方法发现List的特有方法都有索引，这是该集合最大的特点。

LIST的间接实现类：

LinkedList（双向链表）

Vector（向量）

功能和ArrayList一样，线程安全，Stack（栈）， 表示后进先出（LIFO）的对象堆栈

List：有序(元素存入集合的顺序和取出的顺序一致)，元素都有索引。元素可以重复。

• |--ArrayList：数组线性表，底层的数据结构是数组,线程不同步，ArrayList替代了Vector，查询元素的速度非常快。其内部基于一个大小可变数组来存储，允许存储 null 元素
• |--LinkedList：底层的数据结构是链表，线程不同步，增删元素的速度非常快。List 接口的链接列表实现类，允许存储 null 元素
• |--Vector：底层的数据结构就是数组，功能和ArrayList一样线程安全，Stack（栈），表示后进先出（LIFO）的对象堆栈，线程同步的，Vector无论查询和增删都巨慢。

List集合方法

1，添加：
    add(index,element) ：在指定的索引位插入元素。
    addAll(index,collection) ：在指定的索引位插入一堆元素。
2，删除：
    remove(index) ：删除指定索引位的元素。 返回被删的元素。
3，获取：
    Object get(index) ：通过索引获取指定元素。
    int indexOf(obj) ：获取指定元素第一次出现的索引位，如果该元素不存在返回-1；
                     所以，通过-1，可以判断一个元素是否存在。
    int lastIndexOf(Object o) ：反向索引指定元素的位置。
    List subList(start,end) ：获取子列表。
4，修改：
    Object set(index,element) ：对指定索引位进行元素的修改。
5，获取所有元素：
    ListIterator listIterator()：list集合特有的迭代器。
List集合支持对元素的增、删、改、查。

迭代过程中对元素进行操作

在进行list列表元素迭代的时候，如果想要在迭代过程中，想要对元素进行操作的时候，比如满足条件添加新元素。会发生ConcurrentModificationException并发修改异常。

导致的原因是：

集合引用和迭代器引用在同时操作元素，通过集合获取到对应的迭代器后，在迭代中，进行集合引用的元素添加，迭代器并不知道，所以会出现异常情况。

如何解决呢？

既然是在迭代中对元素进行操作,找迭代器的方法最为合适.可是Iterator中只有hasNext,next,remove方法.通过查阅的它的子接口,ListIterator,发现该列表迭代器接口具备了对元素的增、删、改、查的动作。

ListIterator是List集合特有的迭代器。

ListIterator it = list.listIterator;//取代Iterator it = list.iterator;

方法摘要
void	add(E e) 将指定的元素插入列表（可选操作）。
boolean	hasNext() 以正向遍历列表时，如果列表迭代器有多个元素，则返回 true（换句话说，如果 next 返回一个元素而不是抛出异常，则返回 true）。
boolean	hasPrevious() 如果以逆向遍历列表，列表迭代器有多个元素，则返回 true。
E	next() 返回列表中的下一个元素。
int	nextIndex() 返回对 next 的后续调用所返回元素的索引。
E	previous() 返回列表中的前一个元素。
int	previousIndex() 返回对 previous 的后续调用所返回元素的索引。
void	remove() 从列表中移除由 next 或 previous 返回的最后一个元素（可选操作）。
void	set(E e) 用指定元素替换 next 或 previous 返回的最后一个元素（可选操作）。

可变长度数组的原理

当元素超出数组长度，会产生一个新数组，将原数组的数据复制到新数组中，再将新的元素添加到新数组中。

ArrayList：是按照原数组的50%延长。构造一个初始容量为 10 的空列表。

Vector：是按照原数组的100%延长。

注意：对于list集合，底层判断元素是否相同，其实用的是元素自身的equals方法完成的。所以建议元素都要复写equals方法，建立元素对象自己的比较相同的条件依据。

List实现类之一：ArrayList

ArrayList概述

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

ArrayList 是List 接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

每个ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList 时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity 操作来增加ArrayList 实例的容量，这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

 相对比的，Vector 是线程安全的，其中涉及线程安全的方法皆被同步操作了。ArrayList和Vector除了线程不同步之外，大致相等。

ArrayList的实现

对于ArrayList 而言，它实现List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

属性

//默认容量的大小
private static final int DEFAULT_CAPACITY = 10;

//空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存放元素的数组，从这可以发现ArrayList的底层实现就是一个Object数组
transient Object[] elementData;

//数组中包含的元素个数
private int size;

//数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList的属性非常少，就只有这些。其中最重要的莫过于elementData了，ArrayList所有的方法都是建立在elementData之上。接下来，我们就来看一下一些主要的方法吧。

构造器：

ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

从构造方法中我们可以看见，默认情况下，elementData是一个大小为0的空数组，当我们指定了初始大小的时候，elementData的初始大小就变成了我们所指定的初始大小了。

读取：

因为ArrayList是采用数组结构来存储的，所以它的get方法非常简单，先是判断一下有没有越界，之后就可以直接通过数组下标来获取元素了，所以get的时间复杂度是O(1)。

//返回此列表中指定位置上的元素。

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

存储：

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)这些添加元素的方法。下面我们一一讲解：

//用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。
//set方法的作用是把下标为index的元素替换成element，跟get非常类似，
//所以就不在赘述了，时间复杂度度为O(1)。

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

//ArrayList的add方法也很好理解，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。在ensureCapacityInternal方法中，我们可以看见，如果当elementData为空数组时，它会使用默认的大小去扩容。所以说，通过无参构造方法来创建ArrayList时，它的大小其实是为0的，只有在使用到的时候，才会通过grow方法去创建一个大小为10的数组。

//第一个add方法的复杂度为O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的add方法，则复杂度为O(n)，因为涉及到对数组中元素的移动，这一操作是非常耗时的。

//将指定的元素添加到此列表的尾部。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//将指定的元素插入此列表中的指定位置。
//如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。
public void add(int index, E element) {
    rangeCheckForAdd(index);
    //如果数组长度不足，将进行扩容
    ensureCapacityInternal(size + 1);  
    // Increments modCount!!
    //将elementData中从Index位置开始、长度为size-index的元素，
    //拷贝到从下标为index+1位置开始的新的elementData数组中。
    //即将当前位于该位置的元素以及所有后续元素右移一个位置。
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

//从指定的位置开始，将指定collection中的所有元素插入到此列表中。
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

删除：

ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：

//移除此列表中指定位置上的元素。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

//移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。
public boolean remove(Object o) {
//由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
               //类似remove(intindex)，移除列表中指定位置上的元素。
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
remove方法与add带指定下标的方法非常类似，也是调用系统的arraycopy方法来移动元素，时间复杂度为O(n)。

注意：从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。

grow方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

grow方法是在数组进行扩容的时候用到的，从中我们可以看见，ArrayList每次扩容都是扩1.5倍，然后调用Arrays类的copyOf方法，把元素重新拷贝到一个新的数组中去。

size方法

public int size() {
    return size;
}

size方法非常简单，它是直接返回size的值，也就是返回数组中元素的个数，时间复杂度为O(1)。这里要注意一下，返回的并不是数组的实际大小。

8、indexOf方法和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;
}

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

indexOf方法的作用是返回第一个等于给定元素的值的下标。它是通过遍历比较数组中每个元素的值来查找的，所以它的时间复杂度是O(n)。

lastIndexOf的原理跟indexOf一样，而它仅仅是从后往前找起罢了。

调整数组容量：

从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现

Fail-Fast机制：

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险

ArrayList的JDK1.8之前与之后的实现区别？

• JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组
• JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
• lArrays.asList(…) 方法返回的List 集合，既不是ArrayList实例，也不是Vector 实例。Arrays.asList(…)  返回值是一个固定长度的List 集合

List 实现类之二：Vector

Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。很多方法都跟ArrayList一样，只是多加了个synchronized来保证线程安全

在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。

新增方法：

void addElement(Object obj)
void insertElementAt(Object obj,intindex)
void setElementAt(Object obj,intindex)
void removeElement(Object obj)
void removeAllElements()

Vector比ArrayList多了一个属性：

protected int capacityIncrement;

这个属性是在扩容的时候用到的，它表示每次扩容只扩capacityIncrement个空间就足够了。该属性可以通过构造方法给它赋值。先来看一下构造方法：

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

从构造方法中，我们可以看出Vector的默认大小也是10，而且它在初始化的时候就已经创建了数组了，这点跟ArrayList不一样。再来看一下grow方法：

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

从grow方法中我们可以发现，newCapacity默认情况下是两倍的oldCapacity，而当指定了capacityIncrement的值之后，newCapacity变成了oldCapacity+capacityIncrement。

List实现类之三：LinkedList

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

LinkedList的特有方法。

1. void  addFirst(Object o)，将指定数据元素插入此集合的开头,原来元素（如果有）后移；
   void addLast(Object o)，将指定数据元素插入此集合的结尾
   Object getFirst()，返回此集合的第一个数据元素
   Object getLast()，返回此集合的最后一个数据元素
   Object removeFirst()，移除并返回集合表的第一个数据元素
   Object removeLast()，移除并返回集合表的最后一个数据元素

   LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。它允许插入所有元素，包括null，同时，它是线程不同步的。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：

双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个first指针，指向头节点，和last指针，指向尾节点。

prev变量记录前一个元素的位置

next变量记录下一个元素的位置

属性

接下来看一下 LinkedList 中的属性：

//链表的节点个数
transient int size = 0;
//指向头节点的指针
transient Node<E> first;
//指向尾节点的指针
transient Node<E> last;
LinkedList 的属性非常少，就只有这些。通过这三个属性，其实我们大概也可以猜测出它是怎么实现的了。

方法

1、结点结构

Node 是在 LinkedList 里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域item，一个后置指针next，一个前置指针prev。

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

2、添加元素

对于链表这种数据结构来说，添加元素的操作无非就是在表头/表尾插入元素，又或者在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。

在表头添加元素的过程如下：

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点，源码的实现如下：

private void linkFirst(E e) {
    final Node<E> f = first;
    //当前节点的前驱指向null，后继指针原来的头节点
    final Node<E> newNode = new Node<>(null, e, f);
    //头指针指向新的头节点
    first = newNode;
    //如果原来有头节点，则更新原来节点的前驱指针，否则更新尾指针
    if (f == null)
        last = newNode;
    else
    f.prev = newNode;
    size++;
    modCount++;
}

在表尾添加元素跟在表头添加元素大同小异，如图所示：

当向表尾插入一个节点时，很显然当前节点的后继一定为 null，而前驱结点是 last 指针指向的节点，然后还要修改 last 指针指向新的尾节点。此外，还要修改原来尾节点的后继指针，使它指向新的尾节点，源码的实现如下：

void linkLast(E e) {
    final Node<E> l = last;
    //当前节点的前驱指向尾节点，后继指向null
    final Node<E> newNode = new Node<>(l, e, null);
    //尾指针指向新的尾节点
    last = newNode;
    //如果原来有尾节点，则更新原来节点的后继指针，否则更新头指针
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

最后，在指定节点之前插入，如图所示：

当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点，源码的实现如下：

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //指定节点的前驱
    final Node<E> pred = succ.prev;
    //当前节点的前驱为指点节点的前驱，后继为指定的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //更新指定节点的前驱为当前节点
    succ.prev = newNode;
    //更新前驱节点的后继
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

3、删除元素

删除操作与添加操作大同小异，例如删除指定节点的过程如下图所示，需要把当前节点的前驱节点的后继修改为当前节点的后继，以及当前节点的后继结点的前驱修改为当前节点的前驱（是不是很绕？）：

删除头节点和尾节点跟删除指定节点非常类似，就不一一介绍了，源码如下：

//删除表头节点，返回表头元素的值 
private E unlinkFirst(Node<E> f) { 
    // assert f == first && f != null; 
    final E element = f.item; 
    final Node<E> next = f.next; 
    f.item = null; 
    f.next = null; // help GC 
    first = next; //头指针指向后一个节点 
    if (next == null) 
        last = null; 
    else 
        next.prev = null; //新头节点的前驱为null 
    size--; 
    modCount++; 
    return element; 
} 
//删除表尾节点，返回表尾元素的值 
private E unlinkLast(Node<E> l) { 
    // assert l == last && l != null; 
    final E element = l.item; 
    final Node<E> prev = l.prev; 
    l.item = null; 
    l.prev = null; // help GC 
    last = prev; //尾指针指向前一个节点 
    if (prev == null) 
        first = null; 
    else 
        prev.next = null; //新尾节点的后继为null 
    size--; 
    modCount++; 
    return element; 
} 
//删除指定节点，返回指定元素的值 
E unlink(Node<E> x) { 
    // assert x != null; 
    final E element = x.item; 
    final Node<E> next = x.next; //当前节点的后继 
    final Node<E> prev = x.prev; //当前节点的前驱 
    if (prev == null) { 
        first = next; 
    } else { 
        prev.next = next; //更新前驱节点的后继为当前节点的后继 
        x.prev = null; 
    } 
    if (next == null) { 
        last = prev; 
    } else { 
        next.prev = prev; //更新后继节点的前驱为当前节点的前驱 
        x.next = null; 
    } 
    x.item = null; 
    size--; 
    modCount++; 
    return element; 
} 

4、获取元素

获取元素的方法一看就懂，我就不必多加解释了。

//获取表头元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//获取表尾元素
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

//获取指定下标的元素
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

5、常用方法

前面介绍了链表的添加和删除操作，你会发现那些方法都不是 public 的，LinkedList 是在这些基础的方法进行操作的，下面就来看看我们可以调用的方法有哪些。

//删除表头元素

public E removeFirst() { 
    final Node<E> f = first; 
    if (f == null) 
        throw new NoSuchElementException(); 
    return unlinkFirst(f); 
}

//删除表尾元素

public E removeLast() { 
    final Node<E> l = last; 
    if (l == null) 
        throw new NoSuchElementException(); 
    return unlinkLast(l); 
} 

//插入新的表头节点

public void addFirst(E e) { 
    linkFirst(e); 
}

//插入新的表尾节点

public void addLast(E e) { 
    linkLast(e); 
} 

//链表的大小

public int size() { 
    return size; 
}

//添加元素到表尾

public boolean add(E e) { 
    linkLast(e); 
    return true; 
}

//删除指定元素

public boolean remove(Object o) { 
    if (o == null) { 
        for (Node<E> x = first; x != null; x = x.next) { 
            if (x.item == null) { 
                unlink(x); 
                return true; 
            } 
        } 
    } else { 
        for (Node<E> x = first; x != null; x = x.next) { 
            if (o.equals(x.item)) { 
                unlink(x); 
                return true; 
            } 
        } 
    } 
    return false; 
} 

//获取指定下标的元素

public E get(int index) { 
    checkElementIndex(index); //先检查是否越界 
    return node(index).item; 
}

//替换指定下标的值

public E set(int index, E element) { 
    checkElementIndex(index); 
    Node<E> x = node(index); 
    E oldVal = x.item; 
    x.item = element; 
    return oldVal; 
}

//在指定位置插入节点

public void add(int index, E element) { 
    checkPositionIndex(index); 
    if (index == size) 
        linkLast(element); 
    else 
        linkBefore(element, node(index)); 
} 

//删除指定下标的节点

public E remove(int index) { 
    checkElementIndex(index); 
    return unlink(node(index)); 
} 

//获取表头节点的值，表头为空返回null

public E peek() { 
    final Node<E> f = first; 
    return (f == null) ? null : f.item; 
}

//获取表头节点的值，表头为空抛出异常

public E element() { 
    return getFirst(); 
}

//获取表头节点的值，并删除表头节点，表头为空返回null

public E poll() { 
    final Node<E> f = first; 
    return (f == null) ? null : unlinkFirst(f); 
} 

//添加元素到表头

public void push(E e) { 
    addFirst(e); 
}

//删除表头元素

public E pop() { 
    return removeFirst(); 
} 

总结

1、LinkedList 的底层结构是一个带头/尾指针的双向链表，可以快速的对头/尾节点进行操作。

2、相比数组，链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的效率就不如数组那么高了。

数组线性表与数组的区别：

数组是定长有序的线型集合，数组线性表是任意长度的线型集合

故：1. 两者本质的区别在与长度是否可变。

2. 两者获取元素的方式不同

数组：使用下标：array [index]。数组线性表：使用get方法：list.get(index)

3. 获取长度的方式不同，数组：length属性，数组线性表：size()方法

Vector是线程安全（synchronized）的，而ArrayList是非线程安全的，所以调用方法名相同的方法时，Vector对象要比ArrayList对象稍慢一些。

ArrayList，LinkedList，Vector的异同？谈谈你的理解？ArrayList底层是什么？扩容机制？Vector和ArrayList的最大区别?

ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。

此外，ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

Vector和 ArrayList

• 1、ArrayList创建时的大小为0；当加入第一个元素时，进行第一次扩容时，默认容量大小为10。
• 2、ArrayList每次扩容都以当前数组大小的1.5倍去扩容。
• 3、Vector创建时的默认大小为10。
• 4、Vector每次扩容都以当前数组大小的2倍去扩容。当指定了capacityIncrement之后，每次扩容仅在原先基础上增加capacityIncrement个单位空间。
• 5、ArrayList和Vector的add、get、size方法的复杂度都为O(1)，remove方法的复杂度为O(n)。
• 6、ArrayList是非线程安全的，Vector是线程安全的。

List排序对象类

public class Student{
    private String name;
    private Integer age;
    public Student() {
    }
    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
}

方式一：排序对象类实现Comparable接口的compareTo方法

Student类
public class Student implements Comparable<Student>{
    private String name;
    private Integer age;
    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
    public Student() {
    }
    /**
     * 需要实现的方法，实现升序排序，降序请反写
     * this表示当前的对象
     * @param o 比较时传入的对象
     * @return
     */
    @Override
    public int compareTo(Student o) {
        return this.age-o.age;
    }
}
Main
public class Test {
    public static void main(String[] args) {
        //数据准备
        List<Student> list = new ArrayList<>();
        list.add(new Student("小明",1));
        list.add(new Student("小红",4));
        list.add(new Student("小刚",3));
        list.add(new Student("小鸡",5));
        list.add(new Student("小狗",2));
        //使用Collections集合工具类进行排序
        Collections.sort(list);
        for (Student student : list) {
            System.out.println(student);
        }
    }
}
compareTo方法实际上是一个比较大小的方法，只要是排序，我们必须用到比较，
若果是简单的整数数组排序，我们只需要用 > 、 < 等进行比较，
但是对于对象来说，Collections集合工具类在进行排序时，每次比较，
都是调用的我们实现的compareTo方法，this表示当前对象，o表示要进行比较的传入对象，
返回是一个int类型的整数
•	返回值>0：表示当前对象比传入对象大（年龄）
•	返回值=0：表示当前对象和传入对象一样大（年龄）
•	返回值<0：表示当前对象比传入对象小（年龄）
排序结果：
Student{name='小明', age=1}
Student{name='小狗', age=2}
Student{name='小刚', age=3}
Student{name='小红', age=4}
Student{name='小鸡', age=5}

Process finished with exit code 

方式二：使用Comparator接口自定义行为

使用方式一我们必须在Student类上面进行修改，这显然不是最好的办法，如果我们不想按年龄排序，想要按照姓名排序，或者我们有一个方法需要按照年龄，另一个方法需要按照姓名，那么重写compareTo方法显然就没法完成我们的目标了，Collections的重载sort方法可以允许我们在排序对象外部自定义一个比较器（Comparator接口的实现类），因为我们仅需要实现compare（）方法（实际上Comparator接口是一个函数式接口，无伤大雅最后解释，想了解的看最后），没必要在定义一个类，我们直接使用匿名内部类的方式。

此时的Student类我们不用进行任何改写，和最原始的一样即可

Main
public class Test {
    public static void main(String[] args) {
        //数据准备
        List<Student> list = new ArrayList<>();
        list.add(new Student("小明",1));
        list.add(new Student("小红",4));
        list.add(new Student("小刚",3));
        list.add(new Student("小鸡",5));
        list.add(new Student("小狗",2));
        //使用Collections集合工具类进行排序
        Collections.sort(list, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                //升序排序，降序反写
                return o1.getAge()-o2.getAge();
            }
        });
        for (Student student : list) {
            System.out.println(student);
        }
    }
}
排序结果：
Student{name='小明', age=1}
Student{name='小狗', age=2}
Student{name='小刚', age=3}
Student{name='小红', age=4}
Student{name='小鸡', age=5}

Process finished with exit code 0
我们也可以使用List的sort方法（这是List接口的一个默认方法）源码如下：
@SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
我们也需要传入一个Comparator，此处使用匿名类的形式，代码如下：
public static void main(String[] args) {
        //数据准备
        List<Student> list = new ArrayList<>();
        list.add(new Student("小明",1));
        list.add(new Student("小红",4));
        list.add(new Student("小刚",3));
        list.add(new Student("小鸡",5));
        list.add(new Student("小狗",2));


        list.sort(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        });

        for (Student student : list) {
            System.out.println(student);
        }

    }

方式三：Lambda表达式

Collections.sort(list, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                //升序排序，降序反写
                return o1.getAge()-o2.getAge();
            }
        });
变为
Collections.sort(list, (o1, o2) -> o1.getAge() - o2.getAge());
或者使用list的sort方法：
将
 list.sort(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        });
变为：
list.sort((o1, o2) -> o1.getAge()-o2.getAge());

方式四：使用方法引用进一步简化

上文方式三
Collections.sort(list, (o1, o2) -> o1.getAge() - o2.getAge());
可以变为：
Collections.sort(list, Comparator.comparingInt(Student::getAge));
使用List的sort方法时：
list.sort((o1, o2) -> o1.getAge()-o2.getAge());
可以改为
list.sort(Comparator.comparingInt(Student::getAge));

方式五：使用Stream流

List<Student> students = list.stream().
                sorted((Comparator.comparingInt(Student::getAge)))
                .collect(Collectors.toList());

注：返回一个有序的List集合

关于Comparator接口

    文说Comparator接口是一个函数式接口，那么什么是函数式接口呢？

    函数式接口就是只定义一个抽象方法的接口。

    JDK1.8开始支持默认方法，即便这个接口拥有很多默认方法，只要接口只有一个抽象方法，那么这个接口就是函数式接口。

    函数式接口常常用@FunctionInterface来标注，不是必须的，带有@FunctionInterface注解的接口如果不满足函数式接口（有多个抽象方法），编译器会返回提示信息，自己创建函数式接口时推荐使用。

两个对象排序

插入排序

两个对象的一个属性比大小排序

普通排序
for (int i = 0; i < 100; i++) {
    System.err.print("=" + pmsProductList.get(i).getProductCategoryId());
}
long ba = System.currentTimeMillis();
for (int i = 1; i < pmsProductList.size(); i++) {
    PmsProduct temp = pmsProductList.get(i);
    int j;
    for (j = i; j > 0 && pmsProductList.get(j - 1).getProductCategoryId().longValue() < temp.getProductCategoryId().longValue(); j--) {
        pmsProductList.set(j, pmsProductList.get(j - 1));
    }
    pmsProductList.set(j, temp);
}
System.out.println(System.currentTimeMillis() - ba);

Lambda排序
long a = System.currentTimeMillis();
IntStream.range(1, pmsProductList.size()).forEach(currentIndex -> {
    PmsProduct pmsProduct = pmsProductList.get(currentIndex);
    long currentValue = pmsProduct.getProductCategoryId().longValue();
    IntStream.range(0, currentIndex).filter(j -> pmsProductList.get(j).getProductCategoryId().longValue() > currentValue).findFirst().ifPresent(switchIndex -> {
        IntStream.iterate(currentIndex, a2 -> a2 - 1).limit(currentIndex - switchIndex).forEach(a2 -> {
            pmsProductList.set(a2, pmsProductList.get(a2 - 1));
        });
        pmsProductList.set(switchIndex, pmsProduct);
    });
});
System.out.println(System.currentTimeMillis() - a);

Set接口：

Set 接口概述

• Set接口是Collection的子接口，set接口没有提供额外的方法。
• Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
• Set 判断两个对象是否相同不是使用==运算符，而是根据equals() 方法

Set接口取出方式

Set接口中的方法和Collection中方法一致的。Set接口取出方式只有一种，迭代器。

Set实现类之一：HashSet

HashSet是Set 接口的典型实现，大多数时候使用Set 集合时都使用这个实现类，线程是不同步的。无序，高效，底层数据结构是哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

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

HashSet具有以下特点：

不能保证元素的排列顺序，HashSet不是线程安全的，集合元素可以是null

HashSet 集合判断两个元素相等的标准：

两个对象通过hashCode() 方法比较相等，并且两个对象的equals() 方法返回值也相等。

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

向HashSet中添加元素的过程：

    当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值，通过某种散列函数决定该对象在HashSet底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）

    如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。

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

底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32，依次为64,128....等）

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

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

重写equals() 方法的基本原则

以自定义的Customer类为例，何时需要重写equals()？

    当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。

    因此，违反了“相等的对象必须具有相等的散列码”。

    结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

Eclipse/IDEA工具里hashCode()的

以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals和hashCode。

问题：为什么用Eclipse/IDEA复写hashCode方法，有31这个数字？

选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）

并且31只占用5bits,相乘造成数据溢出的概率较小。

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

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

HashSet的实现

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成， HashSet的源代码如下：

package java.util;

import java.io.InvalidObjectException;
import sun.misc.SharedSecrets;

public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
static final long serialVersionUID = -5024744406713321676L;

//底层使用HashMap来保存HashSet中所有元素。
private transient HashMap<E,Object> map;

//定义一个虚拟的Object对象作为HashMap的value，将此对象定义为staticfinal。
    private static final Object PRESENT = new Object();

/**
*默认的无参构造器，构造一个空的HashSet。
*实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
*/
    public HashSet() {
        map = new HashMap<>();
    }       

/**
       	* 构造一个包含指定 collection中的元素的新 set。
       	* 实际底层使用默认的加载因子 0.75和足以包含指定
       	* collection中所有元素的初始容量来创建一个 HashMap。
       	* @param c 其中的元素将存放在此 set中的 collection。
       	*/
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

         /** 
         	* 以指定的 initialCapacity和 loadFactor构造一个空的 HashSet。
         	*
         	* 实际底层以相应的参数构造一个空的 HashMap。
         	* @param initialCapacity 初始容量。
         	* @param loadFactor 加载因子。
         	*/         
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }  

      	/**
  	* 以指定的 initialCapacity构造一个空的 HashSet。
  	*
  	* 实际底层以相应的参数及加载因子 loadFactor为 0.75构造一个空的 HashMap。
  	* @param initialCapacity 初始容量。
  	*/    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

       	/**
       	* 以指定的 initialCapacity和 loadFactor构造一个新的空链接哈希集合。
       	* 此构造函数为包访问权限，不对外公开，实际只是是对 LinkedHashSet的支持。
       	*        
       	* 实际底层会以指定的参数构造一个空 LinkedHashMap实例来实现。
       	* @param initialCapacity 初始容量。
       	* @param loadFactor 加载因子。
       	* @param dummy 标记。
       	*/
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }  

     	/**
  	* 返回对此 set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。
  	*
  	* 底层实际调用底层 HashMap的 keySet来返回所有的 key。
  	* 可见 HashSet中的元素，只是存放在了底层 HashMap的 key上，
  	* value使用一个 static final的 Object对象标识。
         * @return 对此 set中元素进行迭代的 Iterator。
  	*/
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }      
 
   /**
   	* 返回此 set中的元素的数量（set的容量）。
   	*
   	* 底层实际调用 HashMap的 size()方法返回 Entry的数量，就得到该 Set中元素的个数。 
   	* @return 此 set中的元素的数量（set的容量）。
   	*/
    public int size() {
        return map.size();
    }

    /**
    * 如果此 set不包含任何元素，则返回 true。
     *
     * 底层实际调用 HashMap的 isEmpty()判断该 HashSet是否为空。
     * @return 如果此 set不包含任何元素，则返回 true。
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

       	 /**
		* 如果此 set包含指定元素，则返回 true。
		* 更确切地讲，当且仅当此 set包含一个满足(o==null ? e==null : o.equals(e))
		* 的 e元素时，返回 true。
		*
		* 底层实际调用 HashMap的 containsKey判断是否包含指定 key。
		* @param o 在此 set中的存在已得到测试的元素。
		* @return 如果此 set包含指定元素，则返回 true。
		*/
    public boolean contains(Object o) {
        return map.containsKey(o);
    }   

/**
    *如果此set中尚未包含指定元素，则添加指定元素。
    *更确切地讲，如果此set没有包含满足(e==null?e2==null:e.equals(e2))
    *的元素e2，则向此set添加指定的元素e。
    *如果此set已包含该元素，则该调用不更改set并返回false。
    *
    *底层实际将将该元素作为key放入HashMap。
    *由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key
    *与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），
    *新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，
    *因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，
    *原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。
    *@parame将添加到此set中的元素。
    *@return如果此set尚未包含指定元素，则返回true。
    */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
/**
  *如果指定元素存在于此set中，则将其移除。
  *更确切地讲，如果此set包含一个满足(o==null?e==null:o.equals(e))的元素e，
  *则将其移除。如果此set已包含该元素，则返回true
  *（或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。
  *
  *底层实际调用HashMap的remove方法删除指定Entry。
  *@paramo如果存在于此set中则需要将其移除的对象。
  *@return如果set包含指定元素，则返回true。
  */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * 从此set中移除所有元素。此调用返回后，该set将为空。
     * 底层实际调用HashMap的clear方法清空Entry中所有元素。
     */
    public void clear() {
        map.clear();
    }

    
/**
*返回此HashSet实例的浅表副本：并没有复制这些元素本身。
*
*底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。
*/

    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    /**
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
     * set.
     *
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
     * {@link Spliterator#DISTINCT}.  Overriding implementations should document
     * the reporting of additional characteristic values.
     *
     * @return a {@code Spliterator} over the elements in this set
     * @since 1.8
     */
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}

Set实现类之二：LinkedHashSet

• LinkedHashSet：有序，hashset的子类。由于该实现类对象维护着一个运行于所有元素的双重链接列表，由于该链接列表定义了迭代顺序，所以在遍历该实现类集合时按照元素的插入顺序进行遍历
• LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
• LinkedHashSet插入性能略低于HashSet，但在迭代访问Set 里的全部元素时有很好的性能。
• LinkedHashSet不允许集合元素重复。

Set实现类之三：TreeSet

• TreeSet：对Set集合中的元素的进行指定顺序的排序。不同步。TreeSet底层的数据结构就是二叉树。既实现Set接口，同时也实现了SortedSet接口，具有排序功能
• TreeSetTreeSet 是 SortedSet SortedSet SortedSet接口的实现类， TreeSetTreeSetTreeSet TreeSet可以确保集合元素处于排序 可以确保集合元素处于排序状态。
• 存入TreeSet中的对象元素需要实现Comparable接口
• TreeSet两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。
• TreeSet和后面要讲的TreeMap采用红黑树的存储结构

特点：有序，查询速度比List快

TreeSet集合排序有两种方式，Comparable和Comparator区别：

• 1：让元素自身具备比较性，需要元素对象实现Comparable接口，覆盖compareTo方法。
• 2：让集合自身具备比较性，需要定义一个实现了Comparator接口的比较器，并覆盖compare方法，并将该类对象作为实际参数传递给TreeSet集合的构造函数。

第二种方式较为灵活。

排序—自然排序

• 自然排序：TreeSet会调用集合元素的compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列
• 如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable 接口。
• 实现Comparable 的类必须实现compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

Comparable 的典型实现：

1. BigDecimal、BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较
2. Character：按字符的unicode值来进行比较
3. Boolean：true 对应的包装类实例大于false 对应的包装类实例
4. String：按字符串中字符的unicode 值进行比较
5. Date、Time：后边的时间、日期比前面的时间、日期大

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

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

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

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

排序—定制排序

    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。

Comparable接口和Comparator接口的使用和区别

Comparable

Comparable接口在JDK8中的源码：
package java.lang;
import java.util.*;
package java.lang;
public interface Comparable<T> {
    public int compareTo(T o);
}
用法：
public class User implements Comparable<User>{
    private Integer id;
    private Integer age;

    public User() {
    }

    public User(Integer id, Integer age) {
        this.id = id;
        this.age = age;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "id=" + id +
                ", age=" + age +
                '}';
    }

    public int compareTo(User o) {
        if(this.age > o.getAge()) {
            return 1;
        }else if(this.age < o.getAge()) {
            return -1;
        }else{
            return 0;
        }
    }
}
public class Test {
    public static void main(String[] args) {
        User user1 = new User(1, 14);
        User user2 = new User(2, 12);
        User user3 = new User(3, 10);
        User[] users = {user1, user2, user3};
        Arrays.sort(users);
        Arrays.stream(users).forEach(System.out::println);
    }
}

int compareTo(T o)

比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

参数： o - 要比较的对象。

返回：负整数、零或正整数，根据此对象是小于、等于还是大于指定对象。

抛出：ClassCastException - 如果指定对象的类型不允许它与此对象进行比较

Comparator

Comparator接口在JDK8中的源码：

Comparator接口在JDK8中的源码：
package java.util;

import java.io.Serializable;
import java.util.function.Function;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;
import java.util.function.ToDoubleFunction;
import java.util.Comparators;

public interface Comparator<T> {
	int compare(T o1, T o2);
	//还有很多其他方法...
}
使用：
public class Child {
    private Integer id;
    private Integer age;

    public Child() {
    }

    public Child(Integer id, Integer age) {
        this.id = id;
        this.age = age;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Child{" +
                "id=" + id +
                ", age=" + age +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {
        Child child1 = new Child(1, 14);
        Child child2 = new Child(2, 12);
        Child child3 = new Child(3, 10);

        List<Child> list = new ArrayList<>();
        list.add(child1);
        list.add(child2);
        list.add(child3);

        Collections.sort(list, new Comparator<Child>() {
            @Override
            public int compare(Child o1, Child o2) {
                return  o1.getAge() > o2.getAge() ? 1 : (o1.getAge() == o2.getAge() ? 0 : -1);
            }
        });

        // 或者使用JDK8中的Lambda表达式
        //Collections.sort(list, (o1, o2) -> (o1.getAge()-o2.getAge()));

        list.stream().forEach(System.out::println);
    }
}
或者也可以通过实现的方式使用Comparator接口：
import java.util.Comparator;

public class Child implements Comparator<Child> {
    private Integer id;
    private Integer age;

    public Child() {
    }

    public Child(Integer id, Integer age) {
        this.id = id;
        this.age = age;
    }

    @Override
    public int compare(Child o1, Child o2) {
        return o1.getAge() > o2.getAge() ? 1 : (o1.getAge() == o2.getAge() ? 0 : -1);
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Child{" +
                "id=" + id +
                ", age=" + age +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {
        Child child1 = new Child(1, 14);
        Child child2 = new Child(2, 12);
        Child child3 = new Child(3, 10);

        List<Child> list = new ArrayList<>();
        list.add(child1);
        list.add(child2);
        list.add(child3);
        
        Collections.sort(list, new Child());
        list.stream().forEach(System.out::println);
    }
}

Comparator接口其他默认方法的用法

reversed方法

default Comparator<T> reversed() {
        return Collections.reverseOrder(this);
    }
这个方法是用来生成一个逆序器,比如我们开始需要得到一个正序的排序序列,然后又想得到一个反转的排序序列,就可以使用该方法。比如：
public class Test {
    public static void main(String[] args) {
        Child child1 = new Child(1, 14);
        Child child2 = new Child(2, 12);
        Child child3 = new Child(5, 10);
        Child child4 = new Child(4, 10);

        List<Child> list = new ArrayList<>();
        list.add(child1);
        list.add(child2);
        list.add(child3);
        list.add(child4);

        Comparator<Child> comparator = Comparator.comparingInt(x -> x.getAge());
        Collections.sort(list, comparator);
        list.stream().forEach(System.out::println);
        Collections.sort(list, comparator.reversed());
        list.stream().forEach(System.out::println);
    }
}
thenComparing
default <U extends Comparable<? super U>> Comparator<T> thenComparing(
            Function<? super T, ? extends U> keyExtractor) {
        return thenComparing(comparing(keyExtractor));
}
该方法是在原有的比较器上再加入一个比较器，比如先按照年龄排序，年龄相同的在按照id排序。比如：
public class Test {
    public static void main(String[] args) {
        Child child1 = new Child(1, 14);
        Child child2 = new Child(2, 12);
        Child child3 = new Child(5, 10);
        Child child4 = new Child(4, 10);

        List<Child> list = new ArrayList<>();
        list.add(child1);
        list.add(child2);
        list.add(child3);
        list.add(child4);

        Comparator<Child> comparator = Comparator.comparingInt(x -> x.getAge());
        Collections.sort(list, comparator);
        list.stream().forEach(System.out::println);
        System.out.println("-----");
        Collections.sort(list, comparator.thenComparing(x->x.getId()));
        list.stream().forEach(System.out::println);
    }
}

Comparable接口和Comparator接口的区别

• Comparable接口位于java.lang包下；Comparator位于java.util包下
• Comparable接口只提供了一个compareTo()方法；Comparator接口不仅提供了compara()方法，还提供了其他默认方法，如reversed()、thenComparing()，使我们可以按照更多的方式进行排序
• 如果要用Comparable接口，则必须实现这个接口，并重写comparaTo()方法；但是Comparator接口可以在类外部使用，通过将该接口的一个匿名类对象当做参数传递给Collections.sort()方法或者Arrays.sort()方法实现排序。Comparator体现了一种策略模式，即可以不用要把比较方法嵌入到类中，而是可以单独在类外部使用，这样我们就可有不用改变类本身的代码而实现对类对象进行排序

Comparable接口

Comparable称为内部比较器,String和各种包装类已经实现,TreeSet集合内默认是按照自然顺序排序的,在集合内元素之间的比较，由该类的compareTo(Object o)方法来完成，因为这种比较是在类内部实现，所以将Comparable称为内部比较器

Comparator

外部比较器,配合Collections工具类的sort(List list, Comparator c)方法使用。当集合中的对象不支持自比较或者自比较的功能不能满足需求时使用和内部比较器相比，其可重用性好.

哈希表的原理：

1. 1，对对象元素中的关键字(对象中的特有数据)，进行哈希算法的运算，并得出一个具体的算法值，这个值 称为哈希值。
2. 2，哈希值就是这个元素的位置。
3. 3，如果哈希值出现冲突，再次判断这个关键字对应的对象是否相同。如果对象相同，就不存储，因为元素重复。如果对象不同，就存储，在原来对象的哈希值基础 +1顺延。
4. 4，存储哈希值的结构，我们称为哈希表。
5. 5，既然哈希表是根据哈希值存储的，为了提高效率，最好保证对象的关键字是唯一的。
6.   这样可以尽量少的判断关键字对应的对象是否相同，提高了哈希表的操作效率。

判断元素是否存在或者删元素底层依据

对于ArrayList集合，判断元素是否存在，或者删元素底层依据都是equals方法。

对于HashSet集合，判断元素是否存在，或者删除元素，底层依据的是hashCode方法和equals方法。

如果两个类不同的话使用下面两个方法可以规避类转换异常：

先存人后存狗，狗是无法调用人里面的Equals方法：