行业知识
HashMap详解
2026-11-21 15:02:43
来源:互联网转载
手撕HashMap源码
HashMap一直是面试的重点。今天我们来了解了解它的源码吧!
首先���一下Map的继承结构图
源码分析
什么是哈希
**Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。**这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。
任何哈希函数基本都无法彻底避免碰撞两个不同的输入值,根据同一散列函数计算出的散列值相同的现象叫做碰撞。
HashMap 简介
HashMap 主要用来存放键值对,它基于哈希表的 Map 接口实现,是常用的 Java 集合之一。
HashMap 底层数据结构
JDK 1.8 之前 HashMap 底层是数组 + 链表 结合在一起使用,也就是 链表散列。数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(”拉链法”解决冲突)。
JDK 1.8 之后 HashMap 底层是数组 + 红黑树 。
当链表长度大于阈值(默认为 8)时,会首先调用 treeifyBin() 方法。
这个方法会根据 HashMap 数组来决定是否转换为红黑树。
只有当数组长度大于或者等于 64 的情况下,才会执行转换红黑树操作,以减少搜索时间。否则,就是只是执行 resize() 方法对数组扩容。
源码分析
类的属性:
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { // 序列号 private static final long serialVersionUID = 362498820763181265L; // 默认的初始容量是 16 static final int DEFAULT_INITIAL_CAPACITY = 1 final int hash;// 哈希值,存放元素到hashmap中时用来与其他元素hash值比较 final K key;// 键 V value;// 值 // 指向下一个节点 Node 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; } // 重写hashCode()方法 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 重写 equals() 方法 public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry
上一篇:默纳克服务器怎么选?
下一篇:服务器部署内容怎么填写?