`

Java中对HashMap的深度分析

阅读更多
 HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢?
在Java的世界里,无论类还是各种数据,其结构的处理是整个程序的逻辑以及性能的关键。由于本人接触了一个有关性能与逻辑同时并存的问题,于是就开始研究这方面的问题。找遍了大大小小的论坛,也把《Java 虚拟机规范》,《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》,和《Thinking in Java》翻了也找不到很好的答案,于是一气之下把JDK的src 解压出来研究,扩然开朗,遂写此文,跟大家分享感受和顺便验证我理解还有没有漏洞。 这里就拿HashMap来研究吧。

HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢?

在这之前,先介绍一下负载因子和容量的属性。大家都知道其实一个 HashMap 的实际容量就 因子*容量,其默认值是 16×0.75=12; 这个很重要,对效率很一定影响!当存入HashMap的对象超过这个容量时,HashMap 就会重新构造存取表。这就是一个大问题,我后面慢慢介绍,反正,如果你已经知道你大概要存放多少个对象,最好设为该实际容量的能接受的数字。

两个关键的方法,put和get:

先有这样一个概念,HashMap是声明了 Map,Cloneable, Serializable 接口,和继承了 AbstractMap 类,里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现,当然还有一个很重要的继承了Map.Entry 的 Entry 内部类,由于大家都有源代码,大家有兴趣可以看看这部分,我主要想说明的是 Entry 内部类。它包含了hash,value,key 和next 这四个属性,很重要。put的源码如下

public Object put(Object key, Object value) {
Object k = maskNull(key); 

这个就是判断键值是否为空,并不很深奥,其实如果为空,它会返回一个static Object 作为键值,这就是为什么HashMap允许空键值的原因。

int hash = hash(k);
int i = indexFor(hash, table.length);


这连续的两步就是 HashMap 最牛的地方!研究完我都汗颜了,其中 hash 就是通过 key 这个Object的 hashcode 进行 hash,然后通过 indexFor 获得在Object table的索引值。

table?不要惊讶,其实HashMap也神不到哪里去,它就是用 table 来放的。最牛的就是用 hash 能正确的返回索引。其中的hash算法,我跟JDK的作者 Doug 联系过,他建议我看看《The art of programing vol3》可恨的是,我之前就一直在找,我都找不到,他这样一提,我就更加急了,可惜口袋空空啊!

不知道大家有没有留意 put 其实是一个有返回的方法,它会把相同键值的 put 覆盖掉并返回旧的值!如下方法彻底说明了 HashMap 的结构,其实就是一个表加上在相应位置的Entry的链表:

for (Entry e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
Object oldvalue = e.value;
e.value = value; //把新的值赋予给对应键值。
e.recordAccess(this); //空方法,留待实现
return oldvalue; //返回相同键值的对应的旧的值。
}
}
modCount++; //结构性更改的次数
addEntry(hash, k, value, i); //添加新元素,关键所在!
return null; //没有相同的键值返回
}

我们把关键的方法拿出来分析:
void addEntry(int hash, Object key, Object value, int bucketIndex) {
table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);

因为 hash 的算法有可能令不同的键值有相同的hash码并有相同的table索引,如:key=“33”和key=Object g的hash都是-8901334,那它经过indexfor之后的索引一定都为i,这样在new的时候这个Entry的next就会指向这个原本的table[i],再有下一个也如此,形成一个链表,和put的循环对定e.next获得旧的值。到这里,HashMap的结构,大家也十分明白了吧?
if (size++ >= threshold) //这个threshold就是能实际容纳的量
resize(2 * table.length); //超出这个容量就会将Object table重构


所谓的重构也不神,就是建一个两倍大的table(我在别的论坛上看到有人说是两倍加1,把我骗了),然后再一个个indexfor进去!注意!!这就是效率!!如果你能让你的HashMap不需要重构那么多次,效率会大大提高!

说到这里也差不多了,get比put简单得多,大家,了解put,get也差不了多少了。对于collections我是认为,它是适合广泛的,当不完全适合特有的,如果大家的程序需要特殊的用途,自己写吧,其实很简单。(作者是这样跟我说的,他还建议我用LinkedHashMap,我看了源码以后发现,LinkHashMap其实就是继承HashMap的,然后override相应的方法,有兴趣的同人,自己looklook)建个 Object table,写相应的算法,就ok啦。

举个例子吧,像 Vector,list 啊什么的其实都很简单,最多就多了的同步的声明,其实如果要实现像Vector那种,插入,删除不多的,可以用一个Object table来实现,按索引存取,添加等。

如果插入,删除比较多的,可以建两个Object table,然后每个元素用含有next结构的,一个table存,如果要插入到i,但是i已经有元素,用next连起来,然后size++,并在另一个table记录其位置。
分享到:
评论

相关推荐

    2022年Java中对HashMap的深度分析Java教程.docx

    本教程将深入分析2022年Java中HashMap的内部机制、关键属性和操作。 HashMap的核心属性包括容量(capacity)和负载因子(load factor)。容量是指HashMap可以存储的元素的最大数量,而负载因子则是HashMap在达到多...

    java hashmap 深度剖析,和hashmap 相关面试题

    java hashmap 深度剖析,和hashmap 相关面试题

    HashMap源码深度剖析.md

    HashMap源码深度剖析,面试必备

    Java深度历险_Java深度历险

    《Java深度历险》这本书是Java开发者的一本深入学习指南,它涵盖了Java编程语言的核心概念、高级特性以及实际开发中的应用技巧。通过本书,读者可以系统地了解Java的各个方面,从而提升自己的编程技能和问题解决能力...

    java集合深度学习

    总的来说,理解HashMap和HashTable之间的差异是Java集合框架深度学习的关键部分。在选择使用哪个类时,需要根据具体的应用场景和性能需求来决定。同时,深入理解这些类的内部实现,有助于编写更高效、更安全的Java...

    [图灵社区]《深度学习搜索引擎开发:Java实现》源代码.zip

    《深度学习搜索引擎开发:Java实现》是一本专著,...通过研究这些源代码,读者不仅可以了解深度学习搜索引擎的工作原理,还能学习到如何在Java环境中实际应用深度学习技术,这对于软件开发者来说是一次宝贵的实践经验。

    最牛X的高级java书籍《java深度历险》(深入java,适合中、高级java程序员)

    《Java深度历险》是一本面向中、高级Java程序员的权威书籍,旨在帮助读者深入理解Java语言的核心概念和高级特性,提升编程技能和解决问题的能力。这本书涵盖了Java开发的多个重要领域,包括但不限于JVM(Java虚拟机...

    JAVA2深度历险_简体版(PDF格式)

    此外,书中可能还会涉及Java的异常处理策略、设计模式、单元测试、日志记录、性能分析等实用技能,以及如何利用Java开发企业级应用和分布式系统。 通过阅读《JAVA2深度历险_简体版》,读者不仅可以全面了解Java语言...

    Java常见笔试、面试题目深度剖析

    提供的资源如"Java常见笔试、面试题目深度剖析一(未加密).exe"和"Java常见笔试,面试题目深度剖析.ppt"应包含了对这些知识点的详细解析和实例,对于复习和准备是非常有价值的。建议考生结合这些资料进行系统性学习,...

    Java 深度历险.pdf

    4. **集合框架**: 集合是Java编程中不可或缺的一部分,书会深入讲解ArrayList、LinkedList、HashSet、HashMap等容器的使用及它们之间的区别,以及泛型、迭代器、并发集合等内容。 5. **多线程编程**: Java提供了...

    Java集合框架深度解析:Map, List, Set

    重要的是理解如何处理并发问题,特别是在Java 8中对HashMap的优化,如高低位拆分转移方式,避免了JDK 7中出现的链表环问题。ConcurrentHashMap的探讨显得尤为重要,它通过分段锁和CAS操作确保了更高的并发安全。这...

    java深度历险

    《Java深度历险》是一本面向已有一定Java基础的学习者,旨在深化理解并提升Java编程技能的专业书籍。作者王森,以其丰富的编程经验和深入的...通过阅读本书,你将对Java有更深的认识,从而在开发工作中更加得心应手。

    Java常见笔试、面试系列深度剖析第3讲

    在本节"Java常见笔试、面试系列深度剖析第3讲"中,我们将深入探讨Java编程语言的一些关键概念和常见问题,这些内容对于准备Java相关的笔试和面试至关重要。讲解由张龙和风中叶两位专家主讲,他们将分享丰富的经验与...

    深度学习java及其算法详解

    在“深度学习java及其算法详解”这一资源中,我们探讨的是如何将Java编程语言与深度学习技术相结合,以及深入理解基础的计算机科学概念,特别是数据结构和算法。Java是一种广泛应用于企业级应用、移动开发(如...

    java深度历险 详细讲解了java的package机制等

    在Java编程语言中,`package`和`import`机制是构建大型、模块化代码库的关键要素,它们有助于组织和管理类以及确保代码的可重用性。本篇将深入探讨这两个概念,以及如何通过Visual Studio .NET来操控Java虚拟机(JVM...

    Java深度历险

    - 深入解析ArrayList、LinkedList、HashMap、HashSet等常用集合类的内部实现,以及它们的性能特点和适用场景。 9. **IO与NIO** - 介绍传统的Java IO流体系,以及后来引入的非阻塞IO(NIO)和新NIO.2 API,包括...

    Java常见笔试,面试题目深度剖析

    下面将对这些领域进行深入解析,帮助你更好地准备Java相关的技术面试。 ### 字符串(String) 字符串在Java中是常用的数据结构,面试中经常涉及的话题包括字符串的不可变性、字符串连接效率、`String`、`...

    JAVA2深度历险.pdf

    首先,书中可能涵盖了Java核心类库的深度解析,包括集合框架、多线程、网络编程等。集合框架是Java中处理数据结构的关键部分,如ArrayList、LinkedList、HashMap、HashSet等,它们的工作原理和高效使用技巧都是进阶...

Global site tag (gtag.js) - Google Analytics