集合容器概述

什么是集合

集合框架：用于存储数据的容器

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

常见的集合类有哪些

Map接口和Collection接口是Java中所有集合容器的父接口

Collection接口的子接口包括： List、Set、Queue

List接口的实现类有：ArrayList、LinkedList、Stack、Vector等

Set接口的实现类有：HashSet、TreeSet、LinkedHashSet等

Queue接口的实现类有：PriorityQueue、ArrayDeque等

Map接口的实现类有：HashMap、TreeMap、HashTable、ConcurrentHashMap等

List、Set、Map三者的区别？List、Set、Map是否继承自Collection接口？List、Map、Set、三个接口存取元素时，各有什么特点？

集合中有两个核心接口，分别是Collection和Map，Collection接口下面有三个接口，分别是，List、Set、Queue,而Map单独是一个接口，所以Map并未继承自Collection接口

Collection下的两个接口：

• List：特点：List是一个有序容器，即存取顺序一致，List支持索引，List可以存储重复元素。常见实现类有ArrayList，LinkedList、Stack、Vector
• Set：特点：Set是一个无序容器，元素的存储位置随机（由元素的HashCode决定），不支持索引，Set不可以存储重复元素（null只允许有一个），常见实现类有，HashSet、LinkedHashSet、TreeSet

Map是一个键值对模式的集合（即Key-Value），存储键值之间的映射。Key无序，唯一；Value不要求有序，允许重复。Map可以实现通过Key查找对应Value。常见实现类有HashMap、TreeMap、HashTable、ConcurrentHashMap

集合框架底层数据结构

collection

List

• ArrayList ：Object数组
• Vector ：Object数组
• LinkedList ：双向链表（JDK1.6之前为循环链表，JDK1.7取消了循环）

Set

• HashSet ：基于HashMap实现，底层用HashMap来存储数据
• LinkedHashSet：LinkedHashSet继承与HashSet，并且其内部是通过LinkedHashMap来实现的。
• TreeSet：红黑树

Queue

• PriorityQueue：Object[] 数组来实现二叉堆
• ArrayDeque：Object[]数组+双指针

Map

• HashMap：JDK1.8之前是数组+链表组成，数组是HashMap的主体，数组中存储的是Node节点，Node节点是链表节点。用来解决Hash冲突即拉链法。JDK1.8以后，由数组+链表+红黑树组成，为了避免数组中出现过长链表导致的性能降低，当链表节点数超过8后，将链表转为红黑树，低于6后从红黑树重新转为链表。
• LinkedHashMap：LinkedHashMap继承自HashMap，所以它底层的实现就是HashMap的实现，另外，LinkedHashMap在HashMap的基础上将节点从Node换成了Entry，以这种方式，增加了一条双向链表，使的上面的结构可以保持键值对的插入顺序，同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• HashTable：数组加链表组成
• TreeMap：红黑树

哪些集合类是线程安全的

• Vector
• HashTable
• ConcurrentHashMap
• CopyOnWriteArrayList
• CopyOnWriteArraySet

Java集合的快速失败机制fail-fast

fail-fast是Java集合的一种错误检测机制，当多个线程对集合容器进行结构上的改变操作时，有可能产生fail-fast，即抛出一个ConcurrentModificationException。

例如：一个线程遍历容器，一个线程在容器遍历过程中删除一个数据，就会发生fail-fast。

原因：我们遍历集合容器比如List时，会调用iterator（）方法创建一个Iterator实例，该实例有个成员变量expectModCount，这个变量会被赋值为modCount是集合实例的成员变量，这个modCount表示该集合被修改的次数。当我们用多线程遍历集合同时调用集合方法remove（）修改集合，集合中的modCount会加1，但是expectModCount不会，遍历判断得到两者不同，就会触发异常。想要解决这个问题可以使用iterator提供的remove方法进行删除，或者使用CopyOnWriteArrayList来替换ArrayList

fail-fast

怎么确保一个集合不被修改

Collections类下有一类方法，unmodifiableCollection,unmodifiableList,unmidifiableSet等，这种方法可以创建出一个可读集合，只要进行修改，就会抛出异常。

如何选用集合

主要根据集合的特点来选用，比如我们需要根据键值获取到元素时，我们选择Map接口下的实现类，需要排序时使用TreeMap。不需要排序时使用HashMap，需要保证线程安全时使用ConcurrentHashMap.

当我们只需要存放元素值时 ，就选择Collection接口下的实现类，需要数据唯一使用Set，有序用TreeSet，不需要有序用HashSet。不需要元素唯一，或者需要元素支持索引就使用List，比如ArrayList和LinkedList

Collection子接口之List

迭代器Iterator是什么

Iterator接口提供遍历任何Collection接口的功能。我们可以从Collection接口的iterator方法中获取一个迭代器，进行对集合的遍历。迭代器允许我们在运行时移除元素。

*Iterator只提供单向遍历（hasNext），但是更安全，在当前遍历的集合被其他线程改变时，会马上抛出异常。

如何边遍历边移除Collection中的元素

边遍历边移除Collection中的元素使用iterator.remove()方法。多线程遍历Collection时，若有一个线程使用集合的remove方法会抛出ConcurrentModificationException，我们使用iterator.remove()方法就不会出现这个问题。

Iterator和ListIterator有什么区别

• Iterator可以遍历List和Set，ListIterator只能遍历List
• Iterator只能单向遍历，ListIterator可以双向遍历
• Iterator功能单一，ListIterator在其基础上添加了功能

遍历一个List有哪些不同的方式，每种方法的实现原理时什么，Java中List遍历的最佳实践是什么

1. for循环遍历，在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读到最后一个元素时停止，当遍历的数据实现了RandomAccess接口（快速随机访问）时，推荐使用for循环遍历元素。
2. Iterator遍历，Collection接口提供iterator方法获取对象的迭代器，迭代器本质上是一种叫迭代子模式的设计模式。
3. foreach遍历，增强for，底层用iterator迭代器实现，使用时不需要显示声明迭代器或者计数器。代码简介但是不能进行删除，替换操作。

最佳实践

• 如果一个数据结构实现了RandomAccess接口，优先使用for循环进行遍历
• 不支持的使用foreach或者iterator进行遍历

ArrayList

ArrayList 继承自 AbstractList ，实现了 List，AccessRandom（快速随机查找），Cloneable，Serializable这些接口。

说一下ArrayList的优缺点

• 优点：ArrayList底层数据结构是Object[]，且ArrayList实现了RandomAccess接口，支持快速随机查找，且效率很高
• 缺点：ArrayList删除修改的效率不高，因为底层数据机构是数组，且ArrayList是线程不安全的，在多线程情况下建议使用CopyOnWriteArrayList代替

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

• 数组转集合：调用Arrays.toList();
• 集合转数组：集合对象提供一个toArray()方法。

ArrayList和Vector的区别

• ArrayList是List的主要实现类，底层使用Object[]存储，适用于频繁的查找工作，线程不安全；
• Vector是List的主要实现类，底层使用Object[]存储，是线程安全的。

ArrayList与LinkedList区别

1、是否线程安全：ArrayList与LinkedList都是不同步的，也就是不保证线程安全。

2、底层数据结构：ArrayList底层的数据结构是Object[],LinkedList在JDK7以前是双向循环链表，之后是双向链表。

3、插入和删除是否受元素位置的影响：ArrayList底层是数组，所以插入删除元素的时间复杂度为On，LinkedList底层是链表，插入和删除的时间复杂度为O1，但是查找到该元素位置的时间复杂度为On。

4、是否支持快速随机访问：ArrayList和LinkedList都支持随机访问，但是LinkedList的快速随机访问不高效，因为底层是链表，本质上还是从头遍历到尾。

5、内存空间占用：ArrayList空间上的浪费主要是数组会有空的，LinkedList在空间上的花费则体现在它的每个元素都需要消耗比ArrayList更多的空间（因为要存放前驱和后继以及数据）

*建议使用ArrayList

多线程场景下如何使用ArrayList

ArrayList是一个线程不安全的集合容器，所以遇到多线程场景，可以使用Collections.synchronizedList();方法，或者使用CopyOnWriteArrayList代替。

*Collections.synchronizedList()方法是创建了一个SynchronizedRandomList或者SynchronizedList返回，这两个类都是List的子类，且都是线程安全的。

CopyOnWriteArrayList

写时赋值ArrayList，底层数据结构和ArrayList一致，是一个线程安全的List，在CopyOnWriteArrayList中使用ReentrantLock和volatile和数组拷贝实现线程安全

• 在向数组中添加数据时，会调用ReentrantLock将CopyOnWriteArrayList锁住，保证数据只被一个线程修改
• 使用Volatile修饰数组，当数组添加了元素时，让其他线程立马知道
• 每次修改和添加数组数据时，创建一个新的数组，将原数组的数据添加到新数组，在将对象的数组引用指向新数组，这样操作是因为，Volatile只在添加元素时生效，在修改元素时，要将引用地址改变，让其他线程知道。

为什么ArrayList的elementDate加上transient修饰？

我们知道ArrayList底层数据结构是Object数组，而这个elementDate就是这个数组。且ArrayList实现了Serializable接口，这意味着ArrayList实例是可以实例化的。而elementDate变量是用transient修饰的，transient修饰的变量是会被排除在序列化和反序列化的过程中的。我们要存储ArrayList为什么把集合的主体排除了呢？这是因为，ArrayList中实现了writeObject方法和readObject方法，在序列化和反序列化之前遍历数组将存入的元素（数组往往不是占满的）进行序列化，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

ArrayList 扩容机制

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

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

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

构造函数

ArrayList有三种初始化方法。

1、默认无参构造器，用默认容器大小10，创建一个容器，这里其实初始化的是一个空数组，等到第一次添加元素时才将数组扩容为10；

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

2、指定容器大小的初始化方法

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

3、传入集合数据的初始化方法

public ArrayList(Collection 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;
    }
}

添加元素 add()

public boolean add(E e) {
//确认是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal()

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //当是第一次add，即将容器的大小改变为DEFAULT_CAPACITY
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
                        //计算容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//修改容器次数加1

    // 元素个数超过数组长度
    if (minCapacity - elementData.length > 0)
        //进行扩容                
        grow(minCapacity);
}

由以上代码得到结论

• 使用无参构造初始化容器，数组为空数组。
• 第一次添加元素（add）,调用ensureExplicitCapacity判断是否需要扩容，calculateCapacity方法判断是否是第一次添加元素，如果是，返回容器大小等于默认容器大小即10；
• 当添加容器时，size>数组长度时，调用grow方法

grow()//扩容方法

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

结论，每次扩容会把容器扩容到原来的1.5倍（用的是右移运算符，>>），除非，扩容到1.5倍之后容器还是不够，会直接将能存储下的最小容量作为数组大小。

//ArrayList提供了一个ensureCapacity方法供用户使用，当需要一次性add大量数据时，可以进行手动的扩容来减少扩容次数，提升性能。

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

Collection子接口之Set

无序性和不可重复性的含义是什么

1. 无序性不代表完全随机，set的随机是指，不能按照数组的索引添加，而元素所在的位置是由元素的hashcode决定的
2. 不可重复性，表示添加元素时，会经过hashcode和equals方法进行判重，重复元素无法添加set中

比较HashSet、LinkedHashSet、TreeSet三者的异同

• 线程安全方面，HashSet和LinkedHashSet和TreeSet三者都是线程不安全的
• 底层数据结构方面，HashSet底层由HashMap实现，即数组+链表+红黑树，LinkedHashSet底层由LinkedHashMap实现，在HashMap的基础上加上了一条双向队列。TreeSet底层是基于TreeMap实现了，底层数据结构是红黑树
• 实现接口方法，他们都是Set接口下的实现类
• 功能方面，HashSet，具有无序，不重复的特点。LinkedHashSet在HashSet的基础上有增删元素有序的特点。TreeSet可以实现自定义排序规则。

List和Set的区别

• 接口方面：List和Set都是Collection接口下的子接口
• 使用场景方面：List接口下的集合容器是支持快速随机查找的，有序的，可以重复的。Set接口下的容器是无序的，不可重复的
• 实现类方面：List接口下有，ArrayList、LinkedList、Vector，Set接口下有HashSet、TreeSet、LinkedHashSet
• 性能方面，Set在检索元素方面效率低下（Set遍历需要创建iterator进行遍历），删除和插入效率高（底层使用HashMap的put和remove方法）。List检索元素效率高（List接口下的元素大多实现RandomAccess接口，既支持快速随机查找，可以使用for进行遍历），删除和插入的效率低（底层是数组）。

Collection子接口之Queue

Queue与Deque的区别

Queue是队列，是一种先进先出的数据结构，即一端进行插入，一端进行删除。Deque是双端队列，两端都可以进行插入和删除操作。

ArrayDeque和LinkedList的区别

• 接口方面：ArrayDeque实现了Deque接口，具有双端队列的基本功能，LinkedList实现了List接口和Deque接口
• 线程安全方面：ArrayDeque和LinkedList都不是线程安全的
• 数据结构方面：ArrayDeque底层是数组+双指针，LinkedList底层是链表
• 适用场景方面：如果是使用栈/队列等情况，ArrayDeque的性能要优于LinkedList，但是LinkedList由于继承了List接口所以他支持索引查找等操作
• Null值方面：ArrayDeque不支持添加null值，LinkedList支持添加null值

PriorityQueue

优先队列，实现了Queue即可，其与Queue的区别在于，出队的顺序是有元素优先级相关的。即总是优先级最高的元素先出队。

PriorityQueue是一种堆的实现，底层数据结构是数组，通过堆元素的上浮或下沉实现了O(logn)的时间复杂度内插入或者删除元素，PriorityQueue是非线程安全的，不可以存储Null值。可以指定一个Comparator作为参数，指定优先级规则。

BlockingQueue是什么

BlockingQueue是JDK中java.util.concurrent包下的一个接口，既阻塞队列，是一种线程安全的集合容器，他线程安全的原因是他的实现类中有一个成员变量，RetrentLock类的实例，在使用take，put等方法时，会进行加锁处理。阻塞队列主要用于生产者-消费者模型。在队列满时，put线程会阻塞直到队列中有空位，在队列空时，take线程会阻塞，直到队列中有元素。BlockingQueue，的实现子类有ArrayBlockingQueue，LinkedBlockingQueue，PriorityBlockingQueue，DelayQueue等。

Queue中的remove()和poll()方法有什么区别

• 相同点：都是返回第一个元素，并在队列中删除返回的对象
• 不同点：如果没有元素，remove()方法会抛出NoSuchElementException异常，poll()方法会返回null值。

Map接口

HashMap和HashTable的区别

• 接口方面：HashMap和HashTable都是Map接口下的实现类
• 线程安全方面：HashTable是线程安全的，HashMap不是线程安全的
• 底层数据结构方面：HashMap底层的数据结构在JDK1.8以前是数组+链表，JDK1.8之后是数组+链表+红黑树。HashTable就是数组+链表
• 使用场景方面：因为线程安全的原因，HashMap的性能要比HashTable好，考虑到线程安全时可以使用HashTable但是不推荐使用，因为可以用ConcurrentHashMap代替
• Null值方面：Hashmap允许有Nullkey和NullValue，NullKey只允许有一个，NullValue可以有多个，HashTable不可以有Nullkey和NullValue
• 初始容量大小和扩容方面：HashMap初始容量是16，每次扩容都会变为原来的2倍，HashTable初始容量为11，每次扩容容量会变为原来的2n+1;

HashMap和HashSet的区别

• 接口方面：HashMap是Map接口的实现类，HashSet是Collection接口下子接口Set的实现类
• 线程安全方面：HashMap和HashSet都不是线程安全的
• 底层数据结构方面：HashMap底层是数组+链表+红黑树，HashSet底层基于HashMap实现
• 使用场景方面：HashMap存储key-value形式数据，HashSet存储值。添加数据时，HashMap使用put方法，set使用add方法

TreeMap和HashMap的区别

• 接口方面：HashMap是Map接口下的实现类，TreeMap是Map接口下子接口SortedMap的实现类。
• 线程安全方面：TreeMap和HashMap都不是线程安全的
• 底层数据结构方面：HashMap底层数据结构是数组+链表+红黑树，TreeMap底层是红黑树
• 使用场景方面：需要将集合中元素排序时使用TreeMap，不需要时使用HashMap

HashSet如何检查重复

HashSet底层由HashMap实现，HashSet存的值实际上就是HashMap的key，HashMap检查key重复的方法是：计算key的hashCode，通过hashCode计算元素插入数组的位置，该位置若没有元素，将该元素插入，如果以及存在元素，调用equals方法判断两个元素是否出现hash冲突，如果两个对象真的一致，HashMap就不会让加入操作成功。

HashMap源码

JDK1.8之前

HashMap底层是数组+链表结合在一起也就是链表散列

HashMap通过哈希算法得到key的hashCode，然后通过hash&(n+1)计算出该元素应该存储的位置，如果当前位置已经存在元素了，调用equals判断元素是否真的相等（可能出现hash冲突），如果不相等使用拉链法链接，如过相等直接覆盖之前元素。

JDK1.8之后

在数组+链表的基础上增加了红黑树，如果数组的链表长度超过8，会调用（treeifyBin()）将当前链表转换成红黑树（只有当数组的长度超过64才会进行）

HashMap前后比较

	JDK1.7	JDK1.8
数据结构	数组+链表	数组+链表+红黑树
初始化方式	inflateTable（）	集成到resize()扩容函数中
hash值计算方式	四次异或运算，四次右移运算	一次异或运算，一次右移运算
存放数据的规则	无冲突时，存放数组；哈希冲突时，存放链表	无冲突时，存放数组，哈希冲突时存放链表，链表长度超过8时，将链表转化为红黑树
插入数据方式	头插法（先将原位置的数据移到后一位，在插入到该位置），当数组扩容时，重新将数据分配到数组中，会将链表倒置，多线程情况下可能会导致成环，导致死循环，所以在JDK1.8换成尾插法	尾插法（直接插入到链表尾部），此种方法在扩容时重新分配数据位置时，链表会保持原来的顺序。（尾插">头插->尾插）
扩容后存储元素位置的计算方式	全部按照原来的方法进行计算，用新的数组长度计算数据的hash值，之后用（hash&(n-1))计算数组下标	不进行重新计算，因为数组扩容为原来的两倍，只需要均匀的将数组元素分配到数组原来位置和，原来位置+原来数组长度的位置上。我们直到HashMap节点会保存hash值，而是否在原来位置只取决于新的hash值新扩容的一位是否为1.（没有重新进行hash运算，提升性能）详细

HashMap的put方法的具体流程

1. 调用putval方法，判断容器否为空或者长度为0，如果是，调用resize方法进行容器初始化。如果不是进行第二步。
2. 用hash算法算出元素的hashcode，再用hash值使用（n-1）&hash计算出元素存放的位置，如果该位置不存在元素，直接存放在该位置，如果存在，到第三步
3. 遍历该位置的链表，使用equals判断元素是否已经存在，如果存在，直接覆盖原本元素，如果不存在到第四步
4. 使用尾插法，将新元素链接到链表尾部，判断链表元素是否超过8个，且数组长度超过64，将链表转换为红黑树。判断当前hashmap中的元素个数是否超过threshold，如果没有，流程结束，如果超过了进行扩容。

HashMap的扩容操作是怎么实现的

• JDK1.8,在初始化时，数组容量为0，第一次put数据时会调用resize方法进行容器初始化，同时这个方法也是扩容方法，扩容在hashmap元素超过临界值时触发（数组长度*扩容因子）
• resize方法每次将数组扩大到原来的两倍
• 将数组扩大到原来的两倍以后，原数组的元素会被分配到新数组中，元素的位置，是原来的索引位置，或者原数组长度+原索引位置，这一步操作使用元素的hash属性与原数组长度进行&运算。1则到新索引，0则到老索引。这个操作是jdk1.8的一个优化，jdk1.7，扩容时，会将元素的hash值重新计算，然后hash&(n-1)计算索引位置。性能有显著提升

Hash是什么

Hash,一般翻译为散列，也有直接音译为哈希的，hash就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单来说就是将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HashMap是怎么解决哈希冲突的

所谓哈希冲突就是，不同的数据通过散列算法得到了一样的hash值。HashMap使用数组和链表结合，综合他们的优点，出现hash冲突的地方，使用链地址法（拉链法），也就是将hash值相同的元素，以链表的形式连接在数组上。

除此之外，HashMap还优化了hash算法，将key的hashcode与key的hashcode的前16位进行异或运算，降低出现哈希冲突的可能性，这一点相对于JDK1.7有一个优化，JDK1.7进行了五次异或，四次右移，性能相对低。

在以上两条的基础上，JDK8引入了红黑树的机制，链表的遍历时间复杂度是o(n)，红黑树的时间复杂度是o(logn),再出现hash冲突是，需要遍历链表/红黑树，判断是否是重复元素，使用红黑树可以提高遍历的速度。

是否可以使用任何类作为Map的key

技术上来说，可以，所有对象都可以作为key，但是使用上来说，使用的类需要重写hashcode和equals方法来确保使用HashMap时不会出现错误。建议使用String作为Map的key，String天然重修了HashCode方法和equals方法，且String有个属性hash保存着实例的HashCode，重复使用时不需要重新计算。

为什么HashMap中String这样的包装类适合作为Key

• String重写了hashcode方法和equals方法
• String是final修饰的类，其实例作为key具有不可更改性
• String中有一个hash属性，重复使用时，可以不用重复计算

HashMap为什么不直接使用hashCode()处理后的哈希值作为table的下标

hashCode方法返回的值是int类型的，其范围是-2^31-1~2^31，HashMap底层的数组显然取不到这么多的下标，所以HashMap优化了自己的hash方法，将hash值重新计算，一可以降低hash冲他的出现，二可以计算得到数组的索引位置。

HashMap类的属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//容器的最大容量，即2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//链表节点超过8个转成红黑树，少于六个从红黑树转成链表

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

//数组长度超过64，才能触发链表转换的到红黑树

static final int MIN_TREEIFY_CAPACITY = 64;

//存储元素的数组

transient Node[] table;

//存放具体元素的集

transient Set> entrySet;

//临界值(容量*填充因子)当实际大小超过临界值时，会进行扩容

int threshold;

//加载因子

final float loadFactor;

构造器

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

//参数是一个map用于将数据传入

public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

//指定容器大小

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//指定容器大小和加载因子

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

传入map的构造器其中的putMapEntries方法

final void putMapEntries(Map m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        //判断是否初始化，集table数组是否为空
        if (table == null) { // pre-size
                //未初始化，计算出应该的容器大小
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
                //计算得到容器的当前阈值，初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        //已初始化，元素个数大于阈值，进行扩容
        else if (s > threshold)
            resize();
        //将m中元素添加到Hashmap中
        for (Map.Entry e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

HashMap的长度为什么是2的幂次方

HashMap的元素是计算hashcode之后，以hashcode计算得到元素应该在的位置，哈希值的大小范围可以是-2^31-1到2^31，初始化容器时将数组设置成这么大肯定时不现实，所以我们就需要将元素均匀的分到数组中。比如说初始化容器大小为16，那么可以取到的位置就是0~15，我们可以将得到的哈希值16的余，就可以得到对应的位置，但是Java并不是这么做的。Java用(n-1)&hash的方式来计算位置。用位运算的方式比取余运算要快很多，n是容器的大小。我们要将元素均匀分布到容器中，n-1就必须满足二进制为全1，所以容器的大小就一定是2的幂次了。

HashMap为什么不直接使用红黑树？

因为红黑树需要旋转保持树的平衡，且树节点的占用空间是链表节点的两倍，这是时间和空间上的综合考虑。

*为什么8个时转换为红黑树，6个时转换为链表

避免频繁转换。

ConcurrentHashMap和HashTable的区别

• 接口方面：ConcurrentHashMap和HashTable都是map接口的实现类
• 底层数据结构方面：HashTable的底层数据结构是数组+链表，ConcurrentHashMap底层数据结构在JDK1.8以前是，分段的数组+链表实现，之后是数组+链表+红黑树实现
• 实现线程安全方面:ConcurrentHashMap在JDK1.8以前，使用分段锁机制实现，segment继承了ReentrantLock，将容器数组分割分段，每段加上锁，不同的段之间线程安全，不同线程无法同时操作同一段。JDK1.8之后抛弃了段机制，直接用数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作。HashTable使用Synchronized来保证线程安全，多个线程访问hashTable时，只有一个线程可以访问，其他线程会进入阻塞，性能很差。

ConcurrentHashMap底层数据结构

ConcurrentHashMap1.7

存储结构

JDK1.7中的ConcurrentHashMap的底层数据结构是以一种segment段的形式实现的，每一个Segment段是一个类似HashMap的结构，所以每一个Segment的内部都可以进行扩容。但是Segment段的个数一旦初始化就不能改变。默认有16个segment段，所以你可以认为，ConcurrentHashMap默认支持最多16个线程并发。

ConcurrentHashMap1.8

JDK1.8中的ConcurrentHashMap，取消了段机制，而是将数据结构改成类似HashMap的结构，也就是数组+链表+红黑树的结构。采用synchronized和CAS操作来实现并发安全。synchronized只锁定当前链表的或者红黑树的首节点，这样，只要hash不冲突，就不会产生并发，性能提高。

HashMap和ConcurrentHashMap的区别

• 接口方面：HashMap和ConrrentHashMap都是Map接口下的实现类
• 线程安全方面：HashMap是线程不安全的，ConcurrentHashMap是线程安全的，ConcurrentHashMap1.7实现线程安全的方法是，存储数据的Segment继承自RetrentLock，ConcurrentHashMap1.8使用了Synchronized和Cas操作
• 数据结构方面：HashMap是数组+链表/数组+链表+红黑树，ConcurrentHashMap是Segment数组/数组+链表+红黑树
• Null值方面：HashMap支持key为null（只能有多个），vlaue为null，ConcurrentHashMap不支持Null。

ConcurrentHashMap底层具体实现直到吗？实现原理是什么

JDK1.7

将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中的一个段数据时，其他线程不可以访问这个段，但是可以访问其他段，提高了并发量。

JDK1.7ConcurrentHashMap底层具体是Segment数组，默认长度为16，也就是支持16个线程并发。segment就是一个类似于HashMap的结构，HashEntry数组+链表。且segment继承自ReentrantLock，这也就是为什么ConcurrentHashMap支持多线程。

JDK1.8

ConcurrentHashMap摈弃了Segment机制，采用Node+CAS+Synchronized来保证并发的安全进行实现，Synchronized只锁定链表或者红黑树的首节点，这样只要hash不冲突，就不会产生并发。

辅助工具类 Array和ArrayList有何区别

• 数组初始化时长度固定不能再修改，ArrayList长度不固定
• 数组可以存储基本数据类型，ArrayList只能存储实例对象
• ArrayList提供很多内置方法，array没有

Collection和Collections有什么区别

• Collection是一个集合容器的顶级接口，其下有LIst、Set、Queue等接口，有ArrayList、LinkedList、HashSet、TreeSet、ArrayDeque等实现类，是一个规范集合行为的接口。
• Collections是一个给集合容器提供服务的工具类，提供了很多静态方法，如sort，unmodifiableCollection，synchronizedCollection等方法。

TreeMap和TreeSet再排序时如何比较元素？

TreeMap排序时通过key比较，TreeSet排序时通过值比较，TreeMap和TreeSet泛型规定的数据类型应该时实现类Comparable接口，TreeMap内部会使用泛型类实现的compareto方法，也可以再初始化时传入一个Comparator的匿名内部类对象。

Java中的队列都有哪些，有什么区别

1. ArrayDeque
2. LinkedList
3. PriorityQueue
4. ArrayBlockingQueue
5. LinkedBlockingQueue
6. LinkedBlockingDeque
7. PriorityBlockingQueue
8. DelayQueue
9. ConcurrentLinkedQueue
10. SynchronousQueue

延伸考察ConcurrentHashMap与HashMap、HashTable等，考察对技术细节的了解程度 HashMap的死循环

JDK1.7，JDK1.7中HashMap底层的数据结构是数组+链表，当出现hash冲突时，节点会链接到对应数组位置的链表上，插入方式是头插法。当hashmap的size大于临界值时，数组会扩容，扩容后，数据需要重新分配到数组中，因为是头插法，所以会导致原先的链表和新的链表是倒置的。再多线程情况下，假设线程A，B，同时扩容，当A线程分配好指针指向链表的头节点和next节点时，该线程的时间片结束，到线程B运行，线程B将链表倒置，此时线程A重新开始运行，线程A将节点指向next节点时，就会成环，此时就会出现死循环。这个问题再JDK1.8得到解决，插入数据的方法改成了尾插法。（循环）

JDK1.8，再JDK1.7中出现的循环现象已经被修复，此时JDK1.8的hashMap还会出现死循环吗？答案是会的。经过测试，再多线程条件下，JDK1.8再将链表转换为红黑树和插入数据到红黑树时都有可能出现死循环

结论：在多线程条件下，使用HashMap，会有出现数据丢失以及死循环的可能，无论哪个版本。我们不能责怪HashMap，HashMap的角色本来就不是用来解决多线程的场景，多线程场景建议使用ConcurrentHashMap。

ConcurrentHashMap在JDK1.8中的改进

JDK1.7中ConcurrentHashMap的设计：

在JDK1.7的ConcurrentHashMap中，底层的数据结构是一个Segment类的数组，默认长度是16，这个Segment叫段，Segment继承自ReentrantLock,ReetrantLock是一种可重入锁，就是这种机制让ConcurrentHashMap支持多线程。本质上Segment类就是一个小的HashMap，Segment中的数组+链表的机制和HashMap一致。既JDK1.7ConcurrentHashMap最多支持16个线程同时操作,比起HashTable有明显提升。

JDK1.8中ConcurrentHashMap有两方面改进：

1. 取消了Segment[]的数据结构，直接改成了类似HashMap的HashEntry[]的数据结构，给数组中链表或红黑树的首节点加锁，以此实现ConcurrentHashMap的并发性。
2. 将底层数据结构改成和JDK1.8的HashMap的数据结构类似，数组+链表+红黑树。无论是ConcurrentHashMap的size大于临界值时数组扩容，还是hash冲突时遍历链表，都可以将遍历的效率从O(n)提高至O(logn)。

HashMapJDK1.7JDK1.8性能比较

• put方法：JDK1.7和JDK1.8近似，JDK1.8稍慢，原因时JDK1.8链表使用头插法以及转换为红黑树，但是JDK1.8改进了hash算法以及扩容之后的数据的分配方法。所以性能相差无几
• get方法：JDK1.8的性能要优于JDK1.7，JDK1.8在JDK的基础上添加了红黑树的数据结构，查询数据的效率高了。

Collections.synchronizedList和CopyOnWriteArrayList性能分析

CopyOnWriteArrayList在线程对其进行变更操作时，会创建一个新数组以存放新的字段，因此写操作性能很差；而Collections.synchronizedList读操作使用了synchronized，因此读性能很差。

几个面试题 你说说Collection接口里面有什么子类

首先我说一下Collection，Collection是一个接口，我们知道接口是用来规范一系列行为的，而Collection就是用来规范集合的一部分行为的。Collection接口下有List、Set、Queue等子接口。

• List接口下的子类有ArrayList、LinkedList、Vector等子类，这个接口下的子类的特点是，有序存放数据，几乎都实现了RandomAccess接口，可以使用for循环遍历，也就是支持索引，存放的数据可以重复。可以有多个null值。
• Set接口下的子类有HashSet，LinkedHashSet、TreeSet等子类，该接口下的子类的特点是，数据随机存放，此处的随机并不是完全随机，是根据hash值确定索引位置而不是按序存放。存储数据不重复，重复元素会直接覆盖。TreeSet支持以一个规则排序Set容器中的数据
• Queue接口下的子类有ArrayDeque,LinkedList,PriorityQueue,ArrayBlockingQueue等子类，这个接口的实现类可以实现队列的功能。

什么场景下使用List，Set、Map呢

首先，List和Set是Collection接口下的子接口，Map是和Collection同级的顶级接口。

当我们需要存储的数据是键值对形式时，我们使用Map接口下的实现类。Map接口下的实现类有HashMap，LinkedHashMap、TreeMap、HashTable、ConcurrentHashMap等，当我们需要并发时使用ConcurrentHashMap，需要数据按一个规则按Key排序时用TreeMap，需要数据按序存取时用LinkedHashMap，其他情况使用HashMap即可。

当我们需要存取的数据只有一个值时，使用List和Set接口下的实现类。当我们需要数据不重复时，使用Set接口下的实现类，Set接口下的子实现类有HashSet、TreeSet、LinkedHashSet等，需要数据按一个规则排序时，使用TreeSet，按序存取时使用LinkedHashSet，其他情况使用HashSet。当我们不需要数据不重复，或者需要按索引查找元素时，使用List接口下的实现类，List接口下的实现类有ArrayList，LinkedList、Vector，CopyOnWriteArrayList，考虑到线程安全时，可以使用CopyOnWriteArrayLIst，其他情况推荐使用ArrayList。