【第二章：Java核心技术解析】第7节：Java基础 - 三大集合（下）

大家好，很高兴我们可以继续学习交流Java高频面试题。本小节是Java基础篇章的第五小节，在上一小节中，我们将三大集合引出，并且重点介绍了HashMap，Hashtable和ConcurrentHashMap的相关知识点。本小节中，我们继续交流Java中其余的集合知识点，希望大家可以熟练掌握。

（1）TreeMap有哪些特性？

答：TreeMap底层使用红黑树实现，TreeMap中存储的键值对按照键来排序。

• 如果Key存入的是字符串等类型，那么会按照字典默认顺序排序
• 如果传入的是自定义引用类型，比如说User，那么该对象必须实现Comparable接口，并且覆盖其compareTo方法；或者在创建TreeMap的时候，我们必须指定使用的比较器。如下所示：

// 方式一：定义该类的时候，就指定比较规则
class User implements Comparable{
    @Override
    public int compareTo(Object o) {
        // 在这里边定义其比较规则
        return 0;
    }
}
public static void main(String[] args) {
    // 方式二：创建TreeMap的时候，可以指定比较规则
    new TreeMap<User, Integer>(new Comparator<User>() {
        @Override
        public int compare(User o1, User o2) {
            // 在这里边定义其比较规则
            return 0;
        }
    });
}

解析：
关于TreeMap的考察，会涉及到两个接口Comparable和Comparator的比较。Comparable接口的后缀是able大概表示可以的意思，也就是说一个类如果实现了这个接口，那么这个类就是可以比较的。类似的还有cloneable接口表示可以克隆的。而Comparator则是一个比较器，是创建TreeMap的时候传入，用来指定比较规则。

那么Comparable接口和Comparator接口有哪些区别呢？

• Comparable实现比较简单，但是当需要重新定义比较规则的时候，必须修改源代码，即修改User类里边的compareTo方法
• Comparator接口不需要修改源代码，只需要在创建TreeMap的时候重新传入一个具有指定规则的比较器即可。

（2）ArrayList和LinkedList有哪些区别？

答：常用的ArrayList和LinkedList的区别总结如下。

• ArrayList底层使用了动态数组实现，实质上是一个动态数组
• LinkedList底层使用了双向链表实现，可当作堆栈、队列、双端队列使用
• ArrayList在随机存取方面效率高于LinkedList
• LinkedList在节点的增删方面效率高于ArrayList
• ArrayList必须预留一定的空间，当空间不足的时候，会进行扩容操作
• LinkedList的开销是必须存储节点的信息以及节点的指针信息

解析：

该题是集合中最常见和最基础的题目之一，List集合也是我们平时使用很多的集合。List接口的常见实现就算ArrayList和LinkedList，我们必须熟练掌握其底层实现以及一些特性。其实还有一个集合Vector，它是线程安全的ArrayList，但是已经被废弃，不推荐使用了。多线程环境下，我们可以使用CopyOnWriteArrayList替代ArrayList来保证线程安全。

（3）HashSet和TreeSet有哪些区别？

答： HashSet和TreeSet的区别总结如下。

• HashSet底层使用了Hash表实现。

保证元素唯一性的原理：判断元素的hashCode值是否相同。如果相同，还会继续判断元素的equals方法，是否为true

• TreeSet底层使用了红黑树来实现。

保证元素唯一性是通过Comparable或者Comparator接口实现

解析：

其实，HashSet的底层实现还是HashMap，只不过其只使用了其中的Key，具体如下所示：

• HashSet的add方法底层使用HashMap的put方法将key = e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有value，但是key保持不变，所以如果将一个已经存在的e元素添加中HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。
• HashSet的contains方法使用HashMap得containsKey方法实现

（4）LinkedHashMap和LinkedHashSet有了解吗？

答：LinkedHashMap在面试题中还是比较常见的。LinkedHashMap可以记录下元素的插入顺序和访问顺序，具体实现如下：

• LinkedHashMap内部的Entry继承于HashMap.Node，这两个类都实现了Map.Entry<K,V>
• LinkedHashMap的Entry不光有value，next，还有before和after属性，这样通过一个双向链表，保证了各个元素的插入顺序
• 通过构造方法public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)， accessOrder传入true可以实现LRU缓存算法（访问顺序）
• LinkedHashSet 底层使用LinkedHashMap实现，两者的关系类似与HashMap和HashSet的关系，大家可以自行类比。

扩展： 什么是LRU算法？LinkedHashMap如何实现LRU算法？