经历一场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 讲》

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

以上是 经历一场Java面试,面对这些问题我竟然结巴了 的全部内容, 来源链接: utcz.com/z/516299.html

回到顶部