面试准备之Java集合(一)

1、Java集合类框架的基本接口有哪些？

总共有两大接口：Collection 和 Map ，一个元素集合，一个是键值对集合； 其中 List 和 Set 接口继承了 Collection 接口，一个是有序元素集合，一个是无序元素集合； 而 ArrayList 和 LinkedList 实现了 List 接口，HashSet 实现了 Set 接口，这几个都比较常用； HashMap 和 HashTable 实现了 Map 接口，并且 HashTable 是线程安全的，但是 HashMap 性能更好；

2、Collection 和 Collections 有什么区别？

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

3、为什么集合类接口没有实现 Cloneable 和 Serializable 接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

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

5、什么是迭代器(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 中插入和删除元素。

6、Iterator 和 ListIterator 的区别是什么？

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

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

快速失败：当你在迭代一个集合的时候，如果有另一个线程正在修改你正在访问的那个集合时，就会抛出一个 ConcurrentModification 异常。 在 java.util 包下的都是快速失败，不能在多线程下发生并发修改（迭代过程中被修改）。

具体原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。

每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

安全失败：你在迭代的时候会去底层集合做一个拷贝，所以你在修改上层集合的时候是不会受影响的，不会抛出 ConcurrentModification 异常。 在 java.util.concurrent 包下的全是安全失败的。可以在多线程下并发使用，并发修改。

8、HashMap 和 Hashtable 有什么区别？

1、HashMap 是非线程安全的，HashTable 是线程安全的。

2、HashMap 的键和值都允许有 null 值存在，而 HashTable 则不行。

3、因为线程安全的问题，HashMap 效率比 HashTable 的要高。

4、Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线程环境，而 Hashtable 适合于多线程环境。

5、HashMap 去掉了 Hashtable 中的 contains 方法。

6、HashMap 继承自 AbstractMap 类，Hashtable 继承自 Dictionary 类。

7、两者提供了可供应用迭代的键的集合，都是快速失败的。此外 Hashtable 提供了对键的列举(Enumeration)

8、初始容量大小和每次扩充容量大小的不同： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍， 两者的负载因子默认都是：0.75 。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

一般现在不建议用 HashTable, ①是 HashTable 是遗留类，内部实现很多没优化和冗余。②即使在多线程环境下，现在也有同步的 ConcurrentHashMap 替代，没有必要因为是多线程而用 HashTable。

HashMap 中带有初始容量的构造函数：

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
复制代码

下面这个方法保证了 HashMap 总是使用2的幂作为哈希表的大小。

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
复制代码

9、为啥 Hashtable 是不允许 KEY 和 VALUE 为 null, 而 HashMap 则可以呢？

因为 Hashtable 在 put null 值的时候会直接抛空指针异常；要从 Hashtable 成功存储和检索对象，用作键的对象必须实现 hashCode 方法和 equals 方法。由于 null 不是对象，因此不能在其上调用.equals()或.hashCode()，因此 Hashtable 无法将其计算哈希值以用作键。

public synchronized V put(K var1, V var2) {
    if (var2 == null) {// value不能为空
        throw new NullPointerException();
    } else {
        Hashtable.Entry[] var3 = this.table;
        int var4 = var1.hashCode(); // key为null，则无法调用hashCode方法
        int var5 = (var4 & 2147483647) % var3.length;
        for(Hashtable.Entry var6 = var3[var5]; var6 != null; var6 = var6.next) {
            if (var6.hash == var4 && var6.key.equals(var1)) {
                Object var7 = var6.value;
                var6.value = var2;
                return var7;
            }
        }
        this.addEntry(var4, var1, var2, var5);
        return null;
    }
}
复制代码

ConcurrentHashMap 同理。

反观 HashMap 类，在 put 方法中对 value 没有 null 值的限制，对于 key 值有如下处理：

static final int hash(Object var0) {
    int var1;
    return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
复制代码

10、ConcurrentHashMap 和 Hashtable 的区别

• 底层数据结构：ConcurrentHashMap 在 JDK1.7 底层采用 分段的数组+链表 实现，在 JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

• 实现线程安全的方式： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

图片来源：www.cnblogs.com/chengxiao/p…

HashTable:

JDK1.7 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：

11、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程访问其中一个段数据时，只是占用当前数据段的锁，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}
复制代码

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap 取消了Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

推荐阅读：

• ConcurrentHashMap实现原理及源码分析
  
• 解读Java8中ConcurrentHashMap是如何保证线程安全的

12、Java 中的 HashMap 的工作原理是什么？

hashmap 是一个 key-value 键值对的数据结构，从结构上来讲在 jdk1.8 之前是用数组加链表的方式实现，jdk1.8 加了红黑树，hashmap 数组的默认初始长度是 16，hashmap 数组只允许一个 key 为 null，允许多个 value 为 null。

hashmap 的内部实现，hashmap 是使用数组+链表+红黑树的形式实现的，其中数组是一个一个 Node[]数组，我们叫他 hash 桶数组，它上面存放的是 key-value 键值对的节点。HashMap 是用 hash 表来存储的，在 hashmap 里为解决 hash 冲突，使用链地址法，简单来说就是数组加链表的形式来解决，当数据被 hash 后，得到数组下标，把数据放在对应下标的链表中。

然后再说一下 hashmap 的方法实现

• put 方法，put 方法的第一步，就是计算出要 put 元素在 hash 桶数组中的索引位置，得到索引位置需要三步，计算要 put 元素 key 的 hash 值，高位运算，取模运算，高位运算就是用第一步得到的值 h，用 h 的高 16 位和低 16 位进行异或操作，此步骤主要是为了在 hash 桶数组长度较小的时候，让高位也参与运算，并且不会有太大的开销。第三步为了使 hash 桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和 hash 桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高。

• jdk1.8 中 put 方法的具体步骤，先判断 hashmap 是否为空，为空的话扩容，不为空计算出 key 的 索引值 i，然后看 table[i]是否为空，为空就直接插入，不为空判断当前位置的 key 和 table[i] 是否相同，相同就覆盖，不相同就查看 table[i] 是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于 8，并且此时数组的长度大于等于 64，转为红黑树结构，执行完成后看 size 是否大于阈值 threshold，大于就扩容，否则直接结束。

• get 方法就是计算出要获取元素的索引值，去对应位置取即可。

HashMap 的两个重要属性是容量 capacity 和加载因子 loadfactor，默认值分布为 16 和 0.75，当容器中的元素个数大于 capacity*loadfactor 时，容器会进行扩容 resize 为 2n，在初始化 Hashmap 时可以对着两个值进行修改，负载因子 0.75 被证明为是性能比较好的取值，通常不会修改，那么只有初始容量 capacity 会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量 capacity，以防止频繁的 resize 操作影响性能。

扩容机制，当节点数量 size 超过阈值时，进行扩容。hashmap 的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算 hash 插入到新数组中，在 jdk1.8 时，不用重新计算 hash，只用看看原来的 hash 值新增的一位是0还是 1，如果是 1， 这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。

关于链表与红黑树互转：当同一个索引位置的节点在增加后大于8个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。

HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。 JDK1.7 扩容过程一个非常重要的方法是 transfer 方法（JDK1.8中移除该方法），采用头插法，把旧数组的元素插入到新数组中。

13、hashmap 大小为什么是 2 的幂次方

在计算插入元素在 hash 桶数组的索引时第三步，为了使元素分布的更加均匀，用取模操作，但是传统取模操作效率低，然后优化成 h&(length-1)，设置成 2 幂次方，是因为 2 的幂次方-1后的值每一位上都是 1，然后与第二步计算出的 h 值与的时候，最终的结果只和 key 的 hashcode 值本身有关，这样不会造成空间浪费并且分布均匀。 如果 length 不为 2 的幂，比如 15。那么 length-1 的 2 进制就会变成 1110。在 h 为随机数的情况下，和 1110 做&操作。尾数永远为 0。那么 0001、1001、1101 等尾数为 1 的位置就永远不可能被 entry 占用。这样会造成浪费，不随机等问题。

14、HashMap 的内部类 TreeNode 不继承它自己的内部类 Node，为什么继承自 Node 的子类 LinkedHashMap 内部类 Entry ？

在对核心内容展开分析之前，这里先插队分析一下键值对节点的继承体系。先来看看继承体系结构图：

LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node，并新增了两个引用，分别是 before 和 after。这两个引用的用途不难理解，也就是用于维护双向链表。同时，TreeNode 继承 LinkedHashMap 的内部类 Entry 后，就具备了和其他 Entry 一起组成链表的能力。但是这里需要大家考虑一个问题。当我们使用 HashMap 时，TreeNode 并不需要具备组成链表能力。如果继承 LinkedHashMap 内部类 Entry ，TreeNode 就多了两个用不到的引用，这样做不是会浪费空间吗？  这里这么做确实会浪费空间，但与 TreeNode 通过继承获取的组成链表的能力相比，这点浪费是值得的。

一般情况下，只要 hashCode 的实现不糟糕，Node 组成的链表很少会被转成由 TreeNode 组成的红黑树。也就是说 TreeNode 使用的并不多，浪费那点空间是可接受的。假如 TreeNode 机制继承自 Node 类，那么它要想具备组成链表的能力，就需要 Node 去继承 LinkedHashMap 的内部类 Entry。这个时候就得不偿失了，浪费很多空间去获取不一定用得到的能力。

15、如何基于 LinkedHashMap 实现缓存

通过继承 LinkedHashMap 实现了一个简单的 LRU( 最近最少使用 ) 策略的缓存。

在新增数据时，LinkedHashMap 的 put 方法实际上调用 HashMap 的 put 方法，在 putVal 方法的最后，有一个 afterNodeInsertion 方法，源码如下：

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根据条件判断是否移除最近最少被访问的节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
复制代码

根据源码可知，removeEldestEntry()方法默认返回 false，所以无法执行 removeNode() 方法。当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。

比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点。实现代码如下：

/**
 * @author hresh
 * @description https://juejin.cn/user/2664871918047063
 */
public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_NODE_NUM = 16;
    private int limit;
    public SimpleCache() {
        this(MAX_NODE_NUM);
    }
    public SimpleCache(int limit) {
        super(limit, 0.75f, true);
        this.limit = limit;
    }
    public V save(K key, V val) {
        return put(key, val);
    }
    public V getOne(K key) {
        return get(key);
    }
    public boolean exists(K key) {
        return containsKey(key);
    }
    /**
     * 判断节点数是否超限
     * @param eldest
     * @return 超限返回 true，否则返回 false
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > limit;
    }
}
复制代码

测试代码如下：

@Test
public void test() throws Exception {
    SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);
    for (int i = 0; i < 10; i++) {
        cache.save(i, i * i);
    }
    System.out.println("插入10个键值对后，缓存内容：");
    System.out.println(cache + "\n");
    System.out.println("访问键值为7的节点后，缓存内容：");
    cache.getOne(7);
    System.out.println(cache + "\n");
    System.out.println("插入键值为1的键值对后，缓存内容：");
    cache.save(1, 1);
    System.out.println(cache);
}
复制代码

执行结果为：

在测试代码中，设定缓存大小为3。在向缓存中插入10个键值对后，只有最后3个被保存下来了，其他的都被移除了。然后通过访问键值为7的节点，使得该节点被移到双向链表的最后位置。当我们再次插入一个键值对时，键值为7的节点就不会被移除。

16、hashCode()和 equals()方法的重要性体现在什么地方？

HashMap 的很多函数要基于 equal()函数和 hashCode()函数。hashCode()用来定位要存放的位置，equal()用来判断是否相等。hashcode 和 equals 组合在一起确定元素的唯一性。

查找元素时，如果单单使用 equals 来确定一个元素，需要对集合内的元素逐个调用 equals 方法，效率太低。因此加入了 hashcode 方法，将元素映射到随机的内存地址上，通过 hashcode 快速定位到元素（大致）所在的内存地址，再通过使用 equals 方法确定元素的精确位置。 比较两个元素时，先比较 hashcode，如果 hashcode 不同，则元素一定不相等；如果相同，再用 equals 判断。

HashMap 采用这两个方法实现散列存储，提高键的索引性能。HashSet 是基于 HashMap 实现的。