略谈Hash

            这几天自己写了个hash表，以前都是用的系统的，现在轮到自己写了，写的还是比较菜的，希望自己继续扩充吧，下面就简单介绍一下。

 

一、引文

 

   先分析一下最基本的两种数据结构：数组和链表

   优缺点分析：

 

数据结构	数据查找	数据增删
数组	数据储存地址是连续，对于查找数据时可以通过数组下标很快定位	需要重新分配空间，所耗时间较多
链表	数据之间只是通过一个地址在连接，查找数据时需要遍历许多不必要的数据	由于本身数据之间的连接是通过地址的指向，所以只需要改变一下指向

 

     由上可以看出，以上两种数据结构在数据上的查找与增删都有自己的优缺点，而hash结构就是综合了两者的优点。

       

 

二、数据结构——Hash表

 

       1).图示结构

 

 

 

 

2). 从上面的结构图可以看出，hash表整体是以数组为载体，数组内部元素以链表形式存在的，hash表所需要的就是把所要储存的元素平均分配到各个挂表上去，此时所需要的就是hash函数了，我所实现的哈希表是对字符串形式数据的操作，常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，另外还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

算是站在巨人的肩膀上，我基本写出了一个像样的hash表。

以上常用的几个hash函数代码实现及比较，我已经上传到下面的附件，大家可以看一下。

 

三、代码示例

1）一些所需要的数据变量：

 

	private int hash_length = 0;// 数组长度
	private int threatHold = 0;// 重新加载的条件
	private DataNode dataNodes[];// 数据表
	private double load_factor = 0.8f;// 加载因子
	private int size = 0;// 数据的数目
	private static int default_hash_size = 10;// 数组初始大小
	private int MAXIMUM_NODE = 1 << 30;// 数据最大值

 

 

 

2）数据的插入及删除

 

	// 以数据单项插入
	public synchronized void insert(String data) {
		int hash = hash(data);
		DataNode node = new DataNode(data);
		if (dataNodes[hash] == null)
			dataNodes[hash] = node;
		else {
			DataNode fatherNode = dataNodes[hash];
			DataNode childNode = dataNodes[hash].getNextNode();
			while (childNode != null) {
				fatherNode = childNode;
				childNode = childNode.getNextNode();
			}
			childNode = node;
			fatherNode.setNextNode(childNode);
		}
		if (size++ > threatHold) {
			rehash();
		}
		if (size > MAXIMUM_NODE) {
			throw new RuntimeException("Sorry，散列表已满!!!");
		}
	}

	// 以数据形式删除数据项
	public synchronized void delete(String data) {
		int hash = hash(data);
		DataNode node = new DataNode(data);
		if (dataNodes[hash] == null) {
			throw new RuntimeException("该数据项不存在");
		} else if (dataNodes[hash].equals(node)) {
			dataNodes[hash] = dataNodes[hash].getNextNode();
		} else {
			DataNode rootNode = dataNodes[hash].getNextNode();
			while (rootNode != node) {
				if (rootNode == null)
					throw new RuntimeException("该数据项不存在");
				rootNode = rootNode.getNextNode();
			}
		}
		size--;
	}

 

 

 

 

3）我借用了一下前人的RS hash函数，系统是通过每个对象的hashcode进行操作

 

  

// hash函数用来计算数据的key值
	public int hash(String data) {
		//RS hash
		char[] datas = data.trim().toCharArray();
			 int temp1 = 378551;
			 int temp2 = 63689;
			 int hash = 0;
			 for(char ch:datas){
				 hash = hash * temp2 + ch;
				 temp2 *= temp1;
			 }
			return (hash & 0x7FFFFFFF)%hash_length;
	}

 

 

4）比较重要的一点，当hash表数据量达到了开始设定的边界，便需要再次加载，称之为rehash

 

 

// 重新装载
	public synchronized void rehash() {
		System.out.println("又要重新加载了.......");
		hash_length = hash_length << 1;// 扩充为原来的两倍
		if (hash_length > MAXIMUM_NODE) {
			throw new RuntimeException("对不起，数组长度已达到最大！！");
		}
		DataNode newNodes[] = new DataNode[hash_length];

		for (DataNode node : dataNodes) {
			while (node != null) {
				String data = node.getData();
				int hash = hash(data);
				DataNode nodeNew = new DataNode(data);
				if (newNodes[hash] == null)
					newNodes[hash] = nodeNew;
				else {
					DataNode fatherNode = newNodes[hash];
					DataNode childNode = newNodes[hash].getNextNode();
					while (childNode != null) {
						fatherNode = childNode;
						childNode = fatherNode.getNextNode();
					}
					childNode = nodeNew;
					fatherNode.setNextNode(childNode);
				}
				node = node.getNextNode();
			}
		}
		// 复制原来的数据
		dataNodes = newNodes;
		setThreatHold();
	}

 

  

 

四.后文

 

     这实现的基本上只有一个架构，对于很多的细节方面考虑还比较少，接下来主要考虑的还是数据的均分问题，估计更多的还是需要用到位运算，还需要继续下去....