-
ArrayList的扩容机制
以无参构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {};因为在源代码中，int newCapacity = oldCapacity + (oldCapacity >> 1)，所以ArrayList每次扩容之后容量都会变为原来的1.5倍。
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); }
如果minCapacity大于大容量，则新容量为Integer.MAX_VALUE，否则新容量大小为MAX_ARRAY_SIZE，即为Integer.MAX_VALUE - 8。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
-
ArrayList和Vector的区别是什么？为什么要用ArrayList取代Vector？
- Vector类的索引方法都是同步的。可以有两个线程安全地访问一个Vector对象，但是一个线程访问Vector的话代码要在同步操作上耗费大量时间。
- ArrayList不是同步的，所以不需要保证线程安全时建议使用ArrayList
-
ArrayList与LinkedList的区别？
- 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全
- 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到）
- 插入和删除是否首元素位置的影响：① ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList会默认在指定的元素追加到此列表的末尾，这种情况的时间复杂度就是O(1)。但是如果要在指定位置i插入和删除元素的话(add ( int index, E element))时间复杂度就是O(n-i)。因为在进行上述操作的时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。② LinkedList采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似O(1)，如果是要在指定位置i插入和删除元素的话，(add ( int index, E element))时间复杂度近似为O(n)，因为需要先移动到指定位置再插入。
- 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于get(int index) 方法）。
- 内存空间占用：ArrayList的空间浪费主要体现在 在list列表的结尾会预留一定的容量空间，而LinkedList的容量空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
-
HashMap与Hashtable的区别
- 线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的；Hashtable内部的方法基本都经过synchronized修饰。（如果一定要保证线程安全的话可以使用ConcurrentHash）；
- 效率：因为线程安全的问题，HashMap要比Hashtable效率高一点。另外，Hashtable基本被淘汰，不要在代码中使用它；
- 对 Null key 和 Null value 的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。但是在Hashtable中put进的键值只要有一个null，就直接抛出 NullPointerException。
- 初始容量大小和每次扩容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩容，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。② 创建时如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说HashMap总是使用2的幂次方作为哈希表的大小。
- 底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转换为红黑树，以减少搜索时间。Hashtable没有这样的机制。
-
List、Set、Map三者的区别
- List（有序、重复）：List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
- Set（无序、不重复）：不允许重复的集合。不会有多个元素引用相同的对象。
- Map（KV键值对集合）：使用键值对来存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象。但Key不能重复，典型的Key是String类型，但也可以是任何对象。
-
RandomAccess接口
public interface RandomAccess { }通过查看源码可以发现实际上RandomAccess接口中什么都没有定义。所以我认为RandomAccess接口只是一个标识，标识实现这个接口的类具有随机访问功能。
在binarySearch( ) 方法中，它要判断传入的list是否为RandomAccess接口的实现类的实例，如果是，调用indexBinarySearch( )方法，如果不是，则调用iteratorBinarySearch( )方法。
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }ArrayList实现了RandomAccess接口，而LinkedList没有实现。是什么原因？
我认为还是与底层数据结构有关。ArrayList底层是数组，而LinkedList底层是链表。数组天然支持随机访问，时间复杂度为O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问到特定位置的元素，时间复杂度为O(n)，所以不支持快速随机访问。ArrayList实现了RandomAccess接口，就表明了他具有快速随机访问功能。RandomAccess接口只是标识，并不是说ArrayList实现RandomAccess接口才具有快速随机访问功能的！
