声明: 
              1. 本文根据韩顺平老师教学视频自行整理，以便记忆
              2. 若有错误不当之处, 请指出

  系列文章目录

Java基础知识总结（第一篇）：基础语法

Java基础知识总结（第二篇）：流程控制语句(分支控制和循环控制)

Java基础知识总结（第三篇）：数组、排序和查找

Java基础知识总结（第四篇）：面向对象编程基础(类、对象、方法、包以及封装继承多态)

Java基础知识总结（第五篇）：面向对象编程进阶(代码块，抽象类、接口和内部类)

Java基础知识总结（第六篇）：枚举、注解和异常

Java基础知识总结（第七篇）：常用类：包装类、日期类以及String、StringBuffer、Builder、Math 、Arrays 、System 、BigInteger和BigDecimal

目录

一、集合

1.集合的理解与好处

（一）数组的不足分析

（二）集合的优点

2.集合的框架体系

二、Collection

1.Collection 接口

（一）Collection 接口实现类的特点

（二）Collection 接口常用方法

（三）Collection 接口遍历元素

（1）方式 1-使用 Iterator(迭代器)

（2）方式 2-for 循环增强

2.List

（一）List接口

（1）介绍

（2）List 接口的常用方法

（二）ArrayList

（1）ArrayList说明

（2）ArrayList底层结构

（三）Vector

（1）Vector底层结构

（四）LinkedList

（1）LinkedList说明

（2）LinkedList底层结构

（五）Vector 和 ArrayList 的比较

（六）ArrayList 和 LinkedList 的比较

3.Set

（一）Set接口

（1）介绍

（2）Set接口的常用方法

（3）Set 接口的遍历方式

（二）HashSet

（1）HashSet说明

（2）HashSet底层结构 

HashSet元素添加机制

HashSet的扩容和转成红黑树机制

（三）LinkedHashSet

（1）LinkedHashSet说明

（2）LinkedHashSet底层结构

（四）TreeSet

（1）TreeSet说明

（2）TreeSet底层结构

三、Map

1.Map接口

（一）Map 接口实现类的特点

（二）Map 接口常用方法

（三）Map六大遍历方式

（1）使用keySet()方法遍历

（2）使用values()方法遍历

（3）使用entrySey()方法遍历

2.HashMap

（一）HashMap说明

（二）HashMap底层结构

3.Hashtable

（一）Hashtable说明

（二）Hashtable底层结构

4.HashMap和Hashtable对比

5.Properties

（一）Properties说明

7.TreeMap

（一）TreeMap说明

（二）TreeMap底层结构

四、开发中如何选择集合实现类

五、Collections工具类

1.Collections 工具类介绍

2.排序操作：（均为 static 方法)

3.查找、替换

一、集合

1.集合的理解与好处

（一）数组的不足分析

（1）长度开始时必须指定，而且一旦指定，不能更改

（2）保存的必须为同一类型的元素

（3）使用数组进行增加/删除元素比较麻烦

（二）集合的优点

（1）可以动态保存任意多个对象，使用比较方便!

（2）提供了一系列方便的操作对象的方法：add、remove、set、get等

（3）使用集合添加，删除新元素简洁明了

2.集合的框架体系

（1） 集合主要是两组(单列集合 , 双列集合)

（2）Collection 接口有两个重要的子接口 List Set , 他们的实现子类都是单列集合

（3）Map 接口的实现子类 是双列集合，存放的 K-V

单列集合继承图：

双列集合继承图：

二、Collection

1.Collection 接口

（一）Collection 接口实现类的特点

public interface Collection<E>extends Iterable<E>

（1）collection实现子类可以存放多个元素，每个元素可以是Object

（2）有些Collection的实现类，可以存放重复的元素，有些不可以

（3）有些Collection的实现类，有些是有序的(List),有些不是有序(Set)

（4）Collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的

（二）Collection 接口常用方法

（1）add:添加单个元素

list.add("jack");
list.add(10);//相当于list.add(new Integer(10));
list.add(true);

（2）remove:删除指定元素

list.remove(0);//删除第一个元素，根据索引删除，返回的是被删除的对象
list.remove(true);//指定删除某个元素，返回的是被删除对象的索引值

（3）contains:查找元素是否存在

list.contains("jack")//存在返回true，不存在返回false

（4）size:获取元素个数

list.size()

（5）isEmpty:判断是否为空

list.isEmpty()

（6）clear:清空

list.clear()

（7）addAll:添加多个元素

list2.add("红楼梦");
list2.add("三国演义");
list.addAll(list2);

（8）containsAll:查找多个元素是否都存在

(list.containsAll(list2)

（9）removeAll：删除多个元素

list.removeAll(list2);

（三）Collection 接口遍历元素

（1）方式 1-使用 Iterator(迭代器)

介绍：

1)Iterator是Iterable接口里面的一个接口  

2)Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。

3)所有实现了Collection接口的集合类都有一个iterator方法，用以返回一个实现了Iterator接口的对象，即可以返回一个迭代器。？

4)Iterator仅用于遍历集合，Iterator本身并不存放对象。

Iterator接口的方法：

hasNext():判断是否还有下一个元素

next():作用1.下移2.将下移以后集合位置上的元素返回

使用：

//1. 先得到 col 对应的 迭代器
Iterator iterator = col.iterator();
//2. 使用 while 循环遍历
while (iterator.hasNext()) {//判断是否还有数据
    //返回下一个元素，类型是 Object
    Object obj = iterator.next();
    System.out.println("obj=" + obj);
}
//3. 如果希望再次遍历，需要重置我们的迭代器
iterator = col.iterator();

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

（2）方式 2-for 循环增强

增强for就是简化版的iterator,本质一样。只能用于遍历集合或数组。

基本语法：for(元素类型 元素名：集合名或数组名){访问元素}

示例：  

for (Object dog : list) {
System.out.println("dog=" + dog);
}

2.List

（一）List接口

（1）介绍

List接口是Collection接口的子接口

1)List集合类中元素有序(即添加顺序和取出顺序一致)、且可重复

2)List集合中的每个元素都有其对应的顺序索引，即支持索引

3)List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

4)List接口常用的实现类有：ArrayList、LinkedList和Vector。

（2）List 接口的常用方法

（二）ArrayList

（1）ArrayList说明

1)permits all elements,including null,ArrayList可以加入null,并且可以有多个null

2)ArrayList是由数组来实现数据存储的

3)ArrayList基本等同于Vector,除了ArrayList是线程不安全(执行效率高)看源码.在多线程情况下，不建议使用ArrayList

（2）ArrayList底层结构

1)ArrayList中维护了一个Object类型的数组elementData.

底层源码：

transient Object[] elementData; // non-private to simplify nested class access

transient表示瞬间，短暂的，表示该属性不会被序列号

2)当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0,第1次添加，则扩容elementData为10,如需要再次扩容，则扩容elementData为1.5倍。

底层源码(已注释)：

无参构造器：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

扩容：

 list.add(i);


public boolean add(E e) {
   //看看数组容量够不够，不够就扩容
   ensureCapacityInternal(size + 1);  // Increments modCount!!
   elementData[size++] = e;//将新元素添加到数组中
   return true;
}

//该方法用来确保数组容量够用，传入参数为所需要的最小容量，即数组中元素个数
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


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


private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判断是否为空数组
        return Math.max(DEFAULT_CAPACITY, minCapacity);//若为空则返回默认容量或最小容量哪个大设置哪个
    }
    return minCapacity;//数组不为空，返回最小容量
}


//用于记录该集合被修改的次数
protected transient int modCount = 0;


private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0){//如果最小容量大于当前容量
        //增加容量
        grow(minCapacity);
    }
}

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


//给数组扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    //原容量
    int oldCapacity = elementData.length;
    //设置新容量为原来的1.5倍
    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);
}


//大容量处理
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果所需最小容量大于最大数组容量，返回Integer的最大值，否则返回最大数组容量
    return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

3)如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

底层源码(已注释)：

有参构造器：

ArrayList list = new ArrayList(8);

private static final Object[] EMPTY_ELEMENTDATA = {};

//这是ArrayList的有参构造器，参数即为该集合的初始容量
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
//如果传入参数为0，设置elementData为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

（三）Vector

（1）Vector底层结构

1)Vector类的定义

public class Vector<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,Serializable

2)Vector底层也是一个对象数组，protected Object[] elementData;

3)Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

4)在开发中，需要线程同步安全时，考虑使用Vector 

5)如果无参构造器，默认容量为10，满后，就按2倍扩容。如果指定大小，则每次直接按两倍扩

底层源码(已注释)

//无参构造器
public Vector() {
    this(10);
}

//有参构造器，参数为初始容量
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//有参构造器。参数为初始容量和每次扩容的大小
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}



protected int capacityIncrement;

//该方法是扩容的核心方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //capacityIncrement可作为构造器的参数指定，默认为0，表示每次扩容的大小
    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);
}

（四）LinkedList

（1）LinkedList说明

1)LinkedList底层实现了双向链表和双端队列特点

2)可以添加任意元素(元素可以重复),包括null

3)线程不安全，没有实现同步

（2）LinkedList底层结构

1)LinkedList底层维护了一个双向链表.

2)LinkedList中维护了两个属性first和last分别指向首节点和尾节点

//指向头结点
transient Node<E> first;
//指向尾结点
transient Node<E> last;

3)每个节点(Node对象),里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

4)所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

底层源码(已注释)

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


void linkLast(E e) {
    //让l指向集合的尾部
    final Node<E> l = last;
    //创建一个新结点，内容为e，prev指向集合的尾部，next置空
    final Node<E> newNode = new Node<>(l, e, null);
    //让last指向新结点
    last = newNode;
    //如果集合的尾部为空，说明该集合没有元素，让first指向新结点
    if (l == null)
        first = newNode;
    else
    //不为空，则让集合尾部结点的next指向新结点
        l.next = newNode;
    size++;
    modCount++;
}

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

（五）Vector 和 ArrayList 的比较

（六）ArrayList 和 LinkedList 的比较

如何选择ArrayList和LinkedList:

1)如果我们改查的操作多，选择ArrayList

2)如果我们增删的操作多，选择LinkedList

3)一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList

4)在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList,也就是说，要根据业务来进行选择

3.Set

（一）Set接口

（1）介绍

1)无序(添加和取出的顺序不一致),没有索引。但是取出的顺序是固定的

2)不允许重复元素，所以最多包含一个null

3)JDK API中Set接口常用的实现类有：HashSet、LinkedHashSet、TreeSet

（2）Set接口的常用方法

Set 接口是 Collection 的子接口，因此，常用方法和 Collection 接口一样.

（3）Set 接口的遍历方式

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口。

1）可以使用迭代器

2）增强for

3）不能使用索引的方式来获取.

（二）HashSet

（1）HashSet说明

1)HashSet实现了Set接口

2)HashSet实际上是HashMap,源码如下

public HashSet() {
    map = new HashMap<>();
}

3)可以存放null值，但是只能有一个null

4)HashSet不保证元素是有序的，取决于hash后，再确定索引的结果.(即，不保证存放元素的顺序和取出顺序一致)，但是取出的顺序是固定的

5)不能有重复元素/对象.

（2）HashSet底层结构 

HashSet底层是HashMap,HashMap底层是(数组+链表+红黑树)

HashSet元素添加机制

1）添加一个元素时，先获取元素的哈希值(hashCode方法)

底层源码(已注释)

//创建一个HashsSet对象
HashSet hashSet = new HashSet();
//添加一个元素
hashSet.add("java");

//该属性没什么意义，主要起到占位的作用，该值为静态，被所有对象共享
private static final Object PRESENT = new Object();

//执行 add()
public boolean add(E e) {//e = "java"
return map.put(e, PRESENT)==null;
}

//执行map接口的put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//获取元素的hash值
static final int hash(Object key) {
    //存放hash值
    int h;
    //元素为null则返回0，不为空则调用hashCode()计算hash值
    //对hash值进行算术右移16位，再对这两个值进行按位异或，防止冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2）对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号

3）如果该位置上没有其他元素，则直接存放

4）如果该位置上已经有其他元素，则需要进行equals判断(String类重写的该方法比较的是类是否相等，其他对象也可通过重写该方法来确定判断标准)，如果相等，则不再添加。如果不相等，则以链表的方式添加。

底层源码(已注释)

transient Node<K,V>[] table;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;//定义辅助变量
    //判断数组是否为空，或者长度是否为0
    if ((tab = table) == null || (n = tab.length) == 0)
        //执行resize()方法，会返回一个初始化大小了的table表，默认长度16
        n = (tab = resize()).length;
    //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
    //并把这个位置的对象，赋给 p
    //(2)判断p 是否为null
    //(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
    //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
        Node<K,V> e; K k;
        //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
        //并且满足 下面两个条件之一:
        //(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
        //(2)  p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
        //就不能加入
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果相等，则不添加。
            e = p;
        //判断该结点是否是红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                //该if判断插入元素所在位置的单链表中p表示的结点后还有无结点，
                //若无则插入并退出循环，若有，则执行第二个if
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        //在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                        //, 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
                        //注意，在转成红黑树时，要进行判断, 判断条件
                        //if (tab == null || (n = tab.length) < 
                        //MIN_TREEIFY_CAPACITY(64))
                        //            resize();
                        //如果上面条件成立，先table扩容.
                        //只有上面条件不成立时，才进行转成红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                //该if语句判断p结点直接后继结点是否和要插入元素相同，若相同则退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //若不同，则执行p=e，让p表示该结点的后继结点
                p = e;
            }
        }
        if (e != null) { // 若e！=null为true，则表示存在相同的元素
            //将旧值替换成新值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            //添加失败，返回该元素的值
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        //只要加入结点的个数大于阈值，就会进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           

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

    Node(int hash, K key, V value, HashMap.Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

//阈值
int threshold;
static final int MAXIMUM_CAPACITY = 1 << 30;
//该常量表示table表的默认大小，数字1位左移四位，每移一位乘于2
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;

final HashMap.Node<K,V>[] resize() {
    //让oldTap指向table数组
    HashMap.Node<K,V>[] oldTab = table;
    //判断oldTap是否为空，若为空，把0赋给oldCap，若不为空，把oldTap的长度赋给oldCap
    //oldCap负责记录原容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //把阈值赋给oldThr，负责记录原阈值
    int oldThr = threshold;
    //定义newCap新容量，newThr新阈值，初始化为0
    int newCap, newThr = 0;
    if (oldCap > 0) {
        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
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //将默认大小赋给newCap
        newCap = DEFAULT_INITIAL_CAPACITY;
        //newThr是通过加载因子计算出来的临界值，当占用空间到达这个临界值，table表就会进行扩容
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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表newTab，大小为新容量newCap
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    //让table指向这个新表
    table = newTab;
    //如果原table表不等于空
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            HashMap.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 HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    HashMap.Node<K,V> loHead = null, loTail = null;
                    HashMap.Node<K,V> hiHead = null, hiTail = null;
                    HashMap.Node<K,V> next;
                    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;
}

HashSet的扩容和转成红黑树机制

1.HashSet底层是HashMap,第一次添加时，table数组扩容到16,临界值(threshold)是16*加载因子(loadFactor)是0.75=12

2.如果table数组使用到了临界值12,就会扩容到16*2=32,新的临界值就是32*0.75 =24,依次类推

3.在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)（table大小不满足会先对table进行扩容）,就会进行树化(红黑树),否则仍然采用数组扩容机制

（三）LinkedHashSet

（1）LinkedHashSet说明

1)LinkedHashSet是HashSet的子类

2)LinkedHashSet底层是一个LinkedHashMap(是HashMap的子类),底层维护了一个数组+双向链表

public LinkedHashSet() {
    //调用父类HashSet的构造器
    super(16, .75f, true);
}

HashSet(intinitialCapacity, float loadFactor, boolean dummy) {
    //底层是一个LinkedHashMap(是HashMap的子类)
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    //调用父类HashMap的构造器
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

3)LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。

4)LinkedHashSet不允许添重复元素

5)添加第一次时，直接将 数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry

6) 数组是 HashMap$Node[] 类型，存放的元素/数据是 LinkedHashMap$Entry类型

（2）LinkedHashSet底层结构

1)在LinkedHastSet中维护了一个hash表和双向键表(LinkedHashSet有head和tail)

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

2)每一个节点有before和after属性，这样可以形成双向链表

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

3)在添加一个元素时，先求hash值，在求索引，,确定该元素在table的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加（原则和hashset一样）

HashMap.Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

4)这样的话，我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致

（四）TreeSet

（1）TreeSet说明

1）当我们使用无参构造器，创建 TreeSet 时，默认按字符大小排序

2）想要进行排序，要使用 TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)并指定排序规则

TreeSet treeSet = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        //要求加入的元素，按照长度大小排序
        return ((String) o1).length() - ((String) o2).length();
    }
});

（2）TreeSet底层结构

1）构造器把传入的比较器对象，赋给了 TreeSet 的底层的 TreeMap 的属性 this.comparator

//TreeSet构造器调用的是TreeMap构造器
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
}

//TreeMap构造器
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
}

2）在 调用 treeSet.add("tom"), 在底层会执行到我们的匿名内部类(对象)

if (cpr != null) {//cpr 就是我们的匿名内部类(对象)
    do {
        parent = t;
        //动态绑定到我们的匿名内部类(对象)compare
        cmp = cpr.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else //如果相等，即返回 0,替换原先的值
        return t.setValue(value);
    } while (t != null);
}

三、Map

1.Map接口

（一）Map 接口实现类的特点

（1）用于保存具有映射关系的数据；Key-Value

（2）Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中

（3）Map中的key不允许重复，原因和HashSet一样.

（4）Map中的value可以重复

（5）Map的key可以为null,value也可以为null,注意key为null,只能有一个，value为null ,可以多个.

（6）常用String类作为Map的key

（7）key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value

（8）为了方便遍历，创建了Set接口的集合，集合名为EntrySet ，定义的类型是 Map.Entry，底层会把node结点转成Entry类型，再放到EntrySet集合中，因为HashMap$Node实现了Map.Entry接口

Map map = new HashMap();
map.put("no1", "小明");
map.put("no2", "张无忌");
map.put(new Car(), new Person());

//返回一个entrySet集合
Set set = map.entrySet();
System.out.println(set.getClass());// HashMap$EntrySet
for (Object obj : set) {
    //为了从 HashMap$Node 取出k-v
    //1. 先做一个向下转型
    Map.Entry entry = (Map.Entry) obj;
    System.out.println(entry.getKey() + "-" + entry.getValue() );
}

（二）Map 接口常用方法

（三）Map六大遍历方式

准备代码：

Map map = new HashMap();
map.put("邓超", "孙俪");
map.put("王宝强", "马蓉");
map.put("宋喆", "马蓉");
map.put("刘令博", null);
map.put(null, "刘亦菲");
map.put("鹿晗", "关晓彤");

（1）使用keySet()方法遍历

//第一组: 先取出 所有的Key , 通过Key 取出对应的Value
Set keyset = map.keySet();

1. 迭代器遍历

//迭代器
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
    Object key =  iterator.next();
    System.out.println(key + "-" + map.get(key));
} 

1. 增强for遍历

//增强for
for (Object key : keyset) {
    System.out.println(key + "-" + map.get(key));
}

（2）使用values()方法遍历

//把所有的values取出
Collection values = map.values();

1. 迭代器遍历

//迭代器
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
    Object value =  iterator2.next();
    System.out.println(value);
}

1. 增强for遍历

//增强for
for (Object value : values) {
    System.out.println(value);
}

（3）使用entrySey()方法遍历

//通过EntrySet 来获取 k-v
Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>

1. 迭代器遍历

//迭代器
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
    Object entry =  iterator3.next();
    //HashMap$Node -实现-> Map.Entry (getKey,getValue)
    //向下转型 Map.Entry
    Map.Entry m = (Map.Entry) entry;
    System.out.println(m.getKey() + "-" + m.getValue());
}

1. 增强for遍历

//增强for
for (Object entry : entrySet) {
    //将entry 转成 Map.Entry
    Map.Entry m = (Map.Entry) entry;
    System.out.println(m.getKey() + "-" + m.getValue());
}

2.HashMap

（一）HashMap说明

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

3)HashMap是以key-value对的方式来存储数据(HashMap$Node类型)

4)key不能重复，但是值可以重复，允许使用nul键和null值。

5)如果添加相同的key,则会覆盖原来的key-value,等同于修改.(key不会替换，value会替换)

6)与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的.(jdk8的hashMap底层数组+链表+红黑树)

7)HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized

（二）HashMap底层结构

扩容机制(和HashSet相同)

1)HashMap底层维护了Node类型的数组table,默认为null

2)当创建对象时，将加载因子(loadfactor)初始化为0.75.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

3)当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等，如果相等，则直接替换val;如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。

4)第1次添加，则需要扩容table容量为16,临界值(threshold)为12(16*0.75)

5)以后再扩容，则需要扩容table容量为原来的2倍(32),临界值为原来的2倍，即24,依次类推.

6)在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)

3.Hashtable

（一）Hashtable说明

1)存放的元素是键值对：即K-V

2)hashtable的键和值都不能为null,否则会抛出NullPointerException

3)hashTable使用方法基本上和HashMap—样

4)hashTable是线程安全的(synchronized),hashMap是线程不安全的

（二）Hashtable底层结构

1）底层有数组 Hashtable$Entry[] 初始化大小为 11

//Hashtable的构造器
public Hashtable() {
        this(11, 0.75f);
}

//Entry内部类
private static class Entry<K,V> implements Map.Entry<K,V>

2）临界值 threshold = 11 * 0.75（8）

扩容:

3）执行 方法 addEntry(hash, key, value, index); 添加K-V 封装到Entry

4）当 if (count >= threshold) 满足时，就进行扩容

5）按照 int newCapacity = (oldCapacity << 1) + 1; 的大小扩容.（即原先大小的两倍再加1）

4.HashMap和Hashtable对比

5.Properties

（一）Properties说明

（1）Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。

（2）Properties 继承 Hashtable，他的使用特点和Hashtable类似

（3）Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改

（4）工作后xxx.properties文件通常作为配置文件，这个知识点在IO流详解

7.TreeMap

（一）TreeMap说明

TreeMap treeMap = new TreeMap(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        //按照传入的 k(String) 的大小进行排序
        return ((String) o2).compareTo((String) o1);
    }
});

（二）TreeMap底层结构

（1）构造器把传入的实现了 Comparator接口的匿名内部类(对象)，传给给TreeMap的comparator

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

（2）调用put方法

2.1）第一次添加, 把k-v 封装到 Entry对象，放入root

Entry<K,V> t = root;
if (t == null) {
    compare(key, key); // 检查是否为空

    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
    return null;
}

2.2）以后添加

Comparator<? super K> cpr = comparator;
if (cpr != null) {
    do { //遍历所有的key , 给当前key找到适当位置
        parent = t;
        cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类的compare
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else  //如果遍历过程中，发现准备添加Key 和当前已有的Key 相等，会替换值，但不替换键
            return t.setValue(value);
    } while (t != null);
}

四、开发中如何选择集合实现类

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：

1. 先判断存储的类型(一组对象[单列]或一组键值对[双列])

2. 一组对象[单列]:Collection接口

        允许重复：List

                增删多：LinkedList [底层维护了一个双向链表]

                改查多：ArrayList [底层维护Object类型的可变数组]

        不允许重复：Set

                无序：HashSet[底层是HashMap,维护了一个哈希表即(数组+链表+红黑树)】

                排序：TreeSet

                插入和取出顺序一致：LinkedHashSet,维护数组+双向链表

3. 一组键值对[双列]:Map

        键无序：HashMap[底层是：哈希表jdk7:数组+链表，jdk8:数组+链表+红黑树]

        键排序：TreeMap

        键插入和取出顺序一致：LinkedHashMap

        读取文件Properties

五、Collections工具类

1.Collections 工具类介绍

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

（2）Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

2.排序操作：（均为 static 方法)

（1）reverse(List):反转List中元素的顺序

Collections.reverse(list);

（2）shuffle(List):对List集合元素进行随机排序

Collections.shuffle(list);

（3）sort(List):根据元素的自然顺序对指定List集合元素按升序排序

Collections.sort(list);

（4）sort(List,Comparator):根据指定的Comparator产生的顺序对List集合元素进行排序

//按照字符串的长度大小排序
Collections.sort(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
    //可以加入校验代码. 
    return ((String) o2).length() - ((String) o1).length();
    }
});

（5）swap(List,int,int):将指定list集合中的i处元素和j处元素进行交换

Collections.swap(list, 0, 1);

3.查找、替换

（1）Object max(Collection):根据元素的自然顺序，返回给定集合中的最大元素

Collections.max(list)

（2）Object max(Collection,Comparator):根据Comparator指定的顺序，返回给定集合中的最大元素

//比如，我们要返回长度最大的元素
Object maxObject = Collections.max(list, new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String)o1).length() - ((String)o2).length();
    }
});

（3）Object min(Collection):根据元素的自然顺序，返回给定集合中的最小元素

（4）Object min(Collection,Comparator):根据Comparator指定的顺序，返回给定集合中的最小元素

（5）int frequency(Collection,Object):返回指定集合中指定元素的出现次数

Collections.frequency(list, "tom")

（6）void copy(List dest,List src):将src中的内容复制到dest中，如果src的大小大于dest的大小会抛出数值越界的异常

Collections.copy(dest, list);

（7）boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List对象的所有旧值

Collections.replaceAll(list, "tom", "汤姆");