由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 ：

package hash;

import java.util.LinkedList;

public class HashStruct {
	// 定义一个数组
	private static int hashcode = 10;// hashcode值用于rehash时，重构hash结构
	private static LinkedList[] hasharray;
	private static int clashes;// 记录冲突数
	private static int numbers;// 记录结构内成员数

	// hash结构就是根据当前数值，通过hash函数，算得当前值应放入的hashstructure中的位置。
	// 设计hash函数
	public int hashFunction(int x) {
		int hash = x % hashcode;// hashcode为构建的hash函数中的一个变量
		return hash;
	}

	// 向hash结构中添加元素
	public void add(int key) {
		int index = this.hashFunction(key);
		if (hasharray[index].size()>0) {
			clashes++;
		}
		hasharray[index].add(key);

		numbers++;
		// 判断添加后冲突数是否超过峰值，如超过，重构hash结构
		if (this.rank(clashes, numbers)) {
			this.rehash(hasharray);
		}
	}

	// 当冲突数超过峰值时，需要重建hash结构
	public void rehash(LinkedList[] hasharray) {
		hashcode += 5;
		LinkedList[] hasharray2 = hasharray.clone();
		hasharray = null;
		this.init();
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < hasharray2[i].size(); j++) {
				this.add(hasharray2[i].get(j).hashCode());
			}
		}
		System.out.println("rehashed!");
	}

	// 峰值计算函数
	public boolean rank(int clash, int numbers) {
		boolean result = false;
		double c=(double) clash / (double) numbers;
		if (((double) clash / (double) numbers) >= 0.65) {
			result = true;
		}
		return result;
	}

	// 遍历对应hash值下的元素
	public void get() {
		for (int i = 0; i < hasharray.length; i++) {
			System.out.println("hasharray["+i+"]:"+hasharray[i]);
		}
	}

	// 初始化hashstruct
	public void init() {
		hasharray = new LinkedList[hashcode];
		clashes = 0;// 记录冲突数
		numbers = 0;// 记录结构内成员数
		for (int i = 0; i < hashcode; i++) {
			hasharray[i] = new LinkedList<Integer>();
		}
	}
}

 

Test ：

 

package hash;

public class Test {
	public static void main(String[] args) {
		HashStruct hs = new HashStruct();
		hs.init();
		// 添加10个数
		hs.add(10);
		hs.add(12);
		hs.add(22);
		hs.add(25);
		hs.add(15);
		hs.add(35);
		hs.add(27);
		hs.add(37);
		hs.add(47);
		hs.add(17);
		// 检查添加结果
			hs.get();

		//继续添加，验证rehash
		for(int i=1;i<20;i++){
			hs.add(i*7);
		}
		hs.get();
		
	}
}

 

 

图4：

  如上图 4 为输出结果。对比上图 1 和图 2 ，达到了 rehash 的效果。（蓝色线上是初始构建 hash 结构的测试，下方是 rehash 测试。注意红色标记为初始时插入测试的数据。）

       Array AND LinkedList Hashstructure 雌雄双剑剑法演示完毕，请各位看官出招。