2、容器——Java 面试题答案

容器

18. java 容器都有哪些？

常用容器的图录：

18. java 容器都有哪些？

常用容器的图录：

19. Collection 和 Collections 有什么区别？

• java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
• Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。稍微举个例子：

public static void main(String args[]) {   
       //注意List是实现Collection接口的   
       List list = new ArrayList();   
       double array[] = { 112, 111, 23, 456, 231 };   
       for (int i = 0; i < array.length; i++) {   
           list.add(new Double(array[i]));   
       }   
       Collections.sort(list);   //把list按从小到大排序
       for (int i = 0; i < array.length; i++) {   
           System.out.println(list.get(i));   
       }   
       // 结果：23.0 111.0 112.0 231.0 456.0   
 }   
           

然后Collections还有混排（Shuffling）、反转（Reverse）、替换所有的元素（fill）、拷贝（copy）、返回Collections中最小元素（min）、返回Collections中最大元素（max）、返回指定源列表中最后一次出现指定目标列表的起始位置（lastIndexOfSubList）、返回指定源列表中第一次出现指定目标列表的起始位置（IndexOfSubList）、根据指定的距离循环移动指定列表中的元素（Rotate）等方法。

20. List、Set、Map 之间的区别是什么？

比较	List	Set	Map
继承接口	Collection	Collection
常见实现类	AbstractList（其常见子类有ArrayList、LinkedList、Vector）	AbstractSet（其常见子类有HashSet、LinkedHashSet、TreeSet）	HashMap、HashTable
常见方法	add()、remove()、clear()、get()、contains()、size()	add()、remove()、clear()、get()、contains()、size()	put()、get()、remove()、clear()、containsKey()、containsValue()、keySet()、values()、size()
元素	可重复	不可重复（用equals()判断）	不可重复
顺序	有序	无序（实际上由HashCode决定）
线程安全	Vector安全	HashTable安全

21. HashMap 和 Hashtable 有什么区别？

• HashMap去掉了HashTable 的contains方法，但是加上了containsValue（）和containsKey（）方法。
• HashTable是同步的，而HashMap是非同步的，效率上比HashTable要高。
• HashMap允许空键值，而HashTable不允许。

Hashtable	HashMap
方法是同步的	方法是非同步的
基于Dictionary类	基于AbstractMap，而AbstractMap基于Map接口的实现
key和value都不允许为null，遇到null，直接返回 NullPointerException	key和value都允许为null，遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理
hash数组默认大小是11，扩充方式是old*2+1	hash数组的默认大小是16，而且一定是2的指数

更详细的介绍可以参考博客HashTable和HashMap的区别详解

HashMap和TreeMap区别详解以及底层实现

22. 如何决定使用 HashMap 还是 TreeMap？

TreeMap<K,V>的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现也是基于红黑树结构。

而HashMap<K,V>的Key值实现散列hashCode(),分布是散列的均匀的，不支持排序；数据结构主要是桶(数组),链表或红黑树。

大多情况下HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。

23. 说一下 HashMap 的实现原理？

HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构： 在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（链表），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根绝hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。

需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

24. 说一下 HashSet 的实现原理？

HashSet底层由HashMap实现

HashSet的值存放于HashMap的key上

HashMap的value统一为PRESENT

25. ArrayList 和 LinkedList 的区别是什么？

最明显的区别是 ArrrayList底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。

26. 如何实现数组和 List 之间的转换？

List转换成为数组：调用ArrayList的toArray()方法。

数组转换成为List：调用Arrays.asList()方法。

27. ArrayList 和 Vector 的区别是什么？

参考这篇博客arrayList和vector的区别

首先看这两类都实现List接口，而List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。List用于存放多个元素，能够维护元素的次序，并且允许元素的重复。3个具体实现类的相关区别如下：

• ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
• Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
• LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。
• vector是线程（Thread）同步（Synchronized）的，所以它也是线程安全的，而Arraylist是线程异步（ASynchronized）的，是不安全的。如果不考虑到线程的安全因素，一般用Arraylist效率比较高。
• 如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。
• 如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是O(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为O(n-i)n为总长度，这个时候就应该考虑到使用Linkedlist,因为它移动一个指定位置的数据所花费的时间为O(1),而查询一个指定位置的数据时花费的时间为0(i)。

• ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动 等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

  笼统来说：LinkedList：增删改快； ArrayList：查询快（有索引的存在）

28. Array 和 ArrayList 有何区别？

• Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
• Array是指定大小的，而ArrayList大小是固定的。 （在Java集合框架中的大部分类的大小是可以随着元素个数的增加而相应的增加的，我们一般不用关心它的初始大小,除非考虑性能问题时）
• Array没有提供ArrayList那么多功能，比如addAll()、removeAll()和iterator()等。

29. 在 Queue 中 poll()和 remove()有什么区别？

poll()和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

peek()只取但不删除队首元素。

30. 哪些集合类是线程安全的？

Vector：就比ArrayList多了个同步化机制（线程安全），因为效率较低，现在已经不太建议使用。在web应用中，特别是前台页面，往往效率（页面响应速度）是优先考虑的。

HashTable：就比HashTable多了个线程安全。

Statck：堆栈类，先进后出。

Enumeration：枚举，相当于迭代器。

31. 迭代器 Iterator 是什么？

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

32. Iterator 怎么使用？有什么特点？

Java中的Iterator功能比较简单，并且只能单向移动：

(1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法是java.lang.Iterable接口,被Collection继承。

(2) 使用next()获得序列中的下一个元素。

(3) 使用hasNext()检查序列中是否还有元素。

(4) 使用remove()将迭代器新返回的元素删除。

Iterator是Java迭代器最简单的实现，为List设计的ListIterator具有更多的功能，它可以从两个方向遍历List，也可以从List中插入和删除元素。

33. Iterator 和 ListIterator 有什么区别？

Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。

Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。

ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素add()，替换元素set()，获取前一个和后一个元素或索引next()/nextIndex()、previous()/previousIndex()，等等。

34.怎么确保一个集合不能被修改

怎么确保一个集合不能被修改

我们很容易想到用final关键字进行修饰，我们都知道：

final关键字可以修饰类，方法，成员变量，final修饰的类不能被继承，final修饰的方法不能被重写，final修饰的成员变量必须初始化值，如果这个成员变量是基本数据类型，表示这个变量的值是不可改变的，如果说这个成员变量是引用类型，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变的。

那么，我们怎么确保一个集合不能被修改？首先我们要清楚，集合（map,set,list…）都是引用类型，所以我们如果用final修饰的话，集合里面的内容还是可以修改的。

我们可以做一个实验：

可以看到：我们用final关键字定义了一个map集合，这时候我们往集合里面传值，第一个键值对1,1；我们再修改后，可以把键为1的值改为100，说明我们是可以修改map集合的值的。

那我们应该怎么做才能确保集合不被修改呢？

我们可以采用Collections包下的unmodifiableMap方法，通过这个方法返回的map,是不可以修改的。他会报java.lang.UnsupportedOperationException错。

同理：Collections包也提供了对list和set集合的方法：

Collections.unmodifiableList(List)

Collections.unmodifiableSet(Set)

35.如何获取Map中的所有元素

原理：Map没有迭代器，Collection具备迭代器，只要将Map转成Set集合，就可使用迭代器。之所以转成Set，是因为Map集合具备键的唯一性，其实Set集合就来自于Map，Set集合底层其实用的就是Map的方法。

把Map集合转成Set的方法：(决定了两种遍历方式)

• Set keySet();

• Set entrySet();//取的是键和值的映射关系。 Entry就是Map接口中的内部接口；

  为什么要定义在Map内部呢？Entry是访问键值关系的入口，是Map的入口，访问的是Map中的键值对。

  取出map集合中所有元素的方式一：keySet()方法。

可以将map集合中的键都取出存放到set集合中。对set集合进行迭代。迭代完成，再通过get方法对获取到的键进行值的获取。

Set keySet = map.keySet();
Iterator it = keySet.iterator();
while(it.hasNext()) {
	Object key = it.next();
	Objectvalue = map.get(key);
	System.out.println(key+":"+value);  
}   
           

取出map集合中所有元素的方式二：entrySet()方法。

Set entrySet = map.entrySet();
Iterator it =entrySet.iterator();
while(it.hasNext()) {
    Map.Entry  me =(Map.Entry)it.next();
    System.out.println(me.getKey()+"::::"+me.getValue());
}
           

使用集合的技巧：

• 看到Array就是数组结构，有角标，查询速度很快。
• 看到Link就是链表结构：增删速度快，而且有特有方法。addFirst()； addLast()；removeFirst()； removeLast()；getFirst()；getLast()；
• 看到Hash就是哈希表，就要想要哈希值，就要想到唯一性，就要想到存入到该结构中的元素必须覆盖hashCode和equals方法。
• 看到Tree就是二叉树，就要想到排序，就想要用到比较。

*比较的两种方式：

- 一个是Comparable：覆盖compareTo方法；

- 一个是Comparator：覆盖compare方法。

集合部分更多题目：

Java集合面试总结