自定义hash结构.doc

由hash结构，看数据结构优化“宗法” 俗话说：“万变不离其宗”，程序亦是如此。 无论是HashSet、HashMap、Hashtable，还是TreeSet、PriorityQueue，都不离其原则。众所周知，衡量一个程序的好坏、数据结构好坏的重要指标是其空间复杂度和时间复杂度。“鱼和熊掌不可兼得”，时间复杂度和空间复杂度也不能兼顾。比如数组，由于存储空间物理上不连续，其空间占用大；而链表，虽然占用空间较小，而且可以充分利用零散的存储空间，但它没有数组所拥有的下标，导致其时间复杂度较高。 万事万物都有其制约因素，所以也就没有完全意义上的完美，但我们可以寻求“相对的完美”。时间复杂度和空间复杂度势必有一方要被舍弃，但高速发展的社会不仅要求时间上的高效，也要求空间上的资源高效利用。看官（应该有）要问了，“那怎么办呀”？ 我们聪明的老祖宗已经为我们埋下了伏笔。“中庸”的思想帮到了我们。既然各有优点，那何不有机的结合各种结构的优点，这样不就可以达到时间复杂度和空间复杂度的平衡点，也许会是黄金分割点。TreeSet就是个鲜明的例子，是tree结构和Set结构的有机结合，极大的提高了数据结构的“优雅”和“韵律”。 看到这，你也许以为，“有机结合各家所长”就是“宗”了。非也，宗者，乃假外物以为余是也。借助外力补足缺点才是王道。有机结合是通过结合利用其它结构补足自身补足。除此之外，通过适当的转换，也可以达到优化结构的目的。高中物理书中写道：“力是改变物体状态的原因”。对于IT男男女女来说，我们想要改变现有对象的状态时，添加方法就是我们的“力”。你没有下标，增加了时间复杂度。Ok，我将你跟连续的下标联系起来不就行啦！以hash结构为例，基本思想就是通过hash函数（即我们的“力”），改变原有的数据结构特点，以补不足。显然，HashSet就是用hash函数构造的Set；HashMap就是用hash函数构造的Map你若问我hash函数是什么？它是具体情况而定。 下面，以我自定义的hash结构为例。 构建一个简单的hash结构，流程如下：1、 利用hash函数得到hash值，通常为键值或下标位置。2、 将对应的属性值放入到对应键值或下标的相应位置。如选择的是键值对就放入集合内；如选择的是链表就放入节点，加在末尾如下图1。3、 因为是通过函数计算，且键值和下标的本地hashcode值通过计算可能相同，就会产生冲突，链表可以加在末尾，但随冲突的增加，链表越来越长，采用hash结构的优势越来越弱，此时就要重构hash结构。是否需要重构根据具体情况而设定的峰值而定。如下图2，为rehash后的结果。4、 于是出现了问题出现了，怎样重构更好呢？hash结构其实是通过hash函数对各个属性值的散列。既然是散列，就会有一个散列的程度问题。重构时，如能使当前结构内数据rehash后，其散列程度趋于0时，重构效果较好。统计学可以通过计算残差，判断之前的系统是否稳定，相信对于hash结构，同样适用。散列程度的值可以根据冲突数与总数据量之间的关系得到。如下图3。我的代码示例如下：图1：图2：图3：Hashstructure：略Test：略图4：如上图4为输出结果。对比上图1和图2，达到了rehash的效果。（蓝色线上是初始构建hash结构的测试，下方是rehash测试。