Java面试题收集整理

Java 相关知识点

ArrayList 和 Vector 的区别

Util常用类

这张图里的内容对我们学习 Java 来说，非常的重要，白色的部分是需要去了解的，黄色部分是我们要去重点了解的，不但要知道怎么去用，至少还需要读一次源码。绿色部分内容已经很少用了，但在面试题中有可能会问到，我们来看一个经常出现的面试题：ArrayList 与 Vector 的区别是什么？

**首先我们给出标准答案： **

**1、Vector 是线程安全的，ArrayList 不是线程安全的。 **

2、ArrayList 在底层数组不够用时在原来的基础上扩展 0.5 倍，Vector 是扩展 1 倍。

看上图 Vector 和 ArrayList 一样，都继承自 List，来看一下 Vector 的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * The array buffer into which the components of the vector are
     * stored. The capacity of the vector is the length of this array buffer,
     * and is at least large enough to contain all the vector's elements.
     *
     * <p>Any array elements following the last element in the Vector are null.
     *
     * @serial
     */
    protected Object[] elementData;

实现了 List 接口，底层和 ArrayList 一样，都是数组来实现的。分别看一下这两个类的 add 方法，首先来看 ArrayList 的 add 源码

1
2
3
4
5
6
7
8
9
10
11
/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!检查是否需要扩容
        elementData[size++] = e; //给元素赋值
        return true;
    }

再看 Vector 的 add 源码

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) { //加了一个synchronized关键字
        modCount++;
        ensureCapacityHelper(elementCount + 1); //检查是否需要扩容
        elementData[elementCount++] = e; //给元素赋值
        return true;
    }

方法实现都一样，就是加了一个 synchronized 的关键字，remove 方法也是一样。

只要是关键性的操作，方法前面都加了 synchronized 关键字，来保证线程的安全性。当执行 synchronized 修饰的方法前，系统会对该方法加一把锁，方法执行完成后释放锁，加锁和释放锁的这个过程，在系统中是有开销的，因此，在单线程的环境中，Vector 效率要差很多。（多线程环境不允许用 ArrayList，需要做处理）。

和 ArrayList 和 Vector 一样，同样的类似关系的类还有 HashMap 和 HashTable，StringBuilder 和 StringBuffer，后者是前者线程安全版本的实现。

HashMap 原理及实现学习总结

一. HashMap 的工作原理

HashMap 基于 hashing 原理，我们通过 put()和 get()方法储存和获取对象。当我们将键值对传递给 put()方法时，它调用键对象的 hashCode()方法来计算 hashcode，让后找到 bucket 位置来储存值对象。当获取对象时，通过键对象的 equals()方法找到正确的键值对，然后返回值对象。HashMap 使用 LinkedList 来解决碰撞问题，当发生碰撞了，对象将会储存在 LinkedList 的下一个节点中。 HashMap 在每个 LinkedList 节点中储存键值对对象。
当两个不同的键对象的 hashcode 相同时会发生什么？ 它们会储存在同一个 bucket 位置的 LinkedList 中。键对象的 equals()方法用来找到键值对。

二.HashMap 的定义

HashMap 实现了 Map 接口，继承 AbstractMap。其中 Map 接口定义了键映射到值的规则，而 AbstractMap 类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作！

1
2
3
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

三.HashMap 的数据结构

HashMap 的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap 中主要是通过 key 的 hashCode 来计算 hash 值的，只要 hashCode 相同，计算出来的 hash 值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的 hash 值是相同的，这就出现了所谓的 hash 冲突。学过数据结构的同学都知道，解决 hash 冲突的方法有很多，HashMap 底层是通过链表来解决 hash 冲突的。

hash

紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的 key 映射到了数组的同一位置处，就将其放入单链表中。

四.HashMap 的构造函数

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响 HashMap 性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是 O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为 0.75，一般情况下我们是无需修改的。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

五.HashMap 的存储实现

HashMap 中我们最长用的就是 put(K, V)和 get(K)。我们都知道，HashMap 的 K 值是唯一的，那如何保证唯一性呢？我们首先想到的是用 equals 比较，没错，这样可以实现，但随着内部元素的增多，put 和 get 的效率将越来越低，这里的时间复杂度是 O(n)，假如有 1000 个元素，put 时需要比较 1000 次。实际上，HashMap 很少会用到 equals 方法，因为其内通过一个哈希表管理所有元素，哈希是通过 hash 单词音译过来的，也可以称为散列表，哈希算法可以快速的存取元素，当我们调用 put 存值时，HashMap 首先会调用 K 的 hashCode 方法，获取哈希码，通过哈希码快速找到某个存放位置，这个位置可以被称之为 bucketIndex，通过上面所述 hashCode 的协定可以知道，如果 hashCode 不同，equals 一定为 false，如果 hashCode 相同，equals 不一定为 true。所以理论上，hashCode 可能存在冲突的情况，有个专业名词叫碰撞，当碰撞发生时，计算出的 bucketIndex 也是相同的，这时会取到 bucketIndex 位置已存储的元素，最终通过 equals 来比较，equals 方法就是哈希码碰撞时才会执行的方法，所以前面说 HashMap 很少会用到 equals。HashMap 通过 hashCode 和 equals 最终判断出 K 是否已存在，如果已存在，则使用新 V 值替换旧 V 值，并返回旧 V 值，如果不存在 ，则存放新的键值对到 bucketIndex 位置。整个 put 过程的流程图如下：

相关源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换
    public V put(K key, V value) {
        // 当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
        if (key == null)
            return putForNullKey(value);
        // 使用hash函数预处理hashCode，计算key的hash值
        int hash = hash(key.hashCode());//-------（1）
        // 计算key hash 值在 table 数组中的位置
        int i = indexFor(hash, table.length);//------(2)
        // 从i出开始迭代 e,找到 key 保存的位置
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 判断该条链上是否有hash值相同的(key相同)
            // 若存在相同，则直接覆盖value，返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 旧值 = 新值
                V oldValue = e.value;
                // 将要存储的value存进去
                e.value = value;
                e.recordAccess(this);
                // 返回旧的value
                return oldValue;
            }
        }
        // 修改次数增加1
        modCount++;
        // 将key、value添加至i位置处
        addEntry(hash, key, value, i);
        return null;
    }

通过源码我们可以清晰看到 HashMap 保存数据的过程为：首先判断 key 是否为 null，若为 null，则直接调用 putForNullKey 方法。若不为空则先计算 key 的 hash 值，然后根据 hash 值搜索在 table 数组中的索引位置，如果 table 数组在该位置处有元素，则通过比较是否存在相同的 key，若存在则覆盖原来 key 的 value，否则将该元素保存在链头（最先保存的元素放在链尾）。若 table 在该处没有元素，则直接保存。这个过程看似比较简单，其实深有内幕。有如下几点：
1、 先看迭代处。此处迭代原因就是为了防止存在相同的 key 值，若发现两个 hash 值（key）相同时，HashMap 的处理方式是用新 value 替换旧 value，这里并没有处理 key，这就解释了 HashMap 中没有两个相同的 key。
2、 在看（1）、（2）处。这里是 HashMap 的精华所在。首先是 hash 方法，该方法为一个纯粹的数学计算，就是计算 h 的 hash 值。

HashMap 的底层数组长度总是 2 的 n 次方，在构造函数中存在：capacity <<= 1;这样做总是能够保证 HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时，h&(length - 1)就相当于对 length 取模，而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。
这里再来复习 put 的流程：当我们想一个 HashMap 中添加一对 key-value 时，系统首先会计算 key 的 hash 值，然后根据 hash 值确认在 table 中存储的位置。若该位置没有元素，则直接插入。否则迭代该处元素链表并依此比较其 key 的 hash 值。如果两个 hash 值相等且 key 值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),则用新的 Entry 的 value 覆盖原来节点的 value。如果两个 hash 值相等但 key 值不等 ，则将该节点插入该链表的链头。具体的实现过程见 addEntry 方法，如下：

1
2
3
4
5
6
7
8
9
10
11
// 添加一个新的桶来保存该key和value
    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 获取bucketIndex处的Entry
        Entry<K, V> e = table[bucketIndex];
        // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
        table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
        // 若HashMap中元素的个数超过极限了，则容量扩大两倍
        if (size++ >= threshold)
            // 调整容量
            resize(2 * table.length);
    }

这个方法中有两点需要注意：
一是链的产生：系统总是将新的 Entry 对象添加到 bucketIndex 处。如果 bucketIndex 处已经有了对象，那么新添加的 Entry 对象将指向原有的 Entry 对象，形成一条 Entry 链，但是若 bucketIndex 处没有 Entry 对象，也就是 e==null,那么新添加的 Entry 对象指向 null，也就不会产生 Entry 链了。
二是扩容问题：随着 HashMap 中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响 HashMap 的速度，为了保证 HashMap 的效率，系统必须要在某个临界点进行扩容处理。该临界点在当 HashMap 中元素的数量等于 table 数组长度*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新 table 数组中的位置并进行复制处理。所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

六.和其他 Map 比较

HashMap、ConcurrentHashMap、HashTable 的区别

引入ConcurrentHashMap是为了在同步集合 HashTable 之间有更好的选择，HashTable与HashMap、ConcurrentHashMap主要的区别在于 HashMap 不是同步的、线程不安全的和不适合应用于多线程并发环境下，而ConcurrentHashMap是线程安全的集合容器，特别是在多线程和并发环境中，通常作为Map的主要实现。除了线程安全外，他们之间还有一些细微的不同，本文会介绍到。顺便说说，HashMap和ConcurrentHashMap还有ConcurrentHashMap和Hashtable两者之间的区别在 Java 面试中经常出现，特别是高级 Java 程序员。

HashMap 与 ConcurrentHashMap 的区别

在这部分，我们会看到更多关于HashMap和ConcurrentHashMap的细节和对比它们之间的参数比如线程安全、同步、性能和基本的使用。

  1. 就像上面所说他们之间的第一个重要的区别就是ConcurrentHashMap是线程安全的和在并发环境下不需要加额外的同步。虽然它不像Hashtable那样需要同样的同步等级(全表锁)，但也有很多实际的用途。

  2. 你可以使用Collections.synchronizedMap(HashMap)来包装 HashMap 作为同步容器，这时它的作用几乎与Hashtable一样,当每次对Map做修改操作的时候都会锁住这个Map对象，而ConcurrentHashMap会基于并发的等级来划分整个 Map 来达到线程安全，它只会锁操作的那一段数据而不是整个Map都上锁。

  3. ConcurrentHashMap有很好的扩展性，在多线程环境下性能方面比做了同步的HashMap要好，但是在单线程环境下，HashMap会比ConcurrentHashMap好一点。

ConcurrentHashMap vs Hashtable vs Synchronized Map

虽然三个集合类在多线程并发应用中都是线程安全的，但是他们有一个重大的差别，就是他们各自实现线程安全的方式。Hashtable是 jdk1 的一个遗弃的类，它把所有方法都加上synchronized关键字来实现线程安全。所有的方法都同步这样造成多个线程访问效率特别低。Synchronized Map与HashTable差别不大，也是在并发中作类似的操作，两者的唯一区别就是Synchronized Map没被遗弃，它可以通过使用Collections.synchronizedMap()来包装Map作为同步容器使用。

另一方面，ConcurrentHashMap的设计有点特别，表现在多个线程操作上。它不用做外的同步的情况下默认同时允许 16 个线程读和写这个 Map 容器。因为其内部的实现剥夺了锁，使它有很好的扩展性。不像HashTable和Synchronized Map，ConcurrentHashMap不需要锁整个 Map，相反它划分了多个段(segments)，要操作哪一段才上锁那段数据。

坦白说，集合类是一个最重要的 Java API，我觉得恰当的使用它们是一种艺术。依我个人经验，我会使用ArrayList这些容器来提高自己的 Java 程序的性能，而不会去用一些遗弃的容器比如Vector等等，在 Java 5 之前，Java 集合容器有一个很致命的缺陷就是缺乏可扩展性。
同步集合类比如Hashtable和Vector在多线程 Java 应用里面逐渐成为障碍物；在 jdk5 后出现一些很好的并发集合，对大容量、低延迟的电子交易系统有很大影响，是快速存取数据的支柱。

正确理解 Thread Local 的原理与适用场景

ThreadLocal 解决什么问题

由于 ThreadLocal 支持范型，如 ThreadLocal< StringBuilder >，为表述方便，后文用 变量 代表 ThreadLocal 本身，而用 实例 代表具体类型（如 StringBuidler ）的实例。

不恰当的理解

下面是常见的对于 ThreadLocal 的介绍

ThreadLocal 为解决多线程程序的并发问题提供了一种新的思路
ThreadLocal 的目的是为了解决多线程访问资源时的共享问题

还有很多文章在对比 ThreadLocal 与 synchronize 的异同。既然是作比较，那应该是认为这两者解决相同或类似的问题。

上面的描述，问题在于，ThreadLocal 并不解决多线程 共享 变量的问题。既然变量不共享，那就更谈不上同步的问题。

合理的理解

ThreadLocal 变量，它的基本原理是，同一个 ThreadLocal 所包含的对象（对 ThreadLocal< String >而言即为 String 类型变量），在不同的 Thread 中有不同的副本（实际是不同的实例，后文会详细阐述）。这里有几点需要注意

  • 因为每个 Thread 内有自己的实例副本，且该副本只能由当前 Thread 使用。这是也是 ThreadLocal 命名的由来
  • 既然每个 Thread 有自己的实例副本，且其它 Thread 不可访问，那就不存在多线程间共享的问题
  • 既无共享，何来同步问题，又何来解决同步问题一说？

那 ThreadLocal 到底解决了什么问题，又适用于什么样的场景？

This class provides thread-local variables. These variables differ from their normal counterparts in that each thread that accesses one (via its get or set method) has its own, independently initialized copy of the variable. ThreadLocal instances are typically private static fields in classes that wish to associate state with a thread (e.g., a user ID or Transaction ID).
Each thread holds an implicit reference to its copy of a thread-local variable as long as the thread is alive and the ThreadLocal instance is accessible; after a thread goes away, all of its copies of thread-local instances are subject to garbage collection (unless other references to these copies exist).

ThreadLocal 提供了线程本地的实例。它与普通变量的区别在于，每个使用该变量的线程都会初始化一个完全独立的实例副本。ThreadLocal 变量通常被private static修饰。当一个线程结束时，它所使用的所有 ThreadLocal 相对的实例副本都可被回收。

总的来说，ThreadLocal 适用于每个线程需要自己独立的实例且该实例需要在多个方法中被使用，也即变量在线程间隔离而在方法或类间共享的场景。后文会通过实例详细阐述该观点。另外，该场景下，并非必须使用 ThreadLocal ，其它方式完全可以实现同样的效果，只是 ThreadLocal 使得实现更简洁。

ThreadLocal 用法

下面通过如下代码说明 ThreadLocal 的使用方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class ThreadLocalDemo {

  public static void main(String[] args) throws InterruptedException {

    int threads = 3;
    CountDownLatch countDownLatch = new CountDownLatch(threads);
    InnerClass innerClass = new InnerClass();
    for(int i = 1; i <= threads; i++) {
      new Thread(() -> {
        for(int j = 0; j < 4; j++) {
          innerClass.add(String.valueOf(j));
          innerClass.print();
        }
        innerClass.set("hello world");
        countDownLatch.countDown();
      }, "thread - " + i).start();
    }
    countDownLatch.await();

  }

  private static class InnerClass {

    public void add(String newStr) {
      StringBuilder str = Counter.counter.get();
      Counter.counter.set(str.append(newStr));
    }

    public void print() {
      System.out.printf("Thread name:%s , ThreadLocal hashcode:%s, Instance hashcode:%s, Value:%s\n",
      Thread.currentThread().getName(),
      Counter.counter.hashCode(),
      Counter.counter.get().hashCode(),
      Counter.counter.get().toString());
    }

    public void set(String words) {
      Counter.counter.set(new StringBuilder(words));
      System.out.printf("Set, Thread name:%s , ThreadLocal hashcode:%s,  Instance hashcode:%s, Value:%s\n",
      Thread.currentThread().getName(),
      Counter.counter.hashCode(),
      Counter.counter.get().hashCode(),
      Counter.counter.get().toString());
    }
  }

  private static class Counter {

    private static ThreadLocal<StringBuilder> counter = new ThreadLocal<StringBuilder>() {
      @Override
      protected StringBuilder initialValue() {
        return new StringBuilder();
      }
    };

  }

}

上述代码执行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Thread name:thread - 1 , ThreadLocal hashcode:372282300, Instance hashcode:418873098, Value:0
Thread name:thread - 3 , ThreadLocal hashcode:372282300, Instance hashcode:1609588821, Value:0
Thread name:thread - 2 , ThreadLocal hashcode:372282300, Instance hashcode:1780437710, Value:0
Thread name:thread - 3 , ThreadLocal hashcode:372282300, Instance hashcode:1609588821, Value:01
Thread name:thread - 1 , ThreadLocal hashcode:372282300, Instance hashcode:418873098, Value:01
Thread name:thread - 3 , ThreadLocal hashcode:372282300, Instance hashcode:1609588821, Value:012
Thread name:thread - 3 , ThreadLocal hashcode:372282300, Instance hashcode:1609588821, Value:0123
Set, Thread name:thread - 3 , ThreadLocal hashcode:372282300,  Instance hashcode:1362597339, Value:hello world
Thread name:thread - 2 , ThreadLocal hashcode:372282300, Instance hashcode:1780437710, Value:01
Thread name:thread - 1 , ThreadLocal hashcode:372282300, Instance hashcode:418873098, Value:012
Thread name:thread - 2 , ThreadLocal hashcode:372282300, Instance hashcode:1780437710, Value:012
Thread name:thread - 1 , ThreadLocal hashcode:372282300, Instance hashcode:418873098, Value:0123
Thread name:thread - 2 , ThreadLocal hashcode:372282300, Instance hashcode:1780437710, Value:0123
Set, Thread name:thread - 1 , ThreadLocal hashcode:372282300,  Instance hashcode:482932940, Value:hello world
Set, Thread name:thread - 2 , ThreadLocal hashcode:372282300,  Instance hashcode:1691922941, Value:hello world

从上面的输出可看出

  • 从第 1-3 行输出可见，每个线程通过 ThreadLocal 的 get() 方法拿到的是不同的 StringBuilder 实例
  • 第 1-3 行输出表明，每个线程所访问到的是同一个 ThreadLocal 变量
  • 从 7、12、13 行输出以及第 30 行代码可见，虽然从代码上都是对 Counter 类的静态 counter 字段进行 get() 得到 StringBuilder 实例并追加字符串，但是这并不会将所有线程追加的字符串都放进同一个 StringBuilder 中，而是每个线程将字符串追加进各自的 StringBuidler 实例内
  • 对比第 1 行与第 15 行输出并结合第 38 行代码可知，使用 set(T t) 方法后，ThreadLocal 变量所指向的 StringBuilder 实例被替换