说说 List,Set,Map 三者的区别？

List (对付顺序的好帮⼿)：存储的元素是有序的、可重复的。
Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。
Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数 y=f(x)，“x”代表 key，”y”代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个键最多映射到⼀个值。

集合框架底层数据结构总结

Collection 接⼝下⾯的集合

List

Arraylist ：

底层用数组实现的存储。

特点：查询效率高，增删效率低，线程不安全。使用频率很高。
Vector ：

底层用数组实现的存储。

特点：线程安全
LinkedList ：

底层使用双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)实现

特点：增删效率高，查询效率低，线程不安全。

Set

HashSet （⽆序，唯⼀）: 基于HashMap实现的，底层采⽤ HashMap来保存元素
LinkedHashSet ： LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过LinkedHashMap 来实现的。
TreeSet （有序，唯⼀）：红⿊树(⾃平衡的排序⼆叉树)

Map 接⼝下⾯的集合

Map

HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间

LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。

Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的

TreeMap ：红⿊树（⾃平衡的排序⼆叉树）

ArrayList

ArrayList底层时Object[]，数组的长度是有限制的,那ArrayList是怎么自动扩容的

ArrayList可以通过构造方法在初始化的时候指定底层数组的大小。

通过无参构造方法的方式ArrayList()初始化，则赋值底层数Object[] elementData为一个默认空数组Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}所以数组容量为0，只有真正对数据进行添加add时，才分配默认DEFAULT_CAPACITY = 10的初始容量。

大家可以分别看下他的无参构造器和有参构造器，无参就是默认大小0，有参会判断参数。

/**
  * Constructs an empty list with the specified initial capacity.
  *
  * @param  initialCapacity  the initial capacity of the list
  * @throws IllegalArgumentException if the specified initial capacity
  *         is negative
  */
 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);
     }
 }

 /**
  * Constructs an empty list with an initial capacity of ten.
  */
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;// 默认为空
 }

ArrayList长度不受限制的实现方式比较简单，他就是通过数组扩容的方式去实现的。

就比如我们现在有一个长度为10的数组，现在我们要新增一个元素，发现已经满了，它就会执行如下操作:

第一步他会重新定义一个长度为当前1.5倍的数组。
把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组，ArrayList就这样完成了一次改头换面。

ArrayList新增逻辑？

他有指定index新增，也有直接新增的，在这之前他会有一步校验长度的判断ensureCapacityInternal，就是说如果长度不够，是需要扩容的。

直接新增：

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

在扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，右移一位，其实就是除以2这个操作。

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

指定位置新增的时候，在校验之后的操作很简单，就是数组的copy，大家可以看下代码。

指定位置新增：

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

ArrayList源码建议看这边：ArrayList源码

区别相关

HashMap与HashTable的区别？

HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；
HashMap允许K/V都为null；后者K/V都不允许为null；
HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类；

安全性

有哪些集合是线程不安全的？怎么解决呢？

我们常⽤的 Arraylist, LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都不是线程安全的。

解决办法很简单，可以使⽤线程安全的集合来代替。

如果你要使⽤线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使⽤：

ConcurrentHashMap : 可以看作是线程安全的 HashMap。
CopyOnWriteArrayList :可以看作是线程安全的 ArrayList ，在读多写少的场合性能⾮常好，远远好于 Vector。
ConcurrentLinkedQueue :⾼效的并发队列，使⽤链表实现。可以看做⼀个线程安全的LinkedList ，这是⼀个⾮阻塞队列。
BlockingQueue : 这是⼀个接⼝，JDK 内部通过链表、数组等⽅式实现了这个接⼝。表示阻塞队列，⾮常适合⽤于作为数据共享的通道。
ConcurrentSkipListMap :跳表的实现。这是⼀个 Map ，使⽤跳表的数据结构进⾏快速查找。