Java集合QA

ArrayList、LinkedList、Vector 的底层实现和区别

• 从同步性来看，ArrayList 和 LinkedList 是不同步的，而 Vector 是的。所以线程安全的话，可以使用 ArrayList 或 LinkedList，可以节省为同步而耗费的开销。但在多线程下，有时候就不得不使用 Vector 了。当然，也可以通过一些办法包装 ArrayList、LinkedList，使我们也达到同步，但效率可能会有所降低。

• 从内部实现机制来讲 ArrayList 和 Vector 都是使用 Object 的数组形式来存储的。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector 缺省情况下自动增长原来一倍的数组长度，ArrayList 是原来的 50%，所以最后你获得的这个集合所占的空间总是比你实际需要的要大。如果你要在集合中保存大量的数据，那么使用 Vector 有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

• ArrayList 和 Vector 中，从指定的位置（用 index）检索一个对象，或在集合的末尾插入、删除一个对象的时间是一样的，可表示为 O(1)。但是，如果在集合的其他位置增加或者删除元素那么花费的时间会呈线性增长 O(n-i)，其中 n 代表集合中元素的个数，i 代表元素增加或移除元素的索引位置，因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的所有元素都要执行 (n-i) 个对象的位移操作。LinkedList 底层是由双向循环链表实现的，LinkedList 在插入、删除集合中任何位置的元素所花费的时间都是一样的 O(1)，但它在索引一个元素的时候比较慢，为 O(i)，其中 i 是索引的位置，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用 Vector 或 ArrayList 都可以。如果是对其它指定位置的插入、删除操作，最好选择 LinkedList。

---

HashMap 和 HashTable 的底层实现和区别，两者和 ConcurrentHashMap 的区别。

http://blog.csdn.net/xuefeng0707/article/details/40834595

HashTable 线程安全则是依靠方法简单粗暴的 sychronized 修饰，HashMap 则没有相关的线程安全问题考虑。。

在以前的版本貌似 ConcurrentHashMap 引入了一个 “分段锁” 的概念，具体可以理解为把一个大的 Map 拆分成 N 个小的 HashTable，根据 key.hashCode() 来决定把 key 放到哪个 HashTable 中。在 ConcurrentHashMap 中，就是把 Map 分成了 N 个 Segment，put 和 get 的时候，都是现根据 key.hashCode() 算出放到哪个 Segment 中。
通过把整个 Map 分为 N 个 Segment（类似 HashTable），可以提供相同的线程安全，但是效率提升 N 倍。

---

HashMap 的 hashcode 的作用？什么时候需要重写？如何解决哈希冲突？查找的时候流程是如何？

从源码分析 HashMap

---

Arraylist 和 HashMap 如何扩容？负载因子有什么作用？如何保证读写进程安全？

http://m.blog.csdn.net/article/details?id=48956087
http://hovertree.com/h/bjaf/2jdr60li.htm

ArrayList 本身不是线程安全的。 所以正确的做法是去用 java.util.concurrent 里的 CopyOnWriteArrayList 或者某个同步的 Queue 类。

HashMap 实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来 “包装” 该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问.

---

TreeMap、HashMap、LinkedHashMap 的底层实现区别。

http://blog.csdn.net/lolashe/article/details/20806319

---

Collection 包结构，与 Collections 的区别。

Collection 是一个接口，它是 Set、List 等容器的父接口；Collections 是一个工具类，提供了一系列的静态方法来辅助容器操作，这些方法包括对容器的搜索、排序、线程安全化等等。

---

Set、List 之间的区别是什么?
http://developer.51cto.com/art/201309/410205_all.htm

---

Map、Set、List、Queue、Stack 的特点与用法。
http://www.cnblogs.com/yumo/p/4908718.html
Collection 是对象集合， Collection 有两个子接口 List 和 Set
List 可以通过下标 (1,2..) 来取得值，值可以重复
而 Set 只能通过游标来取值，并且值是不能重复的
ArrayList ， Vector ， LinkedList 是 List 的实现类
ArrayList 是线程不安全的， Vector 是线程安全的，这两个类底层都是由数组实现的
LinkedList 是线程不安全的，底层是由链表实现的
Map 是键值对集合
HashTable 和 HashMap 是 Map 的实现类HashTable 是线程安全的，不能存储 null 值HashMap 不是线程安全的，可以存储 null 值
Stack 类：继承自 Vector，实现一个后进先出的栈。提供了几个基本方法，push、pop、peak、empty、search 等。
Queue 接口：提供了几个基本方法，offer、poll、peek 等。已知实现类有 LinkedList、PriorityQueue 等。