转载

java面试题-集合类

准备年后要跳槽，所以最近一直再看面试题，并且把收集到的面试题整理了以下发到博客上，希望对大家有所帮助。

首先是集合类的面试题

1. HashMap 排序题，上机题。

已知一个 HashMap<Integer，User>集合， User 有 name（String）和 age（int）属性。请写一个方法实现对HashMap 的排序功能，该方法接收 HashMap<Integer，User>为形参，返回类型为 HashMap<Integer，User>，要求对 HashMap 中的 User 的 age 倒序进行排序。排序时 key=value 键值对不得拆散。

注意：要做出这道题必须对集合的体系结构非常的熟悉。HashMap 本身就是不可排序的，但是该道题偏偏让给HashMap 排序，那我们就得想在 API 中有没有这样的 Map 结构是有序的，LinkedHashMap，对的，就是他，他是Map 结构，也是链表结构，有序的，更可喜的是他是 HashMap 的子类，我们返回 LinkedHashMap<Integer,User>即可，还符合面向接口（父类编程的思想）。

但凡是对集合的操作，我们应该保持一个原则就是能用 JDK 中的 API 就有 JDK 中的 API，比如排序算法我们不应该去用冒泡或者选择，而是首先想到用 Collections 集合工具类。

public class HashMapTest {
public static void main(String[] args) {
HashMap<Integer, User> users = new HashMap<>();
users.put(1, new User("张三", 25));
users.put(3, new User("李四", 22));
users.put(2, new User("王五", 28));
System.out.println(users);
HashMap<Integer,User> sortHashMap = sortHashMap(users);
System.out.println(sortHashMap);
/**
* 控制台输出内容
* {1=User [name=张三, age=25], 2=User [name=王五, age=28], 3=User [name=李四, age=22]}
{2=User [name=王五, age=28], 1=User [name=张三, age=25], 3=User [name=李四, age=22]}
*/
}
public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {
// 首先拿到 map 的键值对集合
Set<Entry<Integer, User>> entrySet = map.entrySet();
// 将 set 集合转为 List 集合，为什么，为了使用工具类的排序方法
List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>>(entrySet);
// 使用 Collections 集合工具类对 list 进行排序，排序规则使用匿名内部类来实现
Collections.sort(list, new Comparator<Entry<Integer, User>>() {
@Override
public int compare(Entry<Integer, User> o1, Entry<Integer, User> o2) {
 //按照要求根据 User 的 age 的倒序进行排
 return o2.getValue().getAge()-o1.getValue().getAge();
}
});
 //创建一个新的有序的 HashMap 子类的集合
LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();
 //将 List 中的数据存储在 LinkedHashMap 中
for(Entry<Integer, User> entry : list){
linkedHashMap.put(entry.getKey(), entry.getValue());
}
 //返回结果
 return linkedHashMap;
 }
}

2. 集合的安全性问题

请问 ArrayList、HashSet、HashMap 是线程安全的吗？如果不是我想要线程安全的集合怎么办？

我们都看过上面那些集合的源码（如果没有那就看看吧），每个方法都没有加锁，显然都是线程不安全的。话又说过来如果他们安全了也就没第二问了。

在集合中 Vector 和 HashTable 倒是线程安全的。你打开源码会发现其实就是把各自核心方法添加上了synchronized 关键字。

Collections 工具类提供了相关的 API，可以让上面那 3 个不安全的集合变为安全的。

Collections.synchronizedCollection(c)
Collections.synchronizedList(list)
Collections.synchronizedMap(m)
Collections.synchronizedSet(s)

上面几个函数都有对应的返回值类型，传入什么类型返回什么类型。打开源码其实实现原理非常简单，就是将集合的核心方法添加上了 synchronized 关键字。

3. 并发集合和普通集合如何区别？

并发集合常见的有 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque 等。并发集合位于 java.util.concurrent 包下，是 jdk1.5 之后才有的，主要作者是 Doug Lea

（http://baike.baidu.com/view/3141057.htm）完成的。

在 java 中有普通集合、同步（线程安全）的集合、并发集合。普通集合通常性能最高，但是不保证多线程的安全性和并发的可靠性。线程安全集合仅仅是给集合添加了 synchronized 同步锁，严重牺牲了性能，而且对并发的效率就更低了，并发集合则通过复杂的策略不仅保证了多线程的安全又提高的并发时的效率。

参考阅读：

ConcurrentHashMap 是线程安全的 HashMap 的实现，默认构造同样有 initialCapacity 和 loadFactor 属性，不过还多了一个 concurrencyLevel 属性，三属性默认值分别为 16、0.75 及 16。其内部使用锁分段技术，维持这锁Segment 的数组，在 Segment 数组中又存放着 Entity[]数组，内部 hash 算法将数据较均匀分布在不同锁中。

put 操作：并没有在此方法上加上 synchronized，首先对 key.hashcode 进行 hash 操作，得到 key 的 hash 值。hash操作的算法和map也不同，根据此hash值计算并获取其对应的数组中的Segment对象(继承自ReentrantLock)，接着调用此 Segment 对象的 put 方法来完成当前操作。

ConcurrentHashMap 基于 concurrencyLevel 划分出了多个 Segment 来对 key-value 进行存储，从而避免每次 put 操作都得锁住整个数组。在默认的情况下，最佳情况下可允许 16 个线程并发无阻塞的操作集合对象，尽可能地减少并发时的阻塞现象。

get(key)：首先对 key.hashCode 进行 hash 操作，基于其值找到对应的 Segment 对象，调用其 get 方法完成当前操作。而 Segment 的 get 操作首先通过 hash 值和对象数组大小减 1 的值进行按位与操作来获取数组上对应位置的HashEntry。在这个步骤中，可能会因为对象数组大小的改变，以及数组上对应位置的 HashEntry 产生不一致性，那么 ConcurrentHashMap 是如何保证的？

对象数组大小的改变只有在 put 操作时有可能发生，由于 HashEntry 对象数组对应的变量是 volatile 类型的，因此可以保证如 HashEntry 对象数组大小发生改变，读操作可看到最新的对象数组大小。

在获取到了 HashEntry 对象后，怎么能保证它及其 next 属性构成的链表上的对象不会改变呢？这点ConcurrentHashMap 采用了一个简单的方式，即 HashEntry 对象中的 hash、key、next 属性都是 final 的，这也就意味着没办法插入一个HashEntry对象到基于next属性构成的链表中间或末尾。这样就可以保证当获取到HashEntry对象后，其基于 next 属性构建的链表是不会发生变化的。

ConcurrentHashMap 默认情况下采用将数据分为 16 个段进行存储，并且 16 个段分别持有各自不同的锁Segment，锁仅用于 put 和 remove 等改变集合对象的操作，基于 volatile 及 HashEntry 链表的不变性实现了读取的不加锁。这些方式使得 ConcurrentHashMap 能够保持极好的并发支持，尤其是对于读远比插入和删除频繁的 Map而言，而它采用的这些方法也可谓是对于 Java 内存模型、并发机制深刻掌握的体现。

其实关于集合的面试题我收集了很多没有办法一次性全部发出来,只是挑选了这么3道。最后推荐大家看看hashmap的源码（1.8之后的）,作为集合最常问的面试题hashmap以及底层的数组、链表和红黑树都是必须要掌握的。所谓知其然才能知其所以然就是这个意思数据结构就是一个程序员内力的体现。

原文 http://www.cnblogs.com/0000cjw/p/12209218.html

正文到此结束