昨天有人来公司面试,因为面试的地方和我坐的地方比较近,所以也听到了一部分内容。
问:Java 的 HashMap是怎么实现的?
答:通过键值对的形式保存需要存储的值。
很显然这个答案不是面试官要的,这个答案也引起了我的回忆。曾经我在面试时也被几次问道过这个问题,我当时也是类似的回答。所以今天抽空大致研究了下HashMap的源码。
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。
1.首先HashMap里面实现一个静态内部类Entry 其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。
2.既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:
存储时:
int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;
取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index]
到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理
3.疑问:如果两个key通过hash % Entry[].length得到的index相同,会不会有覆盖的危险?
这里HashMap里面用到链式数据结构的一个概念.上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方,第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A.一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。
到这里为止,HashMap的大致实现,我们应该已经清楚了。
当然HashMap里面也包含一些优化方面的实现,这里也啰嗦一下。
比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?
HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。
分享到:
相关推荐
"基于HashMap的用户标签处理兼Java中HashMap实现原理研究" 本文研究了基于HashMap的用户标签处理方法,并对Java中HashMap的实现原理进行了深入研究。HashMap是一种高效的数据结构,可以快速地存储和检索数据。本文...
在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...
Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向下一个Entry对象的引用。...
Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧
在Java中,HashMap是一种广泛使用的数据结构,它基于哈希表的Map接口实现。哈希表是一种通过哈希过程将键映射到特定位置的数据结构,该位置存储了键对应的值。在详细探讨Java中HashMap的工作机制之前,首先需要理解...
在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...
在Java编程中,HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的存储功能,具有快速存取和高效查找的特点。HashMap基于哈希表(也称为散列表)原理,通过键对象的哈希码来定位元素,进而实现O(1)...
《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...
综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...
总结起来,JDK1.8中的HashMap实现原理主要包括以下几个要点: 1. 链表散列结构:数组+链表,链表用于处理哈希碰撞。 2. 红黑树优化:当链表长度超过8时,转换为红黑树,减少查找、插入和删除的时间复杂度。 3. 内部...
HashSet是基于HashMap实现的,它不存储值,只存储键。当向HashSet添加元素时,实际上是在HashMap中添加键,而值是默认的null。由于HashSet没有值的概念,所以它不提供键值对的关联操作,仅提供基本的添加、删除和...
以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个...
在Java编程语言中,`HashMap`是`java.util`包中的一个核心类,它属于集合框架的一部分,主要用于存储键值对的数据结构。`HashMap`基于哈希表(散列表)实现,提供了快速的插入、删除和查找操作,平均时间复杂度为O(1...
HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...
在Java编程语言中,HashMap是基于哈希表实现的数据结构,它是Map接口的一个具体实现,提供了高效的插入、删除和查找操作。HashMap不保证元素的顺序,允许null键和null值。HashMap的工作原理主要依赖于哈希算法,通过...
Java 8还引入了新的HashMap实现,其中包含了红黑树(Red-Black Tree)结构,当哈希表的负载因子达到一定程度时,某些桶(Bucket)内的元素将被转换为红黑树,以提供更高效的查找、插入和删除操作。特别是对于键的...
HashMap是Java编程中不可或缺的数据结构,它提供了高效的键值对存储和检索能力。在深入探讨HashMap的原理之前,我们先来澄清几个基本概念。 1. **哈希码(Hash Code)**:HashMap依赖于对象的哈希码来进行快速查找...