java集合总结

一、java集合框架图

二、总体分体

　　所有集合类都位于java.util包下。Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口

• List集合是有序集合，素可以重复，可以根据元素的索引来访问。
• Set集合是无序集合，元素不可以重复，元素本身来访问（也是集合里元素不允许重复的原因）。
• Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value

三、Collection接口

　　Collection接口是处理对象集合的根接口。Collection接口有两个主要的子接口List和Set，注意Map不是Collection的子接口，这个要牢记。

3.1List接口

　　List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。

　　实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

3.1.1ArrayList

• ArrayList擅长于随机访问。同时ArrayList是非同步的。　
• ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长。
• ArrayList不是线程安全的，只能用在单线程环境下。
• 实现了Serializable接口，因此它支持序列化，能够通过序列化传输；
• 实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问；
• 实现了Cloneable接口，能被克隆。　

　　ArrayList的add()方法详解：

1. public boolean add(E e)

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;    //size是ArrayList私有变量，记录数组大小
        return true;
}

解读：

• 首先确认在数组元素加一后，容量是否能保证。
• 之后向数组中最后一个元素的下一个位置放置新的元素。

2.public void add(int index, E element)

public void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
}

解读：

• 首先判断使用者所想插入的位置index是否合法　　

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

• 但凡未落在数组容量之内的位置都将抛出，索引越界异常。
• 之后再判断，插入元素后数组容量是否能保证。
• 然后把索引位置及其索引之后的元素都往后移动。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

arraycopy一个本地方法，意味着它底层并非java代码实现。

参数意义为：

src	srcPos	dest	destPos	length
原数组src	从原数组src的srcPos位置开始的	复制到dest数组	dest数组的destPos位置	想被复制的个数

  

　　ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量10（必须调用一次add方法后），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

　　retainAll可以用来取集合的交集，而removeAll可以用取集合的差集。

　　注：方法进行判断的时候是会调用equals方法的，所以如果集合中为Object，那么一定要小心处理hashCode和equals了。

　　扩容机制：

　　阅读JDK1.8源码，通过无参构造方法初始容量默认为0，只有第一次真正调用add()方法才会创建，默认大小为10的数组。（之前版本的JDK不是这样处理的）

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

    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方法用于扩充，oldCapacity + (oldCapacity >> 1)相当于每次按照1.5倍（位运算）的比率通过copeOf的方式扩容。

也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15

3.1.2LinkedList

• ArrayList是一个动态数组，而LinkedList是一个双向链表
• LinkedList不能随机访问，允许包括null值
• LinkedList也是非同步的

　　双向链表的get方法访问，每次会判断索引在链表的前半部分还是后半部分，在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端开始遍历）。

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

　　源码解析：　

　　1.结点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;
        }
}

　　2.LinkedList类结构

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包含了三个重要的对象：first、last 和 size。

• first 是双向链表的表头，它是双向链表节点所对应的类Node的实例
• last 是双向链表的最后一个元素表尾，它是双向链表节点所对应的类Node的实例
• size 是双向链表中节点的个数。

　　3.查找元素

//返回指定索引位置的节点
Node<E> node(int index) {
        // assert isElementIndex(index);
        //折半思想，当index < size/2时，从列表首节点向后查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  //当index >= size/2时，从列表尾节点向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}

　　我们看到这里有一个加速动作。 源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果 index>size/2，就从末尾往前遍历到位置index处。这样可以减少一部分不必要的遍历。

3.1.3Vector

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

3.1.4Stack

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

3.2Set接口

　　Set是一种不包含重复的元素的Collection，无序，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。需要注意的是:虽然Set中元素没有顺序，但是元素在set中的位置是由该元素的HashCode决定的，其具体位置其实是固定的。

　　Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

　　set接口判断元素是否重复，用的是e1.equals(e2)进行比较,而不是

　　为了更好地理解，请看下面的例子：

public class TestSet {
    
    public static void main(String[] args){
        
        Set<String> books = new HashSet<String>();
        //添加一个字符串对象
        books.add(new String("我是字符串"));
        
        //再次添加一个字符串对象，
        //因为两个字符串对象通过equals方法比较相等，所以添加失败，返回false
        boolean result = books.add(new String("我是字符串"));
        
        System.out.println(result);
        
        System.out.println(books);    

    }
}

运行结果：

false
[我是字符串]

　　说明：集合两次添加的字符串对象明显不是一个对象（程序通过new关键字来创建字符串对象），当使用==运算符判断返回false，使用equals方法比较返回true，所以不能添加到Set集合中，最后只能输出一个元素。　

　　Java hashCode() 和 equals()的若干问题解答https://www.cnblogs.com/skywang12345/p/3324958.html

3.2.1HashSet

• HashSet 是一个没有重复元素，无序，线程不安全的集合。它是由HashMap实现的，
• HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。
• HashSet的实现方式大致如下，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象。

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

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

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

HashSet使用和理解中容易出现的误区:

（1）a.HashSet中存放null值
  　　HashSet中是允许存入null值的，但是在HashSet中仅仅能够存入一个null值。

（2）b.HashSet中存储元素的位置是固定的
 　　 HashSet中存储的元素的是无序的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的。

3.2.2LinkedHashSet

　　LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

3.2.3TreeSet

　　TreeSet是一个有序集合，其底层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法。

　　注意：TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

四、Map接口

　　Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。

4.1HashMap

• JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
• 构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时

　　首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

　　当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

　　即HashMap的原理图是：

JDK1.8中HashMap的涉及到的数据结构

1，位桶数组

transient Node<k,v>[] table;//存储（位桶）的数组</k,v> 

2，数组元素Node<K,V>实现了Entry接口

// 静态内部类、操纵了 Map 接口中的 Entry<K,V> 接口
static class Node<K,V> implements Map.Entry<K,V> {
    // key 所产生的 hash 值 （不变）
    final int hash;
    // key （不变）
    final K key;
    // value
    V value;
    // 指向下一个 Node 节点、（链地址法解决冲突）
    Node<K,V> next;

    // 构造函数
    Node(int hash, K key, V value, 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; }

    // 计算 key 所产生的 hash 码
    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;
        // 是否都操作 Map.Entry 接口
        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;
    }
}

　　在这里我们需要注意：

• Node 的实现是一个静态内部类
• hash 值与 key 的不变性：即使在 HashMap 中对 key 及 hash 做了final 关键字的约束，但是我们还是需要注意，最好使用不变对象作为 key。

　　首先我们来了解一下 final 关键字在基本类型与引用类型的使用上有什么不同？

• 当 final 修饰基本变量类型时，不能对基本类型变量重新赋值，因此基本类型变量不能被改变。
• 当 final 修饰引用类型变量时，final 只保证这个引用类型变量所引用的地址不会改变，即一直引用同一个对象，但是这个对象(对象的非 final 成员变量的值可以改变)完全可以发生改变。

　　怎么解决？

• 在 HashMap 中，尽量使用 String、Integer 等不可变类型用作 key。
• 重写自定义类的 hashcode 方法，保证在成员变量改变的同时该对象的哈希值不变即可。

　　参考：https://blog.csdn.net/championhengyi/article/details/80024624

3，红黑树

//红黑树  
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {  
    TreeNode<k,v> parent;  // 父节点  
    TreeNode<k,v> left; //左子树  
    TreeNode<k,v> right;//右子树  
    TreeNode<k,v> prev;    // needed to unlink next upon deletion  
    boolean red;    //颜色属性  
    TreeNode(int hash, K key, V val, Node<k,v> next) {  
        super(hash, key, val, next);  
    }  
   
    //返回当前节点的根节点  
    final TreeNode<k,v> root() {  
        for (TreeNode<k,v> r = this, p;;) {  
            if ((p = r.parent) == null)  
                return r;  
            r = p;  
        }  
}

4，数据域

public c
lass HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {  
    private static final long serialVersionUID = 362498820763181265L;  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比  
    //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树  
    static final int TREEIFY_THRESHOLD = 8;  
    static final int UNTREEIFY_THRESHOLD = 6;  
    static final int MIN_TREEIFY_CAPACITY = 64;  
    transient Node<k,v>[] table;//存储元素的数组  transient 关键字：阻止本字段进行序列化
    transient Set<map.entry<k,v>> entrySet;  
    transient int size;//存放元素的个数  
    transient int modCount;//被修改的次数fast-fail机制  
    int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容   
    final float loadFactor;//填充比（......后面略）
}

　　加载因子（默认0.75）HashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。

5、put方法

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

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

　　key 的 hash 值就是这样得到的，key.hashCode()是一个本地方法，具体实现在源码中并没有给出，但这并不是重点，我们需要注意的是在计算出 hash 值后，它又与本身的高 16 位进行了异或。（hash 值本身是 32 位）

　　这样做的好处是什么呢？

主要是从速度、功效、质量来考虑的，这么做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低 Bit 都参与到 Hash 的计算中，同时不会有太大的开销。在混合了原始 hashCode 值的高位和低位后，加大了低位的随机性，而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来，这就使得 hash 方法返回的值，具有更高的随机性，减少了冲突。

putVal 方法源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 哈希表为null || 哈希表的长度为 0（resize 也是一个经典的方法）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // (n - 1) & hash 计算出 key 在哈希表中应该存储的位置（除留余数法，使用 & 运算 比 % 运算更快）
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;

        // 插入的 key 在 HashMap 中已经存在（之后进行 value 的直接覆盖）
        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 ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);

                    // 当处理冲突的链节点数大于等于 8 的时候，转换红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }

                // 插入的 key 在 HashMap 中已经存在
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // key 已经存在，直接覆盖旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;                 // 记录 HashMap 内部结构发生变化的次数，用于快速失败机制
    if (++size > threshold)
        resize();               // 扩容

    afterNodeInsertion(evict);  // 作用不明确

    return null;
}

 　　put 方法的执行流程做一个总结

1.判断键值对数组 table 是否为空或为 null，否则执行 resize() 进行扩容；
2.根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i] == null，直接新建节点添加，转向 6，如果 table[i] 不为空，转向 3；
3.判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向 4，这里的相同指的是 hashCode 以及 equals；
4.判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 5；
5.遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key     已经存在直接覆盖 value 即可；
6.插入成功后，判断实际存在的键值对数量 size 是否超过了负载 threshold，如果超过，进行扩容。

索引定位(n - 1) & hash

　　这种方法有一个前提，就是哈希表 table 的长度 n 必须满足 2 幂次方。

　　HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；

　　这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，hash%length==hash&(length-1)的前提是length是2的n次方；

　　为什么这样能均匀分布减少碰撞呢？

　　2的n次方实际就是1后面n个0，2的n次方-1  实际就是n个1；
　　例如长度为9时候，3&(9-1)=0  2&(9-1)=0 ，都在0上，碰撞了；
　　例如长度为8时候，3&(8-1)=3  2&(8-1)=2 ，不同位置上，不碰撞；

参考：https://blog.csdn.net/championhengyi/article/details/80024624

6，HasMap的扩容机制resize();

　　构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时

 final Node<K,V>[] resize() {  
       Node<K,V>[] oldTab = table;  
       int oldCap = (oldTab == null) ? 0 : oldTab.length;  
       int oldThr = threshold;  
       int newCap, newThr = 0;  
      
/*如果旧表的长度不是空*/  
       if (oldCap > 0) {  
           if (oldCap >= MAXIMUM_CAPACITY) {  
               threshold = Integer.MAX_VALUE;  
               return oldTab;  
           }  
/*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/  
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                    oldCap >= DEFAULT_INITIAL_CAPACITY)  
      /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/  
               newThr = oldThr << 1; // double threshold  
       }  
    /*如果旧表的长度的是0，就是说第一次初始化表*/  
       else if (oldThr > 0) // initial capacity was placed in threshold  
           newCap = oldThr;  
       else {               // zero initial threshold signifies using defaults  
           newCap = DEFAULT_INITIAL_CAPACITY;  
           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"})  
/*下面开始构造新表，初始化表中的数据*/  
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
       table = newTab;//把新表赋值给table  
       if (oldTab != null) {//原表不是空要把原表中数据移动到新表中      
           /*遍历原来的旧表*/        
           for (int j = 0; j < oldCap; ++j) {  
               Node<K,V> e;  
               if ((e = oldTab[j]) != null) {  
                   oldTab[j] = null;  
                   if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  
                       newTab[e.hash & (newCap - 1)] = e;  
                   else if (e instanceof TreeNode)  
                       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
/*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/  
                   else { // preserve order保证顺序  
                ////新计算在新表的位置，并进行搬运  
                       Node<K,V> loHead = null, loTail = null;  
                       Node<K,V> hiHead = null, hiTail = null;  
                       Node<K,V> next;  
                      
                       do {  
                           next = e.next;//记录下一个结点  
          //新表是旧表的两倍容量，实例上就把单链表拆分为两队，  
　　　　　　　　　　　　　//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对  
                           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) {//lo队不为null，放在新表原位置  
                           loTail.next = null;  
                           newTab[j] = loHead;  
                       }  
                       if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置  
                           hiTail.next = null;  
                           newTab[j + oldCap] = hiHead;  
                       }  
                   }  
               }  
           }  
       }  
       return newTab;  
   }

7，红黑树的改进

　　在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）

　　红黑树图解参考：http://m.sohu.com/a/201923614_466939

8，HashMap的遍历

public static void main(String[] args) {
  Map<String,String> map=new HashMap<String,String>();
        map.put("1", "value1");
        map.put("2", "value2");
        map.put("3", "value3");
        map.put("4", "value4");
        
        //第一种：普通使用，二次取值
        System.out.println("
通过Map.keySet遍历key和value：");  
        for(String key:map.keySet())
        {
         System.out.println("Key: "+key+" Value: "+map.get(key));
        }
        
        //第二种
        System.out.println("
通过Map.entrySet使用iterator遍历key和value: ");  
        Iterator map1it=map.entrySet().iterator();
        while(map1it.hasNext())
        {
         Map.Entry<String, String> entry=(Entry<String, String>) map1it.next();
         System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
        }
        
        //第三种：推荐，尤其是容量大时  
        System.out.println("
通过Map.entrySet遍历key和value");  
        for(Map.Entry<String, String> entry: map.entrySet())
        {
         System.out.println("Key: "+ entry.getKey()+ " Value: "+entry.getValue());
        }
        
 }

4.2HashTable

　　HashTable同样是基于哈希表实现的，其实类似HashMap，只不过有些区别，HashTable同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

　　HashTable比较古老， 是JDK1.0就引入的类，而HashMap 是 1.2 引进的 Map 的一个实现。

　　HashTable 是线程安全的，能用于多线程环境中。Hashtable同样也实现了Serializable接口，支持序列化，也实现了Cloneable接口，能被克

　　Hashtable继承于Dictionary类，实现了Map接口。Dictionary是声明了操作"键值对"函数接口的抽象类。 有一点注意，HashTable除了线程安全之外（其实是直接在方法上增加了synchronized关键字，比较古老，落后，低效的同步方式），还有就是它的key、value都不为null。另外Hashtable 也有 初始容量 和 加载因子。

public Hashtable() {
        this(11, 0.75f);
    }

　　默认加载因子也是 0.75，HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。因为HashTable是直接使用除留余数法定位地址。且Hashtable计算hash值，直接用key的hashCode()。

　　还要注意：前面说了Hashtable中key和value都不允许为null，而HashMap中key和value都允许为null（key只能有一个为null，而value则可以有多个为null）。但如在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。

　　最后针对扩容：Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。

4.3LinkedHashMap

　　LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
　　LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
　　根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。
　　注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
　　由于LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

　　LinkedHashMap构造函数

LinkedHashMap<String, String> map = new LinkedHashMap<>(16,0.75f,true);

　　说明：16为初始容量，0.75f为加载因子，true为按访问顺序，默认无参构造false插入排序

4.4TreeMap　

　　TreeMap 是一个有序的key-value集合，非同步，基于红黑树（Red-Black tree）实现，每一个key-value节点作为红黑树的一个节点。TreeMap存储时会进行排序的，会根据key来对key-value键值对进行排序，其中排序方式也是分为两种，一种是自然排序，一种是定制排序，具体取决于使用的构造方法。

　　自然排序：TreeMap中所有的key必须实现Comparable接口，并且所有的key都应该是同一个类的对象，否则会报ClassCastException异常。

　　定制排序：定义TreeMap时，创建一个comparator对象，该对象对所有的treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口。

　　TreeMap判断两个元素相等的标准：两个key通过compareTo()方法返回0，则认为这两个key相等。

　　如果使用自定义的类来作为TreeMap中的key值，且想让TreeMap能够良好的工作，则必须重写自定义类中的equals()方法，TreeMap中判断相等的标准是：两个key通过equals()方法返回为true，并且通过compareTo()方法比较应该返回为0。

五、Iterator 与 ListIterator详解

　　我们在平常经常会使用到foreach，for关键字，其实他们的内部原理使用的都是Iterator迭代器的原理。
但是在使用的时候需要注意的是，如果在遍历的过程中增加元素、删除元素等改变了List、HashMap之类的List的结构时，会产生ConcurrentModificationException（并发修改）异常。

Iterator.

next()方法最终会执行到nextEntry()方法。看一下nextEntry()方法的实现：

final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    HashMapEntry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();

    if ((next = e.next) == null) {
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
            ;
    }
    current = e;
    return e;
}

　　可以看到抛出异常的原因是modCount != expectedModCount。modCount是HashMap中的一个变量，当HashMap结构改变时（比如put进去了一个新的元素，删除了一个新的元素等），这个modCount记录的是改变的次数，而expectedModCount是HashIterator类对象的一个变量，在HashIterator构造函数中赋值，如下所示：

HashIterator() {
    expectedModCount = modCount;
    if (size > 0) { // advance to first entry
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
            ;
    }
}

　　上面的expectedModCount = modCount即为赋值语句。
返回上面举的例子，当我们在遍历HashMap时删除了一个元素，即map.remove(key); 最终执行removeEntryForKey(key)方法，在该方法中执行了modCount++，也即modCount的值改变了。当在HashIterator中继续往下执行到nextEntry()方法时，由于modCount的值不等于expectedModCount，那么就抛出了ConcurrentModificationException异常。

参考：https://www.jianshu.com/p/f9f8dd129b41

5.1.Iterator

Iterator的定义如下：

public interface Iterator<E> {}

Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。Iterator提供的API接口如下：

boolean hasNext()：判断集合里是否存在下一个元素。如果有，hasNext()方法返回 true。
Object next()：返回集合里下一个元素。
void remove()：删除集合里上一次next方法返回的元素。

使用示例：

public class IteratorExample {
    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<String>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        Iterator<String> it = a.iterator();
        while (it.hasNext()) {
            String t = it.next();
            if ("bbb".equals(t)) {
                it.remove();
            }
        }
        System.out.println("After iterate : " + a);
    }
} 

输出结果如下：

Before iterate : [aaa, bbb, ccc]
After iterate : [aaa, ccc] 

注意：

（1）Iterator只能单向移动。

（2）Iterator.remove()是唯一安全的方式来在迭代过程中修改集合；如果在迭代过程中以任何其它的方式修改了基本集合将会产生未知的行为。而且每调用一次next()方法，remove()方法只能被调用一次，如果违反这个规则将抛出一个异常。

　　快速失败(fail-fast)和安全失败(fail-safe)的区别https://www.cnblogs.com/shamo89/p/6685216.html

5.2.ListIterator

ListIterator是一个功能更加强大的迭代器, 它继承于Iterator接口,只能用于各种List类型的访问。可以通过调用listIterator()方法产生一个指向List开始处的ListIterator, 还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator.

ListIterator接口定义如下:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
 
    E next();
 
    boolean hasPrevious();
 
    E previous();
 
    int nextIndex();
 
    int previousIndex();
 
    void remove();
 
    void set(E e);
 
    void add(E e);
     
} 

由以上定义我们可以推出ListIterator可以:

(1)双向移动（向前/向后遍历）.

(2)产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引.

(3)可以使用set()方法替换它访问过的最后一个元素.

(4)可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一个元素.

使用示例：

public class ListIteratorExample {
 
    public static void main(String[] args) {
        ArrayList<String> a = new ArrayList<String>();
        a.add("aaa");
        a.add("bbb");
        a.add("ccc");
        System.out.println("Before iterate : " + a);
        ListIterator<String> it = a.listIterator();
        while (it.hasNext()) {
            System.out.println(it.next() + ", " + it.previousIndex() + ", " + it.nextIndex());
        }
        while (it.hasPrevious()) {
            System.out.print(it.previous() + " ");
        }
        System.out.println();
        it = a.listIterator(1);
        while (it.hasNext()) {
            String t = it.next();
            System.out.println(t);
            if ("ccc".equals(t)) {
                it.set("nnn");
            } else {
                it.add("kkk");
            }
        }
        System.out.println("After iterate : " + a);
    }
} 

输出结果如下：

Before iterate : [aaa, bbb, ccc]
aaa, 0, 1
bbb, 1, 2
ccc, 2, 3
ccc bbb aaa 
bbb
ccc
After iterate : [aaa, bbb, kkk, nnn]

 六、Collection 和 Collections区别

6.1Collection

　　java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。

6.2Collections 

　　java.util.Collections 是一个包装类（工具类/帮助类）。它包含各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，用于对集合中元素进行排序、搜索以及线程安全等各种操作，服务于Java的Collection框架。

代码示例：

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 
  
public class TestCollections { 
      
    public static void main(String args[]) { 
        //注意List是实现Collection接口的 
        List list = new ArrayList(); 
        double array[] = { 112, 111, 23, 456, 231 }; 
        for (int i = 0; i < array.length; i++) { 
            list.add(new Double(array[i])); 
        } 
        Collections.sort(list); 
        for (int i = 0; i < array.length; i++) { 
            System.out.println(list.get(i)); 
        } 
        // 结果：23.0 111.0 112.0 231.0 456.0 
    } 
} 

参考https://www.cnblogs.com/xiaoxi/p/6089984.html

　　https://www.cnblogs.com/little-fly/p/7344285.html

　　https://www.cnblogs.com/kubixuesheng/p/6144535.html