Java中的容器（集合）

1、Java常用容器：List，Set，Map

List：

继承了Collection接口（public interface List<E> extends Collection<E> ），有序且允许出现重复值。

Set：

继承了Collection接口（public interface Set<E> extends Collection<E> ），无序且不允许出现重复值。

Map：

是一个使用键值对存储的容器（public interface Map<K,V> ）。

2、Collection 和 Collections 的区别

Collection：

Collection是一个集合类的通用接口（源码：public interface Collection<E> extends Iterable<E>）。
通过查看源码可以发现，其中包含的都是一些通用的集合操作接口，他的直接继承接口有List和Set。

Collections：

Collections是一个集合工具类（源码：public class Collections）。
其中提供一系列对集合操作的静态方法，比如排序：sort()，集合安全：synchronizedCollection()，反转：reverse()等等。

3、ArrayList 和 LinkedList 的区别

ArrayList：

底层数据结构是一个数组，查询效率比较高，添加删除较慢（默认添加在末尾，在指定位置添加元素效率比较低，因为需要将指定位置后续的元素都往后移位）。

LinkedList：

底层数据结构是一个双向链表（prev指向前节点，next指向后节点），查询效率比较慢，添加删除比较快。

4、ArrayList 和 Vector 的区别

ArrayList：

非线程安全，读取效率较高。

Vector：

线程安全（源码中显示该类的方法使用了synchronized），读取效率较低（推荐使用CopyOnWriteArrayList,该类适合读多写少的场景）。

5、HashMap 和 Hashtable 的区别

HashMap：

非线程安全，允许空键值，执行效率相对较高（底层使用的数据结构是数组+链表+红黑树（jdk8）或者数组+链表（jdk7））。

Hashtable：

线程安全，不允许空键值，执行效率相对较低（推荐使用ConcurrentHashMap）。

6、HashMap 和 TreeMap 的使用场景

HashMap：

一般情况下进行插入，删除，定位元素的话，使用HashMap（常用）。

TreeMap：

如果需要使用有序的集合，推荐用TreeMap。

7、HashMap 实现原理

以put操作为例：

首先会根据key的hashCode得到hash值（部分源码：return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)），依据hash值得到该元素在数组的位置（下标），如果该位置不存在元素，则将该元素直接放入此位置上；否则判断元素是否相等，如果是，则覆盖，否则使用拉链法解决冲突（创建一个链表，先加入的放到链头，后加入的放在链尾（JDK8，JDK7插入是插到了链头），超过8位时，使用红黑树存储）。
放入的元素是包含了键值对的元素，而非仅仅只有值。

8、HashSet 实现原理

以add操作为例：

进入add源码（return map.put(e, PRESENT)==null），可以看到其底层是用map来实现的，只是传入的值当做了map的key，而map的value使用的是统一的PRESENT。

9、迭代器：Iterator

Iterator：

是一个轻量级的对象（创建代价小），主要用来对集合进行遍历移除等操作。
示例代码如下

package com.spring.test.service.demo;

import java.util.*;

/**

 * @Author: philosopherZB

 * @Date: 2019/10/1

 */

public class Demo {

    public static void main(String[] args){

        List<String> list = new ArrayList<>(5);

        for(int i=0;i<5;i++){

            list.add("Test" + i);

            System.out.println("输入：Test" + i);

        }

        //利用iterator()返回一个Iterator对象

        Iterator<String> it = list.iterator();

        //判断是否还存在元素

        while(it.hasNext()){

            //第一次调用next()会返回集合中的第一个元素，之后返回下一个

            String s = it.next();

            if("Test3".equals(s))

                //移除某个元素

                it.remove();

        }

        list.forEach(l->{

            System.out.println(l);

        });

    }

}

10、ArrayList 扩容源码解析（JDK8）

源码解析：

首先我们使用 ArrayList<String> list = new ArrayList<>(5)创建一个ArrayLsit，这表明创建的ArrayList初始容量为5.
源码如下：

    //默认初始容量10

    private static final int DEFAULT_CAPACITY = 10;

    //一个空的默认对象数组，当ArrayList(int initialCapacity)，ArrayList(Collection<? extends E> c)中的容量等于0的时候使用

    private static final Object[] EMPTY_ELEMENTDATA = {};

    //一个空的默认对象数组，用于ArrayList()构造器

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //一个对象数组，transient表示不能序列化

    transient Object[] elementData;

    //数组大小

    private int size;

    //以传入的容量构造一个空的list

    public ArrayList(int initialCapacity) {

        //如果传入值大于0，则创建一个该容量大小的数组。

        if (initialCapacity > 0) {

            this.elementData = new Object[initialCapacity];

        } else if (initialCapacity == 0) {

            //否则如果传入值等于0，则创建默认空数组

            this.elementData = EMPTY_ELEMENTDATA;

        } else {

            //如果小于0则抛出异常

            throw new IllegalArgumentException("Illegal Capacity: "+

                    initialCapacity);

        }

    }

接着我们使用add方法添加一个字符串到该list中，list.add("Test")。进入add源码会发现，真正的扩容是发生在add操作之前的。
源码如下：

    //默认添加在数组末尾

    public boolean add(E e) {

        //添加之前先确认是否需要扩容

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        //新加入的元素是添加在了数组的末尾，随后数组size自增。

        elementData[size++] = e;

        return true;

    }

进入ensureCapacityInternal()方法查看对应源码如下：

    private void ensureCapacityInternal(int minCapacity) {

        //先通过calculateCapacity方法计算最终容量，以确认实际容量

        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    }

到这一步，我们需要先进入calculateCapacity()方法看看他是如何计算最后容量的，源码如下：

    private static int calculateCapacity(Object[] elementData, int minCapacity) {

        //如果elementData为默认空数组，则比较传入值与默认值（10），返回两者中的较大值

        //elementData为默认空数组指的是通过ArrayList()这个构造器创建的ArrayList对象

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            return Math.max(DEFAULT_CAPACITY, minCapacity);

        }

        //返回传入值

        return minCapacity;

    }

现在我们确认了最终容量，那么进入ensureExplicitCapacity，查看源码如下：

    private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        // overflow-conscious code

        //如果最终确认容量大于数组容量，则进行grow()扩容

        if (minCapacity - elementData.length > 0)

            grow(minCapacity);

    }

可以看到，只有当最终容量大于数组容量时才会进行扩容。那么以我们上面的例子而言具体分析如下：
首先因为我们创建的时候就赋了初始容量5，所以elementData.length = 5。
当我们add第一个元素的时候，minCapacity是等于size + 1 = 1的。
此时minCapacity - elementData.length > 0条件不成立，所以不会进入grow(minCapacity)方法进行扩容。
以此类推，只有添加到第五个元素的时候，minCapacity = 6 大于 elementData.length = 5，这时就会进入grow(minCapacity)方法进行扩容。
grow()以及hugeCapacity()源码如下：

    //可分配的最大数组大小

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //扩容

    private void grow(int minCapacity) {

        // overflow-conscious code

        //oldCapacity表示旧容量

        int oldCapacity = elementData.length;

        //newCapacity表示新容量，计算规则为旧容量+旧容量的0.5，即旧容量的1.5倍。如果超过int的最大值会返回一个负数。

        //oldCapacity >> 1表示右移一位，对应除以2的1次方。

        int newCapacity = oldCapacity + (oldCapacity >> 1);

        //如果新容量小于最小容量，则将最小容量赋值给新容量(有时手动扩容可能也会返回<0，对应方法为ensureCapacity())

        if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

        //如果新容量大于MAX_ARRAY_SIZE，则执行hugeCapacity(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) {

        //如果最小容量超过了int的最大值，minCapacity会是一个负数，此时抛出内存溢出错误

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        //比较最小容量是否大于MAX_ARRAY_SIZE，如果是则返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE

        return (minCapacity > MAX_ARRAY_SIZE) ?

                Integer.MAX_VALUE :

                MAX_ARRAY_SIZE;

    }

（以上所有内容皆为个人笔记，如有错误之处还望指正。）

巴特西