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