Java常见面试题题总结（下）

Map接口：

HashMap和HashTable的区别：

线程是否安全角度：HashMap是非线程安全的，而HashTable是线程安全的，因为HashTable内部的方法基本上都经过了synchronized的修饰。（如果要保证线程安全那就使用ConcurrentHashMap）；

效率：因为线程安全的问题，HashMap要比HashTable的效率更高一点。另外，HashTable基本上被淘汰了，不要在代码中使用它，上面推荐了ConcurrentHashMap！

对Null key和Null value的支持：HashMap可以存储null的key和value，但是null作为键只能有一个，作为value可以有多个；HashTable不允许Null key和value，否则会抛出NullPointerException；

初始容量大小和每次扩充容量大小的不同：

• 创建时如果不给初始值：HashTable默认的初始值大小为11，之后每次扩容，容量变为原来的2n + 1；HashMap默认的初始化大小为16，之后每次扩容，容量变为原来的两倍
• 创建时给初始值：HashTable会直接使用给的初始值，而HashMap会将其扩充为2的幂次方大小（HashMap的tableSizeFor方法保证了HashMap总是使用2的幂次方大小作为哈希表的大小）

底层数据结构：JDK1.8以后，HashMap在解决哈希冲突作了大的改变，当链表长度大于阈值（默认值为8）时，将链表转化为红黑树（转化为红黑树之前会做判断，如果当前数组长度小于64，那么会先进行数组扩容，而不会转化为红黑树），以减小搜索时间。HashTable没有这样的机制

HashMap和HashSet的区别：

HashSet的底层是基于HashMap实现的，HashSet底层除了clone()、writeObject()、readObject()是HashSet自己不得不实现的，其它的都是调用的HashMap的方法

HashMap	HashSet
实现了Map接口	实现了Set接口
存储键值对	只存储对象
调用put()向map中添加元素	调用add()向Set中添加元素
HashMap使用key计算hashcode值	HashSet使用成员对象计算hashcode值，对于两个对象来说，hashcode可能会相等，所以用equals()来判断对象的相等性

HashMap和TreeMap的区别：

都继承自AbstarctMap，但是TreeMap还实现了NavigableMap接口和sortedMap接口

实现NavigableMap让TreeMap具有对集合内元素的搜索能力

实现了sortedMap让TreeMap具有了对集合元素根据键排序的能力，默认是按key的升序，不过也可以指定排序顺序

HashSet如何检查重复？

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

在JDK1.8中，HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。

// Returns: true if this set did not already contain the specified element
// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

而在HashMap的putVal()方法中也能看到说明

// Returns : previous value, or null if none
// 返回值：如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
}

也就是说在JDK1.8中，无论HashSet中是否存在重复元素，HashSet都会直接插入，只是会在add()方法的返回值中告诉我们插入之前是否存在相同元素

HashMap的底层实现：

JDK1.8之前：

HashMap底层是通过链表和数组结合在一起实现的，也就是链表散列。HashMap是通过key的hashcode经过扰动函数处理后得到hash值，然后通过(n - 1) & hash判断当前元素存储的位置（n指的是数组长度），如果当前位置存在元素的话，就判断该元素与要插入的元素hash值和key值是否相等，如果相等的话，就直接覆盖，不相同就通过拉链法解决冲突

所谓扰动函数就是HashMap的hash方法，使用hash方法就是为了防止一些实现比较差的hashcode()方法，换句话说就是使用扰动函数后可以减少碰撞

JDK1.8 HashMap的hash方法源码：

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下JDK1.7 HashMap的hash方法：

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉链法就是：将链表和数组结合。也就是会创建一个链表数组，数组中的每一格就是一个链表。如果遇到哈希冲突，就把冲突的值加入到链表即可

JDK1.8以后：

HashMap在解决哈希冲突作了大的改变，当链表长度大于阈值（默认值为8）时，将链表转化为红黑树（转化为红黑树之前会做判断，如果当前数组长度小于64，那么会先进行数组扩容，而不会转化为红黑树），以减小搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

HashMap从链表到红黑树的转换：

1、putVal()方法中执行链表到红黑树的逻辑

链表的长度大于8时，就执行treeifyBin（转换红黑树）的逻辑：

// 遍历链表
for (int binCount = 0; ; ++binCount) {
    // 遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        // 如果链表元素个数大于等于TREEIFY_THRESHOLD（8）
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            // 红黑树转换（并不会直接转换成红黑树）
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

2、treeifyBin方法判断是否真的转换为红黑树：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 判断当前数组的长度是否小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 如果当前数组的长度小于 64，那么会选择先进行数组扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 否则才将列表转换为红黑树

        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

将链表转化为红黑树之前会先对数组长度进行判断，如果小于64那么会先进行扩容，而不是转化为红黑树

HashMap的长度为什么是2的幂次方？

为了让HashMap存取更高效，尽量减少碰撞，也就是尽量要把数据分配均匀。Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

算法的设计：

首先会想到采用%取余的方式来实现。但是重点来了：取余操作中如果除数是2的幂次则等价于与其除数减一的与操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方），采用二进制位操作与（&）相对于取余操作（%）能够提高运算效率，这就解释了为什么HashMap的长度是2的幂次方

HashMap多线程操作导致死循环问题：

主要原因在于并发下的Rehash会造成元素之间产生一个循环链表。不过JDK1.8之后还是解决了这个问题，但是还是不建议在多线程的情况下采用多线程，使用多线程可能会导致数据丢失等问题，并发环境下可以使用ConcurrentHashMap

HashMap常见的遍历方式：

遍历从大的方向来说分四类：

1. 迭代器（Iterator）方式遍历
2. For Each方式遍历
3. Lambda表达式遍历（JDK1.8之后）
4. Streams API方式遍历（JDK1.8之后）

但是每种类型下又有不同的实现方式，具体的遍历方式分7类

1. 使用迭代器EntrySet的方式遍历
2. 使用迭代器KeySet的方式遍历
3. 使用ForEach EntrySet的方式遍历
4. 使用ForEach KeySet的方式遍历
5. 使用Lambda表达式的方式遍历
6. 使用Streams API单线程的方式遍历
7. 使用Streams API多线程的方式遍历

接下来看每种方式的实现：

1.迭代器EntrySet：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}

2.迭代器KeySet：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer key = iterator.next();
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

3.ForEach EntrySet方式：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}

4.ForEach KeySet方式：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        for (Integer key : map.keySet()) {
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

5.使用Lambda表达式的方式：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.forEach((key, value) -> {
            System.out.println(key);
            System.out.println(value);
        });
    }
}

6.使用Streams API单线程的方式：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.entrySet().stream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

7.使用Streams API多线程的方式：

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

以上所有方式的运算结果都是下图：

性能分析：

entryset的性能比keyset的性能高出了一倍多，因此我们应该多使用entryset来遍历map

EntrySet的性能之所以比KeySet的高是因为，KeySet在循环时使用了map.get(key)，而这个操作相当于又去遍历了一遍map去查询key对应的值，为什么是又遍历了一次，是因为在使用迭代器或者for循环时，其实已经遍历了一遍map了，再使用map.get(key)相当于遍历了两遍

而EntrySet只遍历了一遍Map集合，之后通过代码“Map.Entry<Integer, String> entry = iterator.next();”把对象的key和value都放入了Entry对象中，因此再获取的时候不需要遍历Map集合了，只要从Entry对象中取即可

安全性分析：

我们不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。同样的我们也可以使用 Lambda 中的 removeIf 来提前删除数据，或者是使用 Stream 中的 filter 过滤掉要删除的数据进行循环，这样都是安全的，当然我们也可以在 for 循环前删除数据在遍历也是线程安全的

ConcurrentHashMap和HashTable的区别：

主要区别体现在实现线程安全的方式不同 底层数据结构：JDK1.7的ConcurrentHashMap底层采用分段数组+链表实现，JDK1.8底层采用的数据结构是数组+链表/红黑树，HashTable和JDK1.8之前的HashMap都是采用的数组+链表的形式，数组是HashMap主体，链表是为了解决哈希冲突而准备的 实现线程安全的方式：

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

下面看看两者底层的数据结构图： HashTable： JDK1.7的ConcurrentHashMap： ConcurrentHashMap是由Segment数据结构和HashEntry数组构成，Segment的每个元素包含一个HashEntry数组，每个HashEntry属于链表结构 JDK1.8的ConcurrentHashMap： JDK1.8的ConcurrentHashMap是由Node数组+链表/红黑树构成，Node只用于链表的情况，红黑树的情况需要使用TreeNode。当链表冲突达到一定长度时，链表会转换为红黑树 TreeNode时存储红黑树节点，被TreeBin包装。TreeBin通过root属性维护红黑树根节点，因为红黑树在旋转的时候，根节点可能会被原来的子节点替换掉，在这个时间点，其他线程要写这个红黑树就会发生线程不安全的问题，所以在ConcurrentHashMap中TreeBin通过waiter属性维护当前这颗红黑树的线程，防止其他线程进入。

ConcurrentHashMap是Java中的一个类，用于实现线程安全的HashMap。在面试中，你可能会被询问到关于它的工作原理。以下是你可以参考的回答： ConcurrentHashMap是一个散列表，它支持完全并发的读取，并且线程安全地更新。它使用了一种称为"分段锁"的技术，这种技术可以让我们在多线程环境中对Map进行并发访问。

1. 数据分段：ConcurrentHashMap将内部数据分成一段一段的，每一段数据都由一个锁来保护。这意味着，如果我们对一个特定的段进行写操作，其他线程仍然可以访问和修改其他段的数据。
2. 读写锁分离：在ConcurrentHashMap中，读操作大多数情况下不需要获得锁，这就实现了读操作的完全并发。只有在写操作时需要获得锁，而且只对相应的段进行锁定，而不是整个Map。
3. CAS操作：在更新操作中，ConcurrentHashMap使用CAS（Compare-and-Swap）操作来确保对Map的更新操作是线程安全的。CAS操作是现代计算机多线程同步的重要手段，它是一种无锁化的算法，能够在高并发的情况下提供优于传统锁的性能。
4. Size操作：ConcurrentHashMap的size操作可能不准确，因为在执行size操作时可能有其他线程正在进行写操作。
5. KeySet, Values, and EntrySet：返回的是视图，它们迭代器的行为与对应的ConcurrentHashMap迭代器行为一致。

总的来说，ConcurrentHashMap通过分段锁和CAS操作实现了高并发和线程安全。