面试-Java集合

推荐：韩顺平、黑马

1. Java框架体系

2. 数组

• 数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。
• 数组获取其他元素的地址值：a[i] = baseAddress + i * dataTypeSize
  • baseAddress： 数组的首地址
  • dataTypeSize：代表数组中元素类型的大小
• 如果数组的索引从1开始，寻址公式中，就需要增加一次减法操作，对于CPU来说就多了一次指令，性能不高。
• 查询时间复杂度：
  • 根据索引查询：数组元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素，O(1)
  • 未给索引查询：挨个遍历：O(n)或二分：O(logn)
• 插入删除时间复杂度：
  • 数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。需要不挺的挪动元素。
  • 最好情况下是O(1)的，最坏情况下是O(n)的，平均情况下的时间复杂度是O(n)。

3. List

3.1 底层原理

• 底层数据结构：ArrayList底层是用动态的数组实现的

• 初始容量：ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10

• 扩容逻辑：ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组

• 添加逻辑：

  • 确保数组已使用长度（size）加1之后足够存下下一个数据
  • 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）
  • 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
  • 返回添加成功布尔值。

• 成员变量

  /**
  * 默认初始的容量(CAPACITY)
  */
  private static final int DEFAULT_CAPACITY = 10;
  
  /**
  * 用于空实例的共享空数组实例
  */
  private static final Object[] EMPTY_ELEMENTDATA = {};
  
  /**
  * 用于默认大小的空实例的共享空数组实例。
  * 我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
  */
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
  /**
  * 存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。
  * 当添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList
  * 都将扩展为 DEFAULT_CAPACITY
  * 当前对象不参与序列化
  */
  transient Object[] elementData; 
  
  /**
  * ArrayList 的大小（它包含的元素数量）
  */
  private int size;

3.1.1 初始化

List list = new ArrayList();
List list = new ArrayList(2);
//-------------
//源码
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);
    }
}

// 将collection对象转换成数组，然后将数组的地址的赋给elementData
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;
    }
}

3.1.2 第一次添加

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

• 在第一次添加的时候，此时elementData就是一个空集合，首先就会进入grow方法
• 此时就会创建一个大小为10的object数组
• 并且将object[0]分给当前元素进行存储。
• size+1

3.1.3 第二次至第十次添加数据

• 此时因此size > 0且不等于elementData.length，因此直接可以添加数据，而不会进行扩容

• 当第十次添加数据的时候，s为9，那么还是可以正常添加的，当添加完成之后，size为10

3.1.5 第十一次添加

• 此时s为10，和elementData.length，此时进行扩容
• 数组长度变为原来的1.5倍，然后进行数据拷贝

3.1.6 扩容

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, 
                oldCapacity >> 1; // 增加原来容量的1.5倍
        return elementData = Arrays.copyOf(elementData, newCapacity); //数组拷贝
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

3.2 ArrayList list=new ArrayList(10)中的list扩容几次

• 该语句只是声明和实例了一个 ArrayList，指定了容量为 10，未扩容

3.3 如何实现数组和List之间的转换

• 数组转List ，使用JDK中java.util.Arrays工具类的asList方法

• List转数组，使用List的toArray方法。无参toArray方法返回 Object数组，传入初始化长度的数组对象，返回该对象数组

• 用Arrays.asList转List后，如果修改了数组内容，list受影响吗

  • Arrays.asList转换list之后，如果修改了数组的内容，list会受影响；因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }
    
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;
    
        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }
    }
    
    public static <T> T requireNonNull(T obj) {
        if (obj == null)
            throw new NullPointerException();
        return obj;
    }

    根据源码看出，最后只是把数组的引用复制给了新构建的list，因此修改了数组中的内容会改变list的内容

• List用toArray转数组后，如果修改了List内容，数组受影响吗

  • list用了toArray转数组后，如果修改了list内容，数组不会影响;当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    根据源码看出，实际调用的是一个copyOf方法，最后是两个不同的内存地址

3.4 ArrayList和LinkedList的区别是什么？

3.4.1 链表

• 单向链表：

  • 查询：

    • 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)
    • 查询其他结点需要遍历链表，时间复杂度是O(n)

  • 插入和删除：

    • 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)
    • 查询其他结点需要遍历链表，时间复杂度是O(n)

• 双向链表：

  • 查询：
    • 查询头尾结点的时间复杂度是O(1)
    • 平均的查询时间复杂度是O(n)
    • 给定节点找前驱节点的时间复杂度为O(1)
  • 插入和删除：
    • 头尾结点增删的时间复杂度为O(1)
    • 其他部分结点增删的时间复杂度是 O(n)
    • 给定节点增删的时间复杂度为O(1)

• 总结：单向链表：头O(1),其他O(n)；双向链表：头尾O(1),其他O(n),给定节点O(1)

3.4.2 区别：

• 底层数据结构：
  • ArrayList 是动态数组的数据结构实现
  • LinkedList 是双向链表的数据结构实现
• 操作数据效率：
  • ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】， LinkedList不支持下标查询
  • 查找（未知索引）： ArrayList需要遍历，链表也需要遍历，时间复杂度都是O(n)
  • 插入和删除：
    • ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
    • LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)
• 内存空间占用：
  • ArrayList底层是数组，内存连续，节省内存
  • LinkedList 是双向链表需要存储数据，和两个指针，更占用内存
• 线程安全：
  • ArrayList和LinkedList都不是线程安全的
  • 如果需要保证线程安全，有两种方案：
    • 在方法内使用，局部变量则是线程安全的
    • 使用线程安全的ArrayList和LinkedList

4. HashMap

4.1 二叉搜索树

• 二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型
• 二叉搜索树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值
• 
• 插入，查找，删除的时间复杂度O(logn)，即：每次都是二分查找的
• 极端情况下二叉查找树已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是O(n)。

4.3 红黑树

• 红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

• 

• 性质：

  • 节点要么是红色,要么是黑色
  • 根节点是黑色
  • 叶子节点都是黑色的空节点
  • 红黑树中红色节点的子节点都是黑色
  • 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

• 在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质

• 查找：红黑树也是一棵BST（二叉搜索树）树，查找操作的时间复杂度为：O(log n)

• 添加：

  • 添加先要从根节点开始找到元素添加的位置，时间复杂度O(log n)
  • 添加完成后涉及到复杂度为O(1)的旋转调整操作
  • 故整体复杂度为：O(log n)

• 删除：

  • 首先从根节点开始找到被删除元素的位置，时间复杂度O(log n)
  • 删除完成后涉及到复杂度为O(1)的旋转调整操作
  • 故整体复杂度为：O(log n)

4.4 散列表

• 散列表(Hash Table)又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性
• 将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash(key)

4.4.1 hash冲突

• 可能两个元素经过hash计算之后，计算出的hash值是一样的
• 也就是key一样，hash一样，但是hash一样，key也可以不一样。

4.4.2 hash冲突解决

4.4.2.1 拉链法

• 将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除
  的情况。
• HashMap采用的就是拉链法

4.4.2.2 开放定址法

• 如果p=H(key) 出现冲突时，则以p为基础，再次hash，p1=H(p)，如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi 。
• 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次
  hash，所以只能在删除的节点上做标记，而不能真正删除节点。

4.4.2.3 再哈希法

• 提供多个不同的hash函数，当R1=H1(key1) 发生冲突时，再计算R2=H2(key1) ，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。

4.4.2.4 建立公共溢出区

• 将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

4.5 HashMap底层原理

• HashMap的数据结构： 底层使用hash表数据结构，即数组和链表或红黑树

• 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标

• 存储时，如果出现hash值相同的key，此时有两种情况。

  • 如果key相同，则覆盖原始值；
  • 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中 ；
  • 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

• JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

• JDK1.8及之后，当链表长度大于阈值（默认为8） 时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。扩容 resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表（剪枝）

4.6 put具体流程

4.6.1 常见属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认的初始容量，大小为16
static final float DEFAULT_LOAD_FACTOR = 0.75f;			//默认的加载因子，扩容阈值 == 数组容量  *  加载因子
transient HashMap.Node<K,V>[] table;
transient int size;


static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        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;
        }
}

4.6.2 put源码

// 首先计算hash
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
  	// 第一次的时候table为空，进行resize，创建出table数组大小为16，扩容阈值为12
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
  	// table数组指定位置是否有元素，没有就直接添加元素
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
      	// table数组该位置有元素
        Node<K,V> e; K k;
      	// 如果当前table位置key的hash和待添加key的hash是一样的，并且key一样或者equals(key)
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
          	// 将当前tab位置元素引用给临时entry e
            e = p;
      	// 判断当前是否是红黑树树节点，是的话，采用红黑树的方式添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
          	// 此时遍历table下的所有链表
            for (int binCount = 0; ; ++binCount) {
              	// 当遍历到链表尾部
                if ((e = p.next) == null) {
                  	//采用尾插法插入新的节点
                    p.next = newNode(hash, key, value, null);
                  	// 判断当前链表长度是否到达需要进行树化，满足就将链表变为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
              	// 当遍历到有一个节点的hash以及它的key与待插入元素的key相等或者equals，直接跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
              	// 为了遍历链表，本轮扫描结束，将下一个节点赋值给当前节点
                p = e;
            }
        }
      	// 临时entry不为空
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
              	// 将e的value设置为当前的value
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
  	// 判断是否到达扩容阈值，到达就进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4.6.3 总结

• 判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）
• 根据键值key计算hash值得到数组索引
• 判断table[i]==null，条件成立，直接新建节点添加
• 如果table[i]==null ,不成立
  • 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
  • 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
  • 遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操 作，遍历过程中若发现key已经存在直接覆盖value
• 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容。

4.7 HashMap的扩容机制

4.7.1 扩容源码

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
  			// 此一次table是null，因此oldCap为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
  			// 第一次oldThr也为0
        int oldThr = threshold;
        int newCap, newThr = 0;
  			// 非第一次
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
          	// 此时newCap为原来的两倍32、64、..
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
              	// newThr为原来的两倍，24、48、...
                newThr = oldThr << 1; 
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {       
          	// 第一次的时候newCap为16，newThr为12
            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;
  			// 第一次创建了大小为16的Node数组，非第一次根据newCap创建对应大小的Node数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
          	// 遍历老数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                  	// 如果老数组第j个位置的元素下面没有任何元素
                    if (e.next == null)
                      	//经过计算后添加到新数组中
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                      	//如果是树节点，按照树方式添加
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                      	// 遍历链表，需要保持顺序
                        do {
                          	// 老数组节点下的节点
                            next = e.next;
                          	// 对于哈希值在新容量模运算后为0的元素，它们需要保持顺序，因此会创建两个指针（loHead和loTail）来指向这些元素，然后将它们添加到新表中。
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                              // 对于哈希值在新容量模运算后不为0的元素，它们需要保持顺序，因此会创建两个指针（hiHead和hiTail）来指向这些元素，然后将它们添加到新表中。
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                      	// 此时经过(e.hash & oldCap) == 0的元素，此时位置在新表的第j个位置
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                      	// // 此时经过(e.hash & oldCap) != 0的元素，此时位置在新表的第(j + 老table长度)位置
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

4.7.2 总结

• 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
• 每次扩容的时候，都是扩容之前容量的2倍；
• 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
  • 没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
  • 如果是红黑树，走红黑树的添加
  • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

4.8 为什么是无符号左移16

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

• 如果只使用hashCode()作为下标，那么在一些情况下，会造成元素分布的table中的数量极不均衡，table大多数位置是空的，而极个别位置下是红黑树，并且此时table大小也扩容到了64。
• 再进行无符号的右移16为就能确保分布相对均衡。
• (h = key.hashCode()) ^ (h >>> 16)就是扰动函数。

4.9 HashMap长度为什么一定是2的整数次幂

(p = tab[i = (n - 1) & hash])

• (n-1)&hash : 得到数组中的索引，代替取模，性能更好；数组长度必须是2的n次幂；如果不是2的整数次幂(n - 1) & hash和hash % n得到的结果不一致。
• 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

4.10 HashMap在JDK1.7为什么会死锁

• 根本原因就是因为采用了头插法，使得在扩容之后更改了链表的顺序，原本3-2-1的顺序更改为了1-2-3。再加上多线程，线程1进行了扩容，但是线程2对元素的引用还是正常的，此时线程2再进行扩容就会出现死锁。
• 链接