当前位置: 首页 > article >正文

Java高频面试之集合-12

hello啊,各位观众姥爷们!!!本baby今天来报道了!哈哈哈哈哈嗝🐶

面试官:HashMap 的 hash 函数是怎么设计的?

HashMap的hash函数设计核心在于减少碰撞、提高数据分布均匀性,具体实现分为以下步骤:

1. 扰动函数处理

对键的原始hashCode进行高位与低位异或,增加低位随机性:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 作用:将hashCode的高16位右移后与低16位异或,使得高位信息参与低位运算,避免仅依赖低位导致碰撞率升高。

2. 下标计算

通过(n-1) & hash确定数组索引:

  • n为2的幂(如默认16),n-1的二进制全为1(例如15对应1111),位与操作等效于取模运算(但效率更高)。
  • 优势:位运算比取模快,且保证下标均匀分布在数组范围内。

3. 碰撞优化

  • 链表与红黑树:当链表长度≥8时转为红黑树(查找时间复杂度O(log n)),长度≤6时恢复链表,平衡性能与空间。
  • 扩容机制:负载因子默认0.75,当元素数超过阈值时扩容为原数组2倍,重新分配元素位置。

关键设计思想

设计要点实现方式作用
高位扰动异或操作(h ^ (h >>> 16))减少低位重复导致的碰撞
高效取模位运算((n-1) & hash)替代取模运算,提高速度
动态数据结构链表(O(n))与红黑树(O(log n))自动转换避免极端情况下性能退化
负载因子默认0.75(空间与时间折中)控制扩容阈值,平衡内存使用率和查询效率

示例说明

假设键的hashCode为0x12345678,数组长度n=16:

  1. 扰动计算0x12345678 ^ (0x12345678 >>> 16) = 0x12345678 ^ 0x00001234 = 0x1234444C
  2. 确定下标(16-1) & 0x1234444C = 15 & 0x444C = 12(最终存储到数组第12个位置)。

通过这种设计,HashMap在大多数情况下能高效处理数据插入与查询,同时保持较低的碰撞概率。

在这里插入图片描述


http://www.kler.cn/a/585882.html

相关文章:

  • 守护夏日安全防线:视觉分析驱动的区域入侵检测
  • PDF Reader
  • LLM推理和优化(2):节省KV Cache
  • 大白话阐述react和vue高阶组件的概念、优势及应用场景,以及区别,给出简单高阶组件的实现代码
  • 软件/硬件I2C读写MPU6050
  • SSL 原理及实验
  • MyBatis 如何解析 XML 配置文件和 SQL 映射文件
  • 1141. 【贪心算法】排队打水
  • LinuX---Shell---流程控制
  • VSTO(C#)Excel开发8:打包发布安装卸载
  • 开源后台管理系统推荐
  • oracle中OS BLOCK的含义
  • naive ui 控制 n-input 只可以输入26个英文字母+数字
  • 方差缩减梯度算法
  • 【嵌入式】嵌入式系统中的 SemVer 版本控制方案
  • 网络安全信息收集[web子目录]:dirsearch子目录爆破全攻略以及爆破字典结合
  • Flutter三棵树是什么,为什么这么设计
  • SpringBoot解决跨域
  • 鸿蒙app 开发 高效的 存储 数据 推荐使用 @tencent/mmkv(V2.1.0):
  • 计算矩阵边缘元素之和(信息学奥赛一本通-1121)