经常被问到的有深度有内涵的数据结构面试题

数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。

Java工具包提供了强大的数据结构，在开发中一般都离不开Java集合框架，主要包括Collection和Map两个主要接口，而程序中最终使用的数据结构是继承自这两个接口的数据结构类。

Java集合框架

从上面的Java集合框架图可以看到，主要分为Set、 List、Queue和Map四大体系，然而有很多开发者理不清他们之间的区别和联系，特别是对于一些小白来说如意混淆。这也是Java习惯工作面试时经常被考的知识点，那么我们今天来一起温习一下。

List接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为ArrayList和LinkedList，另外还有不常用的Vector。同时LinkedList还是实现了Queue接口，因此也可以作为队列使用。

List接口

Set接口通常表示一个集合，其中的元素不允许重复（通过hashcode和equals方法保证），常用实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap实现的，而TreeSet是通过Map中的TreeMap实现的。另外，TreeSet还实现了SortedSet接口，因此是有序的集合。

Set接口

Queue接口通常表示一个队列，是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

Map是一个映射接口，其中的每个元素都是一个key-value键值对。

Map接口

小编一般都是这样来理解记忆其大致区别的：

Set代表无序、不可重复的集合，

List代表有序、重复的集合，

Map代表具有映射关系的集合，

Queue代表一种队列集合。

关于集合框架的内容特别多，这里就不一一进行说明，后续再逐一分解，今天先来一起温习一下有关Java集合框架有关的面试题。

ArrayList和LinkedList的区别？

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

4.查找操作indexOf,lastIndexOf,contains等，两者差不多。

5.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

ArrayList的扩容机制如何？

如果在初始化ArrayList的时候没有指定初始化长度的话，默认的长度为10。在增加新元素的时候如果超过了原始的容量的话，新容量=原始容量*3/2+1。

这个问题非常简单，稍微看一下源码就知道了。

1. public void ensureCapacity(int minCapacity) {
2. modCount++;
3. int oldCapacity = elementData.length;
4. if (minCapacity > oldCapacity) {
5. Object oldData[] = elementData;
6. int newCapacity = (oldCapacity * 3)/2 + 1;
7. if (newCapacity < minCapacity)
8. newCapacity = minCapacity;
9. // minCapacity is usually close to size, so this is a win:
10. elementData = Arrays.copyOf(elementData, newCapacity);
11. }
12. }

Vector和ArrayList的区别？

相同之处：

1.它们都是List

2.它们都实现了RandomAccess和Cloneable接口，都支持快速随机访问，能克隆自己。

3.它们都是通过数组实现的，本质上都是动态数组。

4.它们的默认数组容量是10。

5.它们都支持Iterator和listIterator遍历。

不同之处：

1.线程安全性不一样。ArrayList是非线程安全的，而Vector是线程安全的； ArrayList适用于单线程，Vector适用于多线程。

2.对序列化支持不同。ArrayList支持序列化，而Vector不支持。

3.构造方法个数不同。ArrayList有3个构造方法，而Vector有4个构造方法。Vector除类似的3个构造方法之外，另外的一个构造方法可以指定容量增加系数。

4.容量增加方式不同。逐个添加元素时，若ArrayList容量不足时，“新的容量”=“(原始容量x3)/2 + 1”。而Vector的容量增长与“增长系数有关”，若指定了“增长系数”，且“增长系数有效(即，大于0)”；那么，每次容量不足时，“新的容量”=“原始容量+增长系数”。若增长系数无效(即，小于/等于0)，则“新的容量”=“原始容量 x 2”。

5.对Enumeration的支持不同。Vector支持通过Enumeration去遍历，而List不支持。

Set 和List的区别？

1.List和Set都是继承自Collection接口。

2.List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的） 。

3.List接口有三个实现类：LinkedList，ArrayList，Vector ，Set接口有两个实现类：HashSet(底层由HashMap实现)，LinkedHashSet。

HashMap和HashSet的区别。

1.HashMap实现了Map接口，HashSet实现了Set接口。

2.HashMap储存键值对，HashSet仅仅存储对象（且无重复对象）。

3.HashMap使用put()方法将元素放入map中，HashSet使用add()方法将元素放入set中。

4.HashMap中使用键对象来计算hashcode值，HashSet使用成员对象来计算hashcode值。对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false。

5.HashMap比较快，因为是使用唯一的键来获取对象；HashSet比HashMap来说更慢。

HashMap与HashTable的区别？

1.HashTable的方法是同步的，HashMap未经同步，所以HashMap效率更高。

2.HashTable不允许null值(key和value都不可以)，HashMap允许null值(key和value都可以)。

3.HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样，HashMap没有contains方法。

4.HashTable使用Enumeration，HashMap使用Iterator。

5.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

6.哈希值的使用不同，HashTable直接使用对象的hashCode。

HashMap的工作原理？HashMap的get()方法的工作原理？

“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”

这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确，也显示出面试者确实知道hashing以及HashMap的工作原理。

1. public V put(K key, V value) {
2. if (key == null)
3. return putForNullKey(value); //null总是放在数组的第一个链表中
4. int hash = hash(key.hashCode());
5. int i = indexFor(hash, table.length);
6. //遍历链表
7. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
8. Object k;
9. //如果key在链表中已存在，则替换为新value
10. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
11. V oldValue = e.value;
12. e.value = value;
13. e.recordAccess(this);
14. return oldValue;
15. }
16. }
17. modCount++;
18. addEntry(hash, key, value, i);
19. return null;
20. }
21. public V get(Object key) {
22. if (key == null)
23. return getForNullKey();
24. int hash = hash(key.hashCode());
25. //先定位到数组元素，再遍历该元素处的链表
26. for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
27. Object k;
28. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
29. return e.value;
30. }
31. return null;
32. }

当两个对象的hashcode相同会发生什么？

从这里开始，真正的困惑开始了，一些面试者会回答因为hashcode相同，所以两个对象是相等的，HashMap将会抛出异常，或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法，并告诉他们两个对象就算hashcode相同，但是它们可能并不相等。一些面试者可能就此放弃，而另外一些还能继续挺进，他们回答“因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理，虽然有很多种处理碰撞的方法，这种方法是最简单的，也正是HashMap的处理方法。

但故事还没有完结，面试官会继续问：

如果两个键的hashcode相同，你如何获取值对象？

面试者会回答：当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket，他给出答案：将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较，你是如何确定确定找到值对象的？除非面试者直到HashMap在链表中存储的是键值对，否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。完美的答案！

许多情况下，面试者会在这个环节中出错，因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现，而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

如果你认为到这里已经完结了，那么听到下面这个问题的时候，你会大吃一惊。

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。如果你能够回答这道问题，下面的问题来了：

你了解重新调整HashMap大小存在什么问题吗？

你可能回答不上来，这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）

为什么String、 Interger这样的wrapper类适合作为键？

String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

我们可以使用自定义的对象作为键吗？

这是前一个问题的延伸。当然你可能使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

我们可以使用CocurrentHashMap来代替Hashtable吗？

这是另外一个很热门的面试题，因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。

Collection和Collections的区别。

Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法。

Collections 是一个包装类，它包含有各种有关集合操作的静态多态方法，此类不能实例化。

a.hashCode() 有什么用？与 a.equals(b) 有什么关系？

hashCode() 方法是相应对象整型的 hash 值。它常用于基于 hash 的集合类，如 Hashtable、HashMap、LinkedHashMap等等。它与 equals() 方法关系特别紧密。根据 Java 规范，两个使用 equal() 方法来判断相等的对象，必须具有相同的 hash code。

为什么在重写 equals 方法的时候需要重写 hashCode 方法？

因为有强制的规范指定需要同时重写 hashcode 与 equal 是方法，许多容器类，如 HashMap、HashSet 都依赖于 hashcode 与 equals 的规定。