解读Hashtable
http://perhaps.cnblogs.com/archive/2006/01/06/312335.html
昨天看到了叶漂兄的Post:《Hashtable的烦恼!》,文中提出有关Hashtable中键值对(key/value pair)排序的问题。其实所谓键值对的排序问题,实质上就是键(key)排序的问题。而一直以来,我都认为Hashtable中的键排序是随机的,因为自己有限的编程经验告诉我:键值对插入的顺序不同会影响键值对的输出顺序,实际上就是影响到键的输出顺序了。在和quitgame讨论了一番之后,我发觉问题远没有自己想象中那么简单。于是对Hashtable进行了一番看似钻牛角尖的研究,终于对Hashtable中键排序有了正确的认识。引发我去思考的C#代码可以参考叶漂的原文,以下给出的是Java的代码(公司里只有WSAD,也只能对Java代码进行分析了):
public static void main(String[] args){
Hashtable ht = new Hashtable();
ht.put("sichuan","chengdu"); //改变以下四行代码的顺序,可能会改变输出内容的顺序
ht.put("hunan","changsha");
ht.put("beijing","beijing");
ht.put("anhui","hefei");
Enumeration e = ht.keys();
while(e.hasMoreElements()) {
Object key = e.nextElement();
Object value = ht.get(key);
System.out.println(key + " " + value + " " + key.hashCode() + " " + value.hashCode());
}
}
}
为了讲述Hashtable键排序的问题,我们先来看Hashtable的结构图:
从上面的结构图可以看出,Hashtable的实质就是一个数组+链表。图中的Entry就是链表的实现,Entry的结构中包含了对自己的另一个实例的引用next,用以指向另外一个Entry。而图中标有数字的部分是一个Entry数组,数字就是这个Entry数组的index。那么往Hashtable增加键值对的时候,index会根据键的hashcode、Entry数组的长度共同决定,从而决定键值对存放在Entry数组的哪个位置。从这种意义来说,当键一定,Entry数组的长度一定的情况下,所得到的index肯定是相同的,也就是说插入顺序应该不会影响输出的顺序才对。然而,还有一个重要的因素没有考虑,就是计算index出现相同值的情况。譬如代码中 "sichuan" 和 "anhui",所得到的index是相同的,在这个时候,Entry的链表功能就发挥作用了:put方法通过Entry的next属性获得对另外一个Entry的引用,然后将后来者放入其中。根据debug得出的结果,"sichuan", "anhui"的index同为2,"hunan"的index为6,"beijing"的index为1,在输出的时候,会以index递减的方式获得键值对。很明显,会改变的输出顺序只有"sichuan"和"anhui"了,也就是说输出只有两种可能:"hunan" - "sichuan" - "anhui" - "beijing"和"hunan" - "anhui" - "sichuan" - "beijing"。以下是运行了示例代码之后,Hashtable的结果:
以上的讨论基于Java展开的,在C#中的Hashtable实现会有所不同,但是我相信两者的设计应该是差不多的。感谢叶漂和quitgame,给了我思考的机会,也让我感到了基础知识的匮乏,看来是要补补基础知识了。
[补充]:在Hashtable的实现代码中,有一个名为rehash的方法用于扩充Hashtable的容量。很明显,当rehash方法被调用以后,每一个键值对相应的index也会改变,也就等于将键值对重新排序了。这也是往不同容量的Hashtable放入相同的键值对会输出不同的键值对序列的原因。在Java中,触发rehash方法的条件很简单:hahtable中的键值对超过某一阀值。默认情况下,该阀值等于hashtable中Entry数组的长度×0.75。
最新文章
- Hibernate 系列 02 - Hibernate介绍及其环境搭建
- ExtJs布局详解
- SQLServer清空日志
- iOS开发:保持程序在后台长时间运行
- iOS开发——UI进阶篇(十八)核心动画小例子,转盘(裁剪图片、自定义按钮、旋转)图片折叠、音量震动条、倒影、粒子效果
- jsp页面间传递参数 中文乱码问题(zz)
- linux命令备份
- sts中从svn导入maven项目
- C#使用Process类调用外部程序(转)
- Windows环境下 配置memcached (php)
- Android——ViewPager多页面滑动切换以及动画效果
- linux下能ping ip不能ping域名详解
- openssl 生成CSR
- SVNKIT的low api应用之修改库中文件内容(File modification)
- VUE环境配置——运行Demo
- 最简单的基于FFmpeg的视频编码器-更新版(YUV编码为HEVC(H.265))
- Thread和Runnable的区别
- 第二篇:用Android Studio编写Hello World
- luogu 1268 树的重量
- python --- 18 类与类之间的关系, 特殊成员