Java HashMap实现原理分析（一）

2024-07-29 05:30:43

从本文开始，介绍一下最常用的一个集合对象HashMap，HashMap存储的是键值对，本文采用的基于JDK11的源码实现。一般大家都知道HashMap是通过put操作把一组键值对（key和value）存储到HashMap中，然后可以通过get(key)去获取key对应的value。而最重要的这两个过程是怎么实现的呢？下面我们就来对put和get这两个过程做一个分析。

HashMap基本工作原理

下面先看一段源码:

/**
   * The table, initialized on first use, and resized as
   * necessary. When allocated, length is always a power of two.
   * (We also tolerate length zero in some operations to allow
   * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

当用户调用put方法的时候把key和value放入到HashMap的时候，这个数组table就是实际存储key和value的地方。HashMap把用户传入的key和value封装成一个Node<K,V>对象，把该Node<K,V>对象放入到table对应的位置。Map执行get操作的时候，并没有传入具体的数组的索引位置信息，只是传入了key，因此这个地方就会涉及到一个key转索引的一个操作，然后根据索引获取table中对应位置的Node对象，把value值返回给用户。由于数组的访问时间复杂度是O(1)，因此Map的get操作也可以认为是O(1)（这个地方先暂时理解为O(1),具体原因见后面）。

简单来说，在执行put方法的时候，Map会根据传入的key获取它hashcode值，然后根据hashcode与table大小进行求模运算，得到的值就是它在table数组索引位置。实际这个过程又有点复杂，具体下面开始分析。

HashMap 数组寻址与hash值计算

用户通过key访问map获取value的时候，原理是用key的hash值来与数组的大小取模获取数组的索引。但实际在HashMap实现中，对取模运算进行了一下优化，采用了(n-1) & hash(key)的方法获取数组索引，这里的n是table的大小，hash(key)表示key的哈希值，这种方法可以得到与取模运算一样的效果，但是速度要比取模运算快。

下面看一下，hash(key)的实现逻辑

static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

从上面的源码看：

调用key的hashCode()方法获取hashCode值h
把h进行无符号右移16位
把h与h右移后的值进行异或操作最后得到key的hash值。

这里大家比较好奇，为什么会进行这种复杂操作，他的用意是什么？下面来给大家说一下这个过程。

假设 table的大小是16，key1和Key2调用hashCode方法获取的值的二进制形式分别是：

1111 1111 1111 1101 0000 0000 0000 0001  # key1
1111 1111 1111 1111 0000 0000 0000 0001  # key2

首先我们直接使用key1和key2的hashCode获取的值去计算在的table的索引值。
具体过程是：

# key1在table中索引的计算过程与结果
1111 1111 1111 1101 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0000 1111  &  #n-1的二进制
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001 # 得到的table索引是1

# key2在table中索引的计算过程与结果
1111 1111 1111 1111 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0000 1111  &  #n-1的二进制
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001 #得到的table索引是1

根据上面计算结果可知，虽然key1和key2值不同，但是最后得到的table的索引都是1，这样就会出现了冲突。主要原因是在与n-1进行&操作的时候，通常n的值比较小，因此高16位都是0，这样0和任何数&结果都是0。通常key的hashCode取值很不固定。从最高位到最低位都会出现1的可能。比如key1和key2，他们的区别恰恰是出现在自己的hashCode的高16位，因此key1和key2与n-1进行&操作的结果是一样的。如果key1和key2经过hash()方法处理后呢，来看看结果：

# key1在table中索引的计算过程与结果
  1111 1111 1111 1101 0000 0000 0000 0001 #key1本身
^  0000 0000 0000 0000 1111 1111 1111 1101 #key1右移16的值
-----------------------------------------------
  1111 1111 1111 1111 1111 1111 1111 1100   # hash(key1)计算后的值
&  0000 0000 0000 0000 0000 0000 0000 1111   #n-1的二进制
-----------------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1100 #得到的table索引是12

# key2在table中索引的计算过程与结果
  1111 1111 1111 1111 0000 0000 0000 0001  #key2本身
^  0000 0000 0000 0000 1111 1111 1111 1111  #key2右移16的值
-----------------------------------------------
  1111 1111 1111 1111 1111 1111 1111 1110   #hash(key1)计算后的值
&  0000 0000 0000 0000 0000 0000 0000 1111   #n-1的二进制
-----------------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1110 #得到的table索引是14

这样key1和key2不会出现位置冲突。当key和自己的高16位进行异或操作的后的值的低16位中同时保留了原始key低16位和高16位的特征。因此key1和key2再和n-1进行&运算时，减少了出现相同值的可能性。明白了这些内容内容，下一篇文章开始结束HashMap的put和get方法的实现原理。

以上就是Java HashMap实现原理分析（一）的详细内容，更多关于Java HashMap原理的资料请关注我们其它相关文章！

在Java中如何决定使用 HashMap 还是 TreeMap

HashMap简单总结: 1.HashMap 是链式数组(存储链表的数组)实现查询速度可以,而且能快速的获取key对应的value: 2.查询速度的影响因素有容量和负载因子,容量大负载因子小查询速度快但浪费空间,反之则相反: 3.数组的index值是(key 关键字, hashcode为key的哈希值, len 数组的大小):hashcode%len的值来确定,如果容量大负载因子小则index相同(index相同也就是指向了同一个桶)的概率小,链表长度小则查询速度快,反之index相同的概率大
java中hashmap容量的初始化实现

HashMap使用HashMap(int initialCapacity)对集合进行初始化. 在默认的情况下,HashMap的容量是16.但是如果用户通过构造函数指定了一个数字作为容量,那么Hash会选择大于该数字的第一个2的幂作为容量.比如如果指定了3,则容量是4:如果指定了7,则容量是8:如果指定了9,则容量是16. 为什么要设置HashMap的初始化容量在<阿里巴巴Java开发手册>中,有一条开发建议是建议我们设置HashMap的初始化容量. 下面我们通过具体的代码来了解下为什么会这么
学习Java HashMap，看这篇就够了

HashMap 是一个散列表,它存储的内容是键值对(key-value)映射. HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条记录的键为 null,不支持线程同步. HashMap 是无序的,即不会记录插入的顺序. HashMap 继承于AbstractMap,实现了 Map.Cloneable.java.io.Serializable 接口. HashMap 的 key 与 value 类型可以相同也可以不同,可以是字符串(Str
JAVA--HashMap热门面试题

1. 为什么我们建议在定义HashMap的时候,就指定它的初始化大小呢? 答:在当我们对HashMap初始化时,如果没有为其设置初始化容量,那么系统会默认创建一个容量为16的大小的集合.当我们向HashMap中添加元素时,如果HashMap的容量值超过了它的临界值(默认16*0.75=12)时,(0.75是HashMap的加载因子)HashMap将会重新扩容到下一个2的指数次幂(2^4=16 下一个2的指数次幂是2^5=32).由于HashMap扩容要进行resize的操作,频繁的resize,
java在hashmap初始化时赋初值过程解析

Java中的HashMap是一种常用的数据结构,一般用来做数据字典或者Hash查找的容器. 一般我们初始化并赋初值是这样做的: HashMap<String, Object> map = new HashMap<>(); map.put("name", "yanggb"); map.put("lover", "huangq"); 但是有时候我们会想在一个表达式中完成初始化并赋初值的操作: HashMap
Java实现简易HashMap功能详解

本文实例讲述了Java实现简易HashMap功能.分享给大家供大家参考,具体如下: 创建节点类节点类含有的属性:键值对(value,key)以及指向下一节点的next: 这些属性的get以及set方法代码如下: /** * 节点类 * @author HP * */ public class Node { private Object value; private Object key; private Node next; /** * 空节点 */ public Node() { } /*
JAVA中哈希表HashMap的深入学习

深入浅出学Java--HashMap 哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解,并对JDK7的HashMap源码进行分析. 一.什么是哈希表在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能数组:采用一段连续的存储单元来存储数据.对于指定下标的查找,时间复杂度为O(1):通过给定值进
Java中遍历ConcurrentHashMap的四种方式详解

这篇文章主要介绍了Java中遍历ConcurrentHashMap的四种方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下方式一:在for-each循环中使用entries来遍历 System.out.println("方式一:在for-each循环中使用entries来遍历");for (Map.Entry<String, String> entry: map.entrySet()) { System.out.pr
Java HashMap三种循环遍历方式及其性能对比实例分析

本文实例讲述了Java HashMap三种循环遍历方式及其性能对比.分享给大家供大家参考,具体如下: HashMap的三种遍历方式 (1)for each map.entrySet() Map<String, String> map = new HashMap<String, String>(); for (Entry<String, String> entry : map.entrySet()) { entry.getKey(); entry.getValue();
Java HashMap实现原理分析（一）

从本文开始,介绍一下最常用的一个集合对象HashMap,HashMap存储的是键值对,本文采用的基于JDK11的源码实现. 一般大家都知道HashMap是通过put操作把一组键值对(key和value)存储到HashMap中,然后可以通过get(key)去获取key对应的value.而最重要的这两个过程是怎么实现的呢?下面我们就来对put和get这两个过程做一个分析. HashMap基本工作原理下面先看一段源码: /** * The table, initialized on first us
详解 Java HashMap 实现原理

HashMap 是 Java 中最常见数据结构之一,它能够在 O(1) 时间复杂度存储键值对和根据键值读取值操作.本文将分析其内部实现原理(基于 jdk1.8.0_231). 数据结构 HashMap 是基于哈希值的一种映射,所谓映射,即可以根据 key 获取到相应的 value.例如:数组是一种的映射,根据下标能够取到值.不过相对于数组,HashMap 占用的存储空间更小,复杂度却同样为 O(1). HashMap 内部定义了一排"桶",用一个叫 table 的 Node 数组表示:
Java 动态代理原理分析

Java 动态代理原理分析概要 AOP的拦截功能是由java中的动态代理来实现的.说白了,就是在目标类的基础上增加切面逻辑,生成增强的目标类(该切面逻辑或者在目标类函数执行之前,或者目标类函数执行之后,或者在目标类函数抛出异常时候执行.Spring中的动态代理是使用Cglib进行实现的.我们这里分析的是JDK中的动态代理实现机制. 下面我们通过例子快速了解JDK中的动态代理实现方式. 示例需要代理的接口 public interface IHello { public void sayHel
java 中ThreadPoolExecutor原理分析

java 中ThreadPoolExecutor原理分析线程池简介 Java线程池是开发中常用的工具,当我们有异步.并行的任务要处理时,经常会用到线程池,或者在实现一个服务器时,也需要使用线程池来接收连接处理请求. 线程池使用 JDK中提供的线程池实现位于java.util.concurrent.ThreadPoolExecutor.在使用时,通常使用ExecutorService接口,它提供了submit,invokeAll,shutdown等通用的方法. 在线程池配置方面,Executor
Java Servlet 运行原理分析

1 Servlet基本执行过程 Web容器(如Tomcat)判断当前请求是否第一次请求Servlet程序 . 如果是第一次,则Web容器执行以下任务: 加载Servlet类. 实例化Servlet类. 调用init方法并传入ServletConfig对象如果不第一次执行,则: 调用service方法,并传入request和response对象 Web容器在需要删除Servlet时(例如,在停止服务器或重新部署项目时)将调用destroy方法. 2 Web容器如何处理Servlet请求 Web容
Java CompletableFuture实现原理分析详解

目录简介 CompletableFuture类结构 CompletableFuture回调原理 CompletableFuture异步原理总结简介前面的一篇文章你知道Java8并发新特性CompletableFuture吗?介绍了CompletableFuture的特性以及一些使用方法,今天我们主要来聊一聊CompletableFuture的回调功能以及异步工作原理是如何实现的. CompletableFuture类结构 1.CompletableFuture类结构主要有两个属性 pub
java中HashMap的原理分析

我们先来看这样的一道面试题: 在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型.放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么? 文中已给出示例代码与答案,但关于HashMap的原理没有做出解释. 1. 特性我们可以用任何类作为HashMap的key,但是对于这些类应该有什么限制条件呢?且看下面的代码: public class Person { priva
详解Java HashMap实现原理

HashMap是基于哈希表的Map接口实现,提供了所有可选的映射操作,并允许使用null值和null建,不同步且不保证映射顺序.下面记录一下研究HashMap实现原理. HashMap内部存储在HashMap内部,通过维护一个瞬时变量数组table (又称:桶) 来存储所有的键值对关系,桶是个Entry对象数组,桶的大小可以按需调整大小,长度必须是2的次幂.如下代码: /** * 一个空的entry数组,桶的默认值 */ static final Entry<?,?>[] EMPTY
深入解析java HashMap实现原理

Mark一下,同时可以很好的结合hashCode()和equals()方法,覆盖equals方法时最好覆盖hashcode(),保证equals的两个对象,hashcode也相等,反过来:hashcode()不等,一定能推出equals()也不等:hashcode()相等,equals()可能相等,也可能不等. 因为HashMap在get时,先比较hashcode,再比较equals,hashcode==&&equals,两者都为true,则认为是相同的key 1. HashMap概
javaSE基础java自定义注解原理分析

目录 1. 从注释的角度来理解注解 2.提出问题 3.编写注解 4.通过Java反射获取方法的注解信息结束注解在JavaSE中算是比较高级的一种用法了,为什么要学习注解,我想大概有以下几个原因: 1. 可以更深层次地学习Java,理解Java的思想. 2. 有了注解的基础,能够方便阅读各种框架的源码,比如hibernate,SpringMVC等等.里面就用到了大量的注解.即便无法阅读源码,以后使用这些框架,会有一种心理上的安全感. 3. 方便今后跟别人吹牛.(当然,这也很重要.) 好了,话不

Java HashMap实现原理分析（一）

相关推荐

随机推荐