Java Collections---HashMap深度分析与比较

文章声明，本文章完全是本人原创，当鉴于水平有限，如有错误，请各位同人指正！感谢万分！  在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