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实现解析ini文件对应到JavaBean中

    要实现解析ini文件对应到JavaBean中,可以通过以下步骤进行: 1.引入依赖 要解析ini文件可以使用jedis的依赖,可以在pom.xml文件中加入以下代码来引入依赖: <dependency> <groupId>redis.clients</groupId> <artifactId>jedis<…

    Java 2023年6月15日
    00
  • java实现的AES加密算法完整实例

    下面是“Java实现的AES加密算法完整实例”的完整攻略: 一、概述 AES(Advanced Encryption Standard)是一种常用的对称加密算法,之前常用的DES算法已经不再安全。在Java中,可以通过javax.crypto包中的AES算法实现加密和解密。 二、实现步骤 生成AES密钥 KeyGenerator kgen = KeyGene…

    Java 2023年5月19日
    00
  • 关于Ubuntu Server 18.04 LTS 安装Tomcat并配置systemctl管理Tomcat服务的问题

    下面是详细讲解如何在Ubuntu Server 18.04 LTS系统上安装Tomcat并配置systemctl管理Tomcat服务的完整攻略。 1. 安装Tomcat 在Ubuntu Server 18.04 LTS系统上安装Tomcat的方法如下: 软件包更新:需要更新软件包列表和已安装软件包,以防止出现软件包依赖错误等问题,在终端中执行以下命令: su…

    Java 2023年5月19日
    00
  • JavaSpringBoot报错“WebApplicationException”的原因和处理方法

    当使用Java的Spring Boot框架时,可能会遇到“WebApplicationException”错误。这个错误通常是由以下原因之一引起的: 请求处理错误:如果请求处理过程中出现错误,则可能会出现此错误。在这种情况下,需要检查请求处理代码并进行必要的更改。 响应处理错误:如果响应处理过程中出现错误,则可能会出现此错误。在这种情况下,需要检查响应处理代…

    Java 2023年5月5日
    00
  • Java参数传递及值传递实现原理详解

    Java参数传递及值传递实现原理详解 Java中的参数传递涉及到两个概念:引用传递和值传递。本文将详细讲解Java参数传递及值传递的实现原理。 引用传递 引用传递是指将实参的地址作为形参传递。在Java中,在方法调用时,如果参数是对象类型,那么实参传递给形参的是对象地址的副本。也就是说,实参和形参指向同一块内存地址。 示例: public class Per…

    Java 2023年5月26日
    00
  • 使用Spirng Boot Admin监控Spring Cloud应用项目

    下面是使用Spring Boot Admin监控Spring Cloud应用项目的完整攻略: 1. 安装和配置Spring Boot Admin 首先,需要在Spring Boot应用项目中添加相关依赖,以便于引入Spring Boot Admin。在pom.xml中加入以下内容: <dependency> <groupId>de.c…

    Java 2023年5月20日
    00
  • SpringBoot统一处理功能实现的全过程

    SpringBoot是一种轻量级的Java框架,提供了一种快速开发的方式,这是因为它提供了大量的自动化配置。SpringBoot为Java开发人员提供了快速开发微服务应用程序所需的各种组件。其中包含了很多与Web应用程序相关的组件,包括MVC(Model-View-Controller)框架。本文将讲解如何实现一个SpringBoot应用程序的统一处理功能,…

    Java 2023年5月15日
    00
  • 结合Service层讲解DAO层的异常处理操作

    让我详细讲解一下“结合Service层讲解DAO层的异常处理操作”的攻略。 首先,我们需要理解DAO(Data Access Object)层的作用。DAO层的主要任务是实现数据的持久化操作,负责与数据库交互,为上层提供数据访问接口。在实现DAO层的过程中,异常处理也是至关重要的一部分。 DAO层的异常处理分为两种情况: SQL异常 SQL异常是指在数据库操…

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