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

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

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

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

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

典型回答

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

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

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 讲》

版权声明:本文版权归属拉勾教育及该专栏作者,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发布/发表,违者必究。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章