Java_集合面试题

Java_集合面试题

0.链表，队列和栈的区别?

• 链表是一种存储结构，指得是存储时候除了要存储数据元素之外，还要用数据元素一起的另外空间存储数据元素的关系。
• 队列和栈都是线性表，属于逻辑结构范畴，都是访问点受到限制，并且限制在线性表端点的线性表。
• 栈被限定为在线性表中的同一个（唯一一个的）端点插入删除
• 队列被限定为在线性表的一端插入，另外一个端点删除
• 栈和队列也可以用链表来实现，分别称为链栈和链队列

1. ArrayList

• ArrayList是基于数组实现的，最大长度不会超过数组的长度2147483647(最大值是int的最大值是,2的31次方减去1 ).如果业务中可能存在超过这个长度的数据,使用LinkedArrayList

3.HashMap

Java中的HashMap是以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

4.HashMap和HashTable的区别?

1. >继承不同。 public class Hashtable extends Dictionary implements Map public class HashMap extends AbstractMap implements Map
2. >Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。
3. >Hashtable中，key和value都不允许出现null值。在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
4. > 两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
5. >哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
6. >Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

5.Java集合类里面最基本的接口有：

1. Collection：代表一组对象，每一个对象都是它的子元素。
2. Set：不包含重复元素的Collection。
3. List：有顺序的collection，并且可以包含重复元素。
4. Map：可以把键(key)映射到值(value)的对象，键不能重复。

6.什么是迭代器(Iterator)？

Iterator接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素。

7.Iterator和ListIterator的区别是什么？

1. Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。
2. Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
3. ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

8.Enumeration接口和Iterator接口的区别有哪些？

Enumeration速度是Iterator的2倍，同时占用更少的内存。但是，Iterator远远比Enumeration安全，因为其他线程不能够修改正在被iterator遍历的集合里面的对象。同时，Iterator允许调用者删除底层集合里面的元素，这对Enumeration来说是不可能的。

9.快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

1. fail-fast机制在遍历一个集合时，当集合结构被修改，会抛出Concurrent Modification Exception。 > fail-fast会在以下两种情况下抛出ConcurrentModificationException : >> 1. 单线程环境:集合被创建后，在遍历它的过程中修改了结构。 >>>> <font color=red size=2>注意 remove()方法会让expectModcount和modcount 相等，所以是不会抛出这个异常。</font> >> 2. 多线程环境: 当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改。 >>> <font color=red size=2>注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测 bug。</font> > fail-fast机制是如何检测的? >> 迭代器在遍历过程中是直接访问内部数据的，因此内部的数据在遍历的过程中无法被修改。为了保证不被修改，迭代器内部维护了一个标记 “mode” ，当集合结构改变（添加删除或者修改），标记"mode"会被修改，而迭代器每次的hasNext()和next()方法都会检查该"mode"是否被改变，当检测到被修改时，抛出Concurrent Modification Exception

2. fail-safe任何对集合结构的修改都会在一个复制的集合上进行修改，因此不会抛出ConcurrentModificationException > * fail-safe机制有两个问题 > 1. 需要复制集合，产生大量的无效对象，开销大 > 2. 无法保证读取的数据是目前原始数据结构中的数据。

10.ArrayList和LinkedList有什么区别？

ArrayList和LinkedList都实现了List接口，他们有以下的不同点： 1. ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。 2. 相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。

1. LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

11.什么是Java优先级队列(Priority Queue)？

• PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个*队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。
• 优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。
• 优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象
• 优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
• PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。

<font color=red size=2>说明：有界队列是一种特殊队列，当队列为空时，队列的获取操作将会阻塞获取线程，直到队列中有新增元素；当队列已满时，队列的插入操作会阻塞插入线程，直到队列中出现空位。 *队列与有界队列相比，除非系统资源耗尽，否则*的任务队列不存在任务入队失败的情况。 </font>

12.Java集合类框架的最佳实践有哪些？

1. 根据应用的需要正确选择要使用的集合的类型对性能非常重要，比如：假如元素的大小是固定的，而且能事先知道，我们就应该用Array而不是ArrayList。

2. 有些集合类允许指定初始容量。因此，如果我们能估计出存储的元素的数目，我们可以设置初始容量来避免重新计算hash值或者是扩容。

3. 为了类型安全，可读性和健壮性的原因总是要使用泛型。同时，使用泛型还可以避免运行时的ClassCastException。

4. 使用JDK提供的不变类(immutable class)作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。

5. 编程的时候接口优于实现。

6. 底层的集合实际上是空的情况下，返回长度是0的集合或者是数组，不要返回null。

13.HashSet和TreeSet有什么区别？

1. HashSet是由一个hash表来实现的，因此，它的元素是无序的。add()，remove()，contains()方法的时间复杂度是O(1)。

2. 另一方面，TreeSet是由一个树形的结构来实现的，它里面的元素是有序的。因此，add()，remove()，contains()方法的时间复杂度是O(logn)。

14.TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

• TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。
• TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。
• Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

15.ArrayList和Vector的区别

这两个类都实现了List接口（List接口继承了Collection接口），他们都是有序集合，即存储在这两个集合中的元素的位置都是有顺序的，相当于一种动态的数组，我们以后可以按位置索引号取出某个元素，并且其中的数据是允许重复的，这是与HashSet之类的集合的最大不同处，HashSet之类的集合不可以按索引号去检索其中的元素，也不允许有重复的元素。 * ArrayList与Vector的区别主要包括两个方面：. 1. 同步性：Vector是线程安全的，也就是说是它的方法之间是线程同步的，而ArrayList是线程序不安全的，它的方法之间是线程不同步的。如果只有一个线程会访问到集合，那最好是使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问到集合，那最好是使用Vector，因为不需要我们自己再去考虑和编写线程安全的代码。 2. 数据增长：ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，不是只增加一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。Vector默认增长为原来两倍，而ArrayList的增长策略在文档中没有明确规定（从源代码看到的是增长为原来的1.5倍）。ArrayList与Vector都可以设置初始的空间大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。

总结：即Vector增长原来的一倍，ArrayList增加原来的0.5倍。