java-基础-集合问题

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的区别。

<a target="_blank" href="http://blog.csdn.net/xuefeng0707/article/details/40834595">http://blog.csdn.net/xuefeng0707/article/details/40834595</a>

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的作用？什么时候需要重写？如何解决哈希冲突？查找的时候流程是如何？

<a target="_blank" href="http://blog.csdn.net/codeemperor/article/details/51351247">从源码分析HashMap</a>

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

<a target="_blank" href="http://m.blog.csdn.net/article/details?id=48956087">http://m.blog.csdn.net/article/details?id=48956087</a>

<a target="_blank" href="http://hovertree.com/h/bjaf/2jdr60li.htm">http://hovertree.com/h/bjaf/2jdr60li.htm</a>

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

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

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

<a target="_blank" href="http://blog.csdn.net/lolashe/article/details/20806319">http://blog.csdn.net/lolashe/article/details/20806319</a>

Collection包结构，与Collections的区别。

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

Set、List之间的区别是什么?

<a target="_blank" href="http://developer.51cto.com/art/201309/410205_all.htm">http://developer.51cto.com/art/201309/410205_all.htm</a>

Map、Set、List、Queue、Stack的特点与用法。

<a target="_blank" href="http://www.cnblogs.com/yumo/p/4908718.html">http://www.cnblogs.com/yumo/p/4908718.html</a>

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等。