hash表

        编程中常用的存储方式有两种：数组与链表。数组实现了有序、连续的数据存储，使得数据查询变得高效，时间代价为⊙(n)，但是遇到数据的删除与插入时，当前插入点之后的所有数据都要前移或者后移，时间代价为⊙(n²)；相对于数组，链表在插入或者删除数据时只需要创建和更改相应的指针对象，所需代价较小⊙(n)，可是因为本身的无序特性，令数据的查询必须要每一次从头部节点开始遍历，耗费的时间较多。

        hash表采用了数组与链表的优点，通过初始化数组，数组节点内部套用链表结构的方式实现了插入与搜索的相对高效，规避了缺陷。

        要实现一个hash表，要从几部分来考虑：首先，要将数据存入已定义数组的相应位置，就必须有一个对应的法则，这就是hash函数，比如数字尾数为0，就存入数组的0号位置。实际操作中，通常通过取模运算实现对应关系，而为了使得整个数组的存储变的均衡，不会出现极端（所有插入的数据被放入了同一个位置，数组的其他位为空）情况，hash函数可以写为 存入值 mod 数组长度，在书写过程中，我也尝试了其他方式的取摸运算或者函数作为hash函数，发现在插入随机时，还是对数组长度取摸的方法效率最高，此部分代码如下：

int hash(int num,LinkNode[] array){
		int index = num % array.length;
		return index;
	}

 

 

 

        虽然有了方法确定插入数据的具体位置，但实际操作中我们会发现，两个数据经过了hash函数后所得的index（代替位置）是相同的，这是需要考虑的第二个问题—冲突。在上述定义中已经提到过，hash表的数组内部并不只是单独的存储数据，而是一个链表结构，当同一index有两个数据要插入，如上述LinkNode结构，第一个元素会被作为index处的data，第二个元素作为当前index的node.head.data存储，具体方法：

/**
	 * 插入数据的方法,每次插入后判断是否达到装在临界值
	 */
	void put(Item item,LinkNode[] array){
		//超过装载因子2，重建hash表
		if(count/array.length>=0.75){
			reHash();
			count = 0;//每一次的reHash，count都要清0，否则会成倍增长
			oldarray = new LinkNode[oldarray.length*2];
			for(int i=0;i<oldarray.length;i++){
				oldarray[i] = new LinkNode();
			}
			//遍历list，将取出的item重新计算后放入更新后的oldarray
			for(int j=0;j<list.size();j++){
				put(list.get(j),oldarray);
				//System.out.println("I am list"+j+": "+list.get(j).num);
			}
			put(item,oldarray);
		}else{
			//将放入的对象hash计算索引值
			int index = hash(item.num,array);
			//判断即将放入的位置,将插入的数据放在合适的位
			judge(array[index],item);
		}
	}

 

 

 

 

 judge方法在判断的过程中采用了递归，直到在index处找到空闲的位置放置当前的LinkNode节点）

 

      阅读上面代码时还可以看出，当我们put一个元素进入数组，有一个if、else的判断步骤，它的做法是初始化一个计数器count，每次添加一个元素进入数组，count++，如果某一次判断时发现数组中存储的元素已经大于等于当前数组长度的两倍，便调用reHash方法，扩大数组的长度，这也是我们要讨论的第三个问题。reHash方法的采用其实是为了保证hash表的操作效率，如果一个长度为10的数组里面插入了500个元素，那么在搜索时，尽管能够很快的定位到index，在这个index中也可能存在一个长度为50（取平均情况）的链表，过长的遍历寻找也会耗费大量的时间，所以我们需要确定下来一个装载因子，即一个临界值，当数组中存入的元素大于或者等于这个临界值便重建数组，当然新建的数组长度可以自己定义。我的代码中设定的装载因子是2，reHash函数中新建数组的长度为原来的两倍：

/**
	 * 重构数组的方法
	 */
	void reHash(){
		list.removeAll(list);//每次reHash时，清空list，否则会出现重复
		//遍历数组array，取出原有值加入list
		for(int i=0;i<oldarray.length;i++){
			if(oldarray[i] == null){
				//System.out.println("I am item out is null");
			}else{
				caculate(oldarray[i]);
			}
		}
	}
	
	/**
	 * 按照传入的节点，找出子节点，并存在list中
	 * node:接受的位置节点
	 * @return:不为空，返回item,为空(包括数组为空的清况)，返回null
	 */
	static void caculate(LinkNode node){
		if(node!=null){
			if(node.head!=null){
				list.add((Item)node.data);
				node = node.head;
				caculate(node);
			}else{
				Item it = (Item)node.data;
				//System.out.println("I am return item:"+it.num);
				list.add(it);
			}	
		}else{
			//System.out.println("reHash item is null");
		}
	}

 

        程序中通过取出全部的原有数组元素放入一个list，再通过遍历list重新执行一遍put操作，将所有元素放入新数组中（代码参见put方法）。

      至此，一个基本可运行的hash代码便完成了。在写这段代码之前，我觉得只要思路清晰应该能够很快实现，但在实际写的过程中还是出现了不少问题，比如：由于涉及了多个node.data以及node.head的判断，而且没有及时地处理new操作，出现了一些空指针异常；递归造成的返回值差异；计数器在每次reHash后忘记清零，使得reHash的出现次数过于频繁。其实都是一些很简单的问题，但因为自己的不注意导致运行结果五花八门，这提醒了我在今后写代码一定要理清自己的逻辑，最好在纸上写出处理的流程，因为编代码时难免会遗漏一些事先已经想好的步骤，细节处理不完善必然会导致程序不正确。

      接下来还要说几个问题：

   1）我的hash与系统hash

        我测试了自己的hash代码，系统的hashmap,hashtable,hashset(惭愧，没看完源码)，array以及list在插入相同数量数据（10W）时的执行时间：hashmap:1764    Myhash:2332    hashset: 1697    hashTable:1572   array:1429   list:30385，单位均为毫秒（嘿嘿，不得不说自己写的远不如系统自带的速度快）。从时间可以看出来，list的速度比较慢，应该是在创建指针上花费了大量时间，其他几种系统提供的方法间差距大概是100毫秒，当然，这其中可能包括一些不稳定因素的影响，而且我只是执行了数据的put操作，并未调试插入、删除等操作，相信如果加入了大量的结构性操作，array会比较纠结~

注：此时，所有测试函数的初始大小均为16，装载因子为2

   2）系统hash

        在上文中我说过自己的代码设定的装载因子大小为2，查看jdk中hash部分的时候发现初始大小的设定几乎都是16（hashtable是11，list无定长），而装载因子都为0.75，据jdk中说是一种时间空间上的折中（引用原话：通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本）。对此，我进行了测试，同样是插入10W数据，对于hashMap（16,0.75）花费的时间是1330，hashMap（16,2）花费的时间为1399（这次测试的时间比1）中花费的时间要少）0.75的效率要更高一些（这个值应该是经过各种测算或者数学公式得来的，理应牛气一些~），这之间的时间差在大量数据操作的情况下可能会体现得更为明显。不过其中的原理还真是不太懂，源码正在阅读中，如果有人研究过，求解释~~

   3）第三点，好吧，题外话一下~吐槽~~

        不得不说，这个ITeye我是真的搞不懂，写了一半多突然死掉，被迫重开~原想着最起码有草稿，结果第二次打开读草稿的过程中又over~我想着吧，没事，还有记忆~第三次打开……居然为空！！显示的保存时间为第二次打开的时间……欲哭无泪嘎，显示都没显示就来了个空保存，悲催啊~还有我之前存的草稿，只保存了编辑窗口这么大小的内容，剩下的全部变成了E%~此外，如果文章已经提交再修改，就会出现贴入的代码格式全部变成了文本格式，我就真的…………现在，我开始培养写完一部分就保存一份txt的习惯做预防，谨以此提醒大家：做好备份啊！！！

 

 

                                                                                                        艾~~~