2.2 Java 容器
-
ArrayList、LinkedList、Vector 区别？
1 ArrayList和LinkedList的区别：
（1）相同点：
LinkedeList和ArrayList都实现了List接口。
ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。
（2）不同点：ArrayList底层的实现数组，而LinkedList是双向链表。
ArrayList进行随机访问所消耗的时间是固定的，因此随机访问时效率比较高。
LinkedList是不支持快速的随机访问的，但是在插入删除时效率比较高。2 ArrayList和Vector的区别：
（1）相同点：ArrayList和Vector都是用数组实现的。
默认初始化大小都是10
（2）不同点Vector多线程是安全的，而ArrayList不是。Vector类中的方法很多有synchronized进行修饰，这样就导致了Vector在效率上无法与ArrayList相比；
两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同的。（ArrayList每次存储时会检查空间大小，不够时会扩充为原来的1.5倍，Vector会扩充为原来空间的2倍） -
HashMap、LinkedHashMap、Hashtable、TreeMap 区别、源码？
1）HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为null，不允许多条记录的值为null。HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要同步，可以用Collections.synchronizedMap(HashMap map)方法使HashMap具有同步的能力。
2）Hashtable与HashMap类似，不同的是：它不允许记录的键或者值为空；它支持线程的同步，即任一时刻只有一个线程能写Hashtable，然而，这也导致了Hashtable在写入时会比较慢。
3）LinkedHashMap保存了记录的插入顺序，在用Iteraor遍历LinkedHashMap时，先得到的记录肯定是先插入的。在遍历的时候会比HashMap慢。有HashMap的全部特性。
4）TreeMap能够把它保存的记录根据键排序，默认是按升序排序，也可以指定排序的比较器。当用Iteraor遍历TreeMap时，得到的记录是排过序的。TreeMap的键和值都不能为空。 -
List、Set、Map 区别？
List：
1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。Set：
1.不允许重复对象
2.无序容器，你无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。- 只允许一个 null 元素
4.Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap 实现的 HashSet；TreeSet 还实现了 SortedSet 接口，因此 TreeSet 是一个根据其 compare() 和 compareTo() 的定义进行排序的有序容器。而且可以重复
Map
1.Map不是collection的子接口或者实现类。Map是一个接口。
2.Map 的 每个 Entry 都持有两个对象，也就是一个键一个值，Map 可能会持有相同的值对象但键对象必须是唯一的。- TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序。
- Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
5.Map 接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。（HashMap、TreeMap最常用）
- 只允许一个 null 元素
-
说说 ConcurrentHashMap？
ConcurrentHashMap的总结：比起Segment，锁拆的更细
1.首先使用无锁操作CAS插入头结点，失败则循环重试
2.若头结点已经存在，则尝试获取头结点的同步锁，再进行操作
-
ArrayList 扩容机制？
1.5
-
说说 ArrayList 源码中 ensureCapacity() 作用吧？
对于ArrayLis中有一个方法ensureCapacity(int n),这个方法可以对ArrayList低层的数组进行扩容，显示的调用这个函数，如果参数大于低层数组长度的1.5倍，那么这个数组的容量就会被扩容到这个参数值，如果参数小于低层数组长度的1.5倍，那么这个容量就会被扩容到低层数组长度的1.5倍。说这么多，总而言之，记住这个函数可以对低层数组扩容就行了，在适当的时机，好好利用这个函数，将会使我们写出来的程序性能得到提升例如如下两段代码
-
HashMap 的长度为什么是 2 的幂次方？
- 这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方；
- 这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
-
comparable 和 Comparator 的区别?
Comparable 简介
Comparable 是排序接口。
若一个类实现了Comparable接口，就意味着“该类支持排序”。此外，“实现Comparable接口的类的对象”可以用作“有序映射(如TreeMap)”中的键或“有序集合(TreeSet)”中的元素，而不需要指定比较器。
接口中通过x.compareTo(y)来比较x和y的大小。若返回负数，意味着x比y小；返回零，意味着x等于y；返回正数，意味着x大于y。Comparator 简介
Comparator 是比较器接口。我们若需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)；那么，我们可以建立一个“该类的比较器”来进行排序。这个“比较器”只需要实现Comparator接口即可。也就是说，我们可以通过“实现Comparator类来新建一个比较器”，然后通过该比较器对类进行排序。int compare(T o1, T o2)和上面的x.compareTo(y)类似，定义排序规则后返回正数，零和负数分别代表大于，等于和小于。
两者的联系
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。