Java面试题之HashMap 的 hash 方法原理是什么

HashMap 的 hash 方法原理是什么

在了解HashMap的原理之前, 我们先看看hash散列表是怎么工作的, 他的原理是什么。

散列表的原理是将关键字通过散列函数映射到固定的位置上, 并对原始值进行处理, 最终得到的值就是我们所说的哈希值, 即在HashMap中所表现出来的值。在JDK1.7之前,HashMap的内部实现方式是数组 + 链表,数组的下标就是哈希值,而链表则是解决哈希冲突的方案。而在JDK1.8之后,由于链表会引起频繁的GC,会对性能有影响,而添加了红黑树的设计,对冲突的解决更加高效。

比如在HashMap中,我们put一个新的键值对时,便会对新的key生成一个哈希值(hashCode),这个hashCode将会指导他在数组中的大致位置, 但有可能会存在相同的hashCode(即hash冲突),因此会通过拉链法(或者是红黑树)来使链表在当前位置上依次挂起来,这样既能保证查询时的O(1)速度,又能避免产生很多碰撞。

具体来说,当我们使用HashMap的put方法时,HashMap首先会对key进行hash计算,得到一个hash值。然后,HashMap会将这个hash值用来决定key-value存放在数组中的位置。

hash方法的实现原理

接下来是讲解hash方法的实现原理,hash方法是用来计算hashCode的,接下来是hash方法的代码实现:

static final int hash(Object key) {
    int h;
    // key.hashCode()计算出key的哈希值h
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在上面的实现中, 首先对键值调用key.hashCode()方法,确定键值的哈希值h。hashCode()的具体实现可以看做是从对象的物理地址、时间等因素来生成唯一标识。

在key为null的情况下,哈希值设为0。
为什么要进行以下位运算呢,在进行哈希值计算的时候借助到了以下位运算:

h ^ (h >>> 16)

这里是采用了hash分流算法, 具体步骤如下:

  • 按照hashcode和右移16的结果做异或,生成新的哈希值
  • 将新的哈希值除以容量size的余数,得到下标index
  • 如果当前下标没有hash冲突,则直接将其放入slots[index]中;
  • 如果当前下标有hash冲突,则将当前的键值对添加到当前下标对应的链表的最后;

然而hash散列并不是完美的算法, 在极端情况下可能出现hash冲突,即不同的两个key所对应的hash值是相同的,这就需要采取一些特殊处理的策略,例如拉链法或者是一些替代性的算法,这些算法都有其优劣性。对于比较简单的key值集合来说,HashMap可以将一个键值的HashCode直接映射为一个下标,这种情况下性能最好。

下面再举个栗子: 我们以五个关键字生成的hashCode为例,说一下在HashMap中如何定位分组的过程。

String s1= "name";
String s2 = "gender";
String s3 = "age";
String s4 = "addr";
String s5 = "phone";
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
System.out.println(s3.hashCode());
System.out.println(s4.hashCode());
System.out.println(s5.hashCode());

//分别输出如下, 
//名字(hashCode): 3373707
//性别(hashCode): 1967188755
//年龄(hashCode):95458899
//地址(hashCode): 3009914
//电话(hashCode): 3081039

所以, 当存储出现哈希冲突,我们可以通过维护链表的方式解决。例如, 有两个键值对[key1, value1]和[key2, value2],他们都对应了相同的哈希值h。那么,HashMap就将其存储在[h]位置的链表的尾部。这样,查询哈希表中任一键值对时,HashMap首先对该键值计算哈希值,然后找到[h]位置并遍历链表,在链表中找到一个哈希值和要查询的键值的哈希值相同的键值对。 haMap的hash方法原理和hash算法通过详细的讲解,我们已经能够对HashMap有了较全面的认识。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java面试题之HashMap 的 hash 方法原理是什么 - Python技术站

(0)
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • Java基础-Java编程语言发展史

    Java基础-Java编程语言发展史 Java的起源 Java是一种由Sun Microsystems公司于1995年推出的面向对象编程语言。最初,Sun公司希望开发一种嵌入式系统的语言,但是随着互联网的发展,Java被扩展为可以运行在任意平台上的通用编程语言。Java的诞生,极大地简化了跨平台应用程序的开发,也促进了互联网的发展。 Java的版本历史 Ja…

    Java 2023年5月23日
    00
  • Java基础教程之整数运算

    Java基础教程之整数运算攻略 Java是一种强类型语言,其中包含了整数类型及其运算操作。本文将详细讲解Java基础教程中的整数运算,包括基本概念、运算规则和示例说明。 基本概念 Java中的整数类型主要有四种:byte、short、int和long,对应的存储空间分别为1、2、4和8个字节。整数运算包括加、减、乘、除和取模等操作。 运算规则 Java中的整…

    Java 2023年5月26日
    00
  • Spring Security账户与密码验证实现过程

    下面是详细讲解”Spring Security账户与密码验证实现过程”的完整攻略。 Spring Security账户与密码验证实现过程 Spring Security 是一个功能强大的权限验证框架,它提供了多种认证方式,其中最常用的是账户与密码验证方式。本文将介绍实现 Spring Security 账户与密码验证的完整过程。 步骤一:添加 Spring …

    Java 2023年5月20日
    00
  • java编程之基于SpringBoot框架实现扫码登录

    下面我将详细讲解“Java编程之基于SpringBoot框架实现扫码登录”的完整攻略。 概述 本篇攻略将介绍如何通过SpringBoot框架实现扫码登录功能。扫码登录功能是近年来非常流行的一种登录方式,主要是便于用户的使用和提高安全性。 实现步骤 本文主要分为以下几个步骤: 配置开发环境 创建SpringBoot项目 实现扫码登录 测试运行 1. 配置开发环…

    Java 2023年5月19日
    00
  • Java实现记事本功能

    Java实现记事本功能一般可以分为以下几个步骤: 1. 创建GUI界面 利用Java Swing等工具,进行界面设计,实现如文件编辑区、菜单栏、工具栏、状态栏等基础功能的设计与实现。 2. 实现文件的读写功能 通过Java IO流,实现文件的打开、保存、另存为、关闭、撤销、重做等功能,使得用户可以对文本进行编辑、保存等操作。可以使用 FileInputStr…

    Java 2023年5月18日
    00
  • Java之Arrays的各种功能和用法总结

    Java之Arrays的各种功能和用法总结 简介 Java中的Arrays类提供了一组用于操作数组的静态方法。Arrays类中的方法支持对数组的排序、搜索、比较、填充和转换等操作,该类还提供了一个asList()方法来创建一个ArrayList. 方法列表 下面是Arrays类中一些常用方法的列表: 方法 描述 sort() 对数组进行排序。 binaryS…

    Java 2023年5月26日
    00
  • java去除中文括号小括号,或者英文括号的实例代码

    这里提供两个示例说明: 示例1:去除中文括号和小括号 public static String removeBrackets(String text) { if (text == null) return null; // 中文括号 text = text.replaceAll("[()()]", ""); retur…

    Java 2023年5月26日
    00
  • JavaEE账号注册模拟网站邮箱激活

    JavaEE账号注册模拟网站邮箱激活是一个常见的Web应用程序开发需求。具体实现这个功能的步骤如下: 1. 搭建Web应用程序 首先,需要搭建一个基于JavaEE的Web应用程序,这个应用程序会充当网站的后端服务器,接收客户端请求并返回数据。可以使用诸如Tomcat、Jetty等开源的Web服务器来搭建这个Web应用程序。 2. 设计数据库 建立数据库表,通…

    Java 2023年6月15日
    00
合作推广
合作推广
分享本页
返回顶部