`
laotu5i0
  • 浏览: 143670 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Java中HashMap的实现原理

    博客分类:
  • java
阅读更多

昨天有人来公司面试,因为面试的地方和我坐的地方比较近,所以也听到了一部分内容。

 

问: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[]会以一定的规则加长长度。

2
2
分享到:
评论
4 楼 MyDreamNotDream 2013-05-21  
看代码看到这里很不容易呢。
3 楼 四书五经 2013-04-11  
to 楼上的 SonofGod :

这个时候这样去获取:
如果(值 等于 你想要的值) 返回该值
(抱歉,公司里面不能贴代码,以上自己转换成代码。)否则hashMap会继续next下去.

其实,当冲突发生时,它会用next链接起所有的元素,且所有的元素是按一种类似栈的形式存放的(也就是说,先来的放最后,后来的放最上面)

建议看下这个,debug下:
http://winse.iteye.com/blog/1331725
2 楼 SonofGod 2012-12-07  
请问 楼主 在疑问3中。多个key的hash值一样的话,存储时通过链式的指向存储的。正如你说的C.next = B,Entry[0] = C 这样;那么取值时候是如何定位到的呢?如想获得B的Value。
1 楼 SonofGod 2012-12-07  
请问 楼主 在疑问2中。多个可以的hash得到一样的hash值后存储时通过链式的指向存储好了。正如你说的C.next = B,Entry[0] = C;那么取得时候是如何定位到的呢?如想获得B的Value。

相关推荐

    基于HashMap的用户标签处理兼Java中HashMap实现原理研究.pdf

    "基于HashMap的用户标签处理兼Java中HashMap实现原理研究" 本文研究了基于HashMap的用户标签处理方法,并对Java中HashMap的实现原理进行了深入研究。HashMap是一种高效的数据结构,可以快速地存储和检索数据。本文...

    hashmap实现原理

    在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...

    java HashMap原理分析

    Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向下一个Entry对象的引用。...

    Java8 HashMap的实现原理分析

    Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧

    Java中HashMap的工作机制

    在Java中,HashMap是一种广泛使用的数据结构,它基于哈希表的Map接口实现。哈希表是一种通过哈希过程将键映射到特定位置的数据结构,该位置存储了键对应的值。在详细探讨Java中HashMap的工作机制之前,首先需要理解...

    深入Java集合学习系列:HashMap的实现原理

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

    自定义map实现java的hashmap

    在Java编程中,HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的存储功能,具有快速存取和高效查找的特点。HashMap基于哈希表(也称为散列表)原理,通过键对象的哈希码来定位元素,进而实现O(1)...

    Jdk1.8中的HashMap实现原理.docx

    《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...

    深入解析java HashMap实现原理

    综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...

    Jdk1.8中的HashMap实现原理.pdf

    总结起来,JDK1.8中的HashMap实现原理主要包括以下几个要点: 1. 链表散列结构:数组+链表,链表用于处理哈希碰撞。 2. 红黑树优化:当链表长度超过8时,转换为红黑树,减少查找、插入和删除的时间复杂度。 3. 内部...

    Java中HashMap详解(通俗易懂).doc

    HashSet是基于HashMap实现的,它不存储值,只存储键。当向HashSet添加元素时,实际上是在HashMap中添加键,而值是默认的null。由于HashSet没有值的概念,所以它不提供键值对的关联操作,仅提供基本的添加、删除和...

    详解Java HashMap实现原理

    以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个...

    Java-HashMap.rar_hashmap_java hashmap

    在Java编程语言中,`HashMap`是`java.util`包中的一个核心类,它属于集合框架的一部分,主要用于存储键值对的数据结构。`HashMap`基于哈希表(散列表)实现,提供了快速的插入、删除和查找操作,平均时间复杂度为O(1...

    HashMap底层原理

    HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...

    java中HashMap详解.pdf

    在Java编程语言中,HashMap是基于哈希表实现的数据结构,它是Map接口的一个具体实现,提供了高效的插入、删除和查找操作。HashMap不保证元素的顺序,允许null键和null值。HashMap的工作原理主要依赖于哈希算法,通过...

    Java8HashMap键与Comparable接口编程开

    Java 8还引入了新的HashMap实现,其中包含了红黑树(Red-Black Tree)结构,当哈希表的负载因子达到一定程度时,某些桶(Bucket)内的元素将被转换为红黑树,以提供更高效的查找、插入和删除操作。特别是对于键的...

    java中HashMap的原理分析

    HashMap是Java编程中不可或缺的数据结构,它提供了高效的键值对存储和检索能力。在深入探讨HashMap的原理之前,我们先来澄清几个基本概念。 1. **哈希码(Hash Code)**:HashMap依赖于对象的哈希码来进行快速查找...

Global site tag (gtag.js) - Google Analytics