ArrayList

ArrayList底层是一个动态数组，默认初始化容量为10，是非线程安全的。ArrayList可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

如果ArrayList容量不足以容纳当前元素个数的时候，会通过ensureCapacity()方法进行扩容，默认扩容为旧容量的1.5倍 + 1，如果默认扩容后的容量仍不足以容纳当前元素个数，则把需要新增的元素个数作为扩容的长度，扩容之后再把旧数组中的元素通过Arrays.copyOf()方法拷贝到新的扩容数组中。所以使用ArrayList最好确定元素的初始化容量，否则频繁的数组扩容会造成性能上的消耗。 ArrayList中允许元素为null。

LinkedList

LinkedList底层是一个双向循环链表，是非线程安全的 。LinkedList进行插入和删除元素的操作只需要移动相应的指针，所以插入和删除操作效率非常高，但是由于无法提前直到LinkedList的长度，所以查找元素时需要从链表头或者链表尾开始遍历查找，所以查找元素的效率比较低。

由于LinkedList是双向循环链表，在LinkedList内部的方法entry(int index)有一个提升查找效率的优化，该方法是查找链表指定位置的元素，查找时会先比较指定位置距离链表头比较近就从头部开始遍历，如果距离链表尾比较近就从尾部开始遍历，这样可以减少一部分不必要的遍历。LinkedList中允许元素为null。LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。

Vector

Vector底层是一个动态数组，默认初始化容量为10，是线程安全的。Vector的实现基本上与ArrayList相同，唯一的区别是Vector扩容时默认新容量为旧容量的2倍，如果新容量还不够，就把所需的容量作为新容量。Vector中允许元素为null。

HashMap

HashMap底层是基于哈希表实现，即数组+单链表的形式，默认初始化容量为16（实际容量必须是2的整数次幂），是非线程安全的。通过Entry[]数组来存放元素，每个Entry本质上又是一个单链表，每个元素都是以key-value键值对的形式存放，可以直接通过key值索引到对应的value值，所以查找效率相对比较高。HashMap中允许key和value为null。

HashMap内部是如何组织哈希表的呢？主要通过两步操作：

（1）计算key的hash值：首先调用Object类的hashCode()方法获取key的hashcode，然后调用HashMap的内部函数hash()对hashcode进行二次计算，最终得到key对应的hash值。  

（2）计算hash值对应的数组索引（value值存放的内存地址）：采用位运算。首先调用HashMap的内部函数indexFor()方法，传入key的hash值和哈希表长度作为参数，通过将hash值与数组长度作位与计算（h & (length - 1)）直接得到对应的数组索引；所以 indexFor()返回的数组索引可以直接通过数组下标索引的方式获取对应的value值，访问速度相当快。

HashMap内部是如何实现动态扩容的呢？主要涉及三个参数：

（1）initialCapacity：初始化容量，默认为16，实际容量必须是2的整数次幂。

（2）loadFactor：负载因子；它是介于0和1之间的浮点数，默认为0.75，表示HashMap的填充比，当负载因子越接近1表示元素在数组中的填充密度越大。如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。计算方式为loadFactor = 元素总个数 / 数组总长度。

（3）threshold：阈值；当HashMap中存储数据的数量达到threshold时，就需要进行扩容，新的容量为旧容量的2倍；计算方式为 threshold = 元素总个数 * loadFactor。因此，HashMap的实际填充率不会超过负载因子。

具体的扩容步骤：当HashMap调用put()方法添加一个键值对Entry时，会调用addEntry()方法新增一个Entry，在该方法中会判断当前元素个数是否超过了阈值threshold，如果超过了则需要进行扩容操作，会调用resize()方法并默认传入数组长度的2倍作为新容量的长度；在resize()方法中会新建一个Entry[]数组，并初始化为新容量的长度，接着会调用transfer()方法把旧HashMap的元素全部拷贝到新创建的HashMap中；transfer()内部会遍历整个哈希表，并重新建立新的链表关系，是一个相对耗时的操作。扩容操作完成后会重新更新threshold的值。HashMap的扩容操作会遍历整个HashMap，应该尽量避免该操作发生，设置合理的初始大小initialCapacity和负载因子loadFactor，可以有效的减少HashMap扩容的次数。

HashMap是如何解决哈希冲突的？主要通过单链表来解决：

HashMap本身就是一个数组链表，数组的每个元素都是一个单链表的头节点，链表是用来解决哈希冲突的，也就是说如果不同的key值映射到了同一个数组索引（内存地址），就会把新的Entry值（键值对）插入到单链表中，并将新的Entry值的next域指向旧的Entry值（新的Entry值总会插入到头结点的位置），从而形成一条链表。所以当发生哈希冲突，访问到同一个数组索引时，我们可以通过遍历该单链表找到我们需要的值。

影响HashMap性能的原因是什么？

（1）计算key的hash值时，hash()和hashcode()算法要足够好，由于hashcode()是native层的方法，所以几乎不存在性能的问题，而hash()方法全部是基于位运算的，所以也是高性能的。如果hashcode()或者hash()算法不够好，将导致大量的哈希冲突，这样将导致哈希表退化成几个链表，这样对数据的访问无异于遍历单链表，效率是极低的。

（2）通过key的hash值计算数组索引（内存地址）的算法要足够好，HashMap的数组索引算法是hash值和数组长度进行位与运算得出数组下标索引（ hash & (length - 1) ），可以直接通过数组下标索引访问数组，效率也是相当高的。

（3）要设置合理的初始大小 initialCapacity 和负载因子 loadFactor，负载因子过大会导致HashMap产生大量的hash冲突，影响索引的效率，而且不合理的初始容量和负载因子会导致HashMap频繁发生扩容操作，影响性能。

HashTable

HashTable底层是基于哈希表实现，是线程安全的，默认初始化容量为11，采用单链表解决冲突。

HashTable内部是如何组织哈希表的呢？ 

（1）计算key的hash值：直接调用Object类的hashcode()方法得到hash值。

（2）计算hash值对应的数组索引：采用取模运算（即除法散列法）。通过hash值对数组长度进行取模，具体计算方式：(hash & 0x7FFFFFFF) % length。（&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变）

ArrayList与LinkedList的区别

1、ArrayList底层是动态数组，LinkedList底层是双向循环链表，根据其底层数据结构的特性，ArrayList适合频繁读取查询数据的操作，LinkedList适合频繁插入和删除数据的操作。

2、ArrayList进行数组扩容的时候需要拷贝旧数组到新的数组中，是比较消耗性能的操作，而LinkedList扩容时只需要改变指针的方向即可扩容，性能相对比较高；所以在事先能确定元素数量的情况下，建议使用ArrayList。

HashMap与HashTable的区别

1、HashMap是非线程安全的，HashTable是线程安全的。

2、HashMap允许有null的键和值，HashTable不允许有null的键和值。

3、在单线程的环境下，HashMap效率比HashTable高。

4、计算key的hash算法不同：HashMap调用内部的hash()方法，HashTable直接调用Object类的hashcode()方法。

5、计算hash值到内存索引的映射算法不同：HashMap采用位运算，HashTable采用取模运算（即除法散列法）；取模运算会用到除法，所以效率会比HashMap。

6、HashMap要求数组实际容量大小为2的整数次幂，而HashTable则不要求。