转载

经历一场 Java 面试，面对这些问题我竟然结巴了

作者简介：王磊，前360技术专家。本文选自：拉勾教育《Java 源码剖析 34 讲》

你好，我是你的 Java 面试课老师王磊，欢迎进入第 02 课时的内容“HashMap 底层实现原理是什么？它都做了哪些优化？”

HashMap 是使用频率最高的类型之一，同时也是面试经常被问到的问题之一，这是因为 HashMap 的知识点有很多，同时它又属于 Java 基础知识的一部分，因此在面试中经常被问到。

本课时的面试题是，HashMap 底层是如何实现的？在 JDK 1.8 中它都做了哪些优化？

典型回答

在 JDK 1.7 中 HashMap 是以数组加链表的形式组成的，JDK 1.8 之后新增了红黑树的组成结构，当链表大于 8 时，链表结构会转换成红黑树结构，它的组成结构如下图所示：

经历一场 Java 面试，面对这些问题我竟然结巴了

数组中的元素我们称之为哈希桶，它的定义如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;


    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }


    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }


    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }


    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }


    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;

可以看出每个哈希桶中包含了四个字段：hash、key、value、next，其中 next 表示链表的下一个节点。

JDK 1.8 之所以添加红黑树是因为一旦链表过长，会严重影响 HashMap 的性能，而红黑树具有快速增删改查的特点，这样就可以有效的解决链表过长时操作比较慢的问题。

本文选自：拉勾教育《Java 源码剖析 34 讲》

考点分析

上面大体介绍了 HashMap 的组成结构，但面试官想要知道的远远不止这些，和 HashMap 相关的面试题还有以下几个：

JDK 1.8 HashMap 扩容时做了哪些优化？
加载因子为什么是 0.75？
当有哈希冲突时，HashMap 是如何查找并确认元素的？
HashMap 源码中有哪些重要的方法？

知识拓展

1.HashMap 源码分析

声明：本系列课程在未做特殊说明的情况下，都是以目前主流的 JDK 版本 1.8 为例来进行源码分析的。

HashMap 源码中包含了以下几个属性：

// HashMap 初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


// HashMap 最大长度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824


// 默认的加载因子 (扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;


// 转换红黑树的临界值，当链表长度大于此值时，会把链表结构转换为红黑树结构
static final int TREEIFY_THRESHOLD = 8;


// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;


// 最小树容量
static final int MIN_TREEIFY_CAPACITY =

什么是加载因子？加载因子为什么是 0.75？

加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。

那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢？

这其实是出于容量和性能之间平衡的结果：

当加载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生 Hash 冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；
而当加载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。

所以综合了以上情况就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

HashMap 源码中三个重要方法： 查询、新增 和 数据扩容。

先来看查询源码：

public V get(Object key) {
    Node<K,V> e;
    // 对 key 进行哈希操作
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 非空判断
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个元素是否是要查询的元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 下一个节点非空判断
        if ((e = first.next) != null) {
            // 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 非树结构，循环节点判断
                // hash 相等并且 key 相同，则返回此节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

从以上源码可以看出，当哈希冲突时我们需要通过判断 key 值是否相等，才能确认此元素是不是我们想要的元素。

OK，这节课就讲到这里啦，下一课时我将分享“线程的状态有哪些？它是如何工作的？”，记得按时来听课哈。

本文选自：拉勾教育《Java 源码剖析 34 讲》

原文 https://segmentfault.com/a/1190000022594859

正文到此结束