在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记录其位置。
本文转自 ☆★ 包罗万象网 ★☆ - http://www.baoluowanxiang.com 转载请注明出处,侵权必究!
原文链接:http://www.baoluowanxiang.com/a/program/java/2010/0503/684.html
分享到:
相关推荐
2022年Java中对HashMap的深度分析Java教程.docx
HashMap源码深度剖析,面试必备
·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的方方面面,全而不冗余 ·全程内容涵盖数据结构、设计模式、JVM内存...
java面试笔试资料包括JAVA基础核心知识点深度学习Spring面试题等资料合集: JAVA核心知识点整理-282页 Java与哈希算法.docx Java中Lambda表达式的使用.docx JAVA多线程之线程间的通信方式.docx Java注解详解.docx ...
本文将对Java常见面试题进行总结和解析,旨在为准备面试的Java开发者提供全面而深入的学习参考。以下是一些关键的Java面试题目类别及其概述: Java集合框架:这部分问题关注ArrayList、LinkedList、HashMap、HashSet...
JAVA企业级基础课题(HashMap那些事) 企业架构师必备技能(JAVA核心技术反射) JavaWeb之基础(手写实现Tomcat服务器) java多线程编程 纯手写实现SpringIOC实现过程 JEE企业级开发(企业级项目开发权威指南) 网络爬虫之...
09MySQL深度原理解析 10Netty深度源码解读 11SpringCloud微服务框架源码解读 12彻底搞懂分布式锁架构设计原理 13分布式数据一致性设计原理 14分布式消息中间件 15实战新零售微服务电商项目 16实战新零售微服务电商...
最新更新:修正HashMap1.8中变树阈值部分泊松分布的概率分布图 网络通信 操作系统层面 Redis 最新更新:Redis分布式锁细节补充 Spring Bean 声明周期 & 循环依赖 更新2021-1-27:补充生命周期AOP处理 及 ...
java内核源码 Java指南针 基础核心 基础知识 反射 泛型 动态代理 JDK8新特性 集合容器 多线程与并发 Spring SpringMVC SpringBoot Mybatis 数据结构与算法 入门基础 基础数据结构 数组&链表 数组&链表进阶 栈 队列 ...
常用集合底层原理深度解析,包括arraylist,hashmap,hashset,linkedarrayList,面试必备!
java lru leetcode Python 的算法游乐场 这是 Python 版,也有 Java 版。 目前,这是一个纯 Python 项目,并且支持 PyCharm IDE,因此您可以随意在 Python 中打开该项目。 单元测试正在使用内置单元测试(将来可能会...
冒泡排序,插入排序,选择排序,快速排序,堆排序,合并排序,广度优先搜索,深度优先搜索,二进制搜索,lru,dijkstra,A *(计划中) 概念 位操作,OOP,动态编程,图形(计划的) 破解编码面试 (〜2.7。交集) ...
用数组值查找排列位置想要达到O(1),用HashMap--常用技巧。 20有效的括号:【栈】。 21合并两个有序链表:可以【循环】,也可以采用【递归】。 53最大子序和:一次循环,maxEndingHere存储以该点结尾的子序和,...