RELATEED CONSULTING
相关咨询
选择下列产品马上在线沟通
服务时间:9:30-18:00
你可能遇到了下面的问题
关闭右侧工具栏
Java Collections---HashMap深度分析与比较
  • 作者:zhaozj
  • 发表时间:2020-12-23 10:35
  • 来源:未知

文章声明,本文章完全是本人原创,当鉴于水平有限,如有错误,请各位同人指正!感谢万分!   在Java的世界里,无论类还是各种数据,其结构的处理是整个程序的逻辑以及性能的关键。由于本人接触了一个有关性能与逻辑同时并存的问题,于是就开始研究这方面的问题。找遍了大大小小的论坛,也把《Java 虚拟机规范》,《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》,和《Think 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》可恨的是,我之前就一直在找,我都找不到,他这样一提,我就更加急了,可惜口袋空空啊~~5555

    不知道大家有没有留意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的结构,大家也十分明白了吧?