数据结构-----Hash

数据结构之Hash表

 

一.数据结构概念

数据结构是计算机存储，组织数据的方式.

      包括三个组成部分: 数据的逻辑结构 ，数据的存储结构 ，数据运算结构 

  就个人理解，数据结构就是存储数据的容器，简单的数组显然不能适应大量数据存储，查找等功能的实现。因此，合理，高效，也就是空间和时间效率都必须高效，也就成了计算机人员所研究的重点对象。

  接下来，就简单介绍Hash表作为一种数据结构的原理，具体代码实现.

 

二.Hash原理

 

1.数组，链表 ， 数等数据结构有一个共同点：数据的位置和其关键字之间不存在一个确定关系，它们之间的区别仅在于：关键字和给定值比较的顺序不同.

  2.将数据位置和关键字联系----以Hash（key） 函数计算key在表中的位置.

  接下来我将以除留余数法---H(key)=key MOD p(p<m)  (m为表长) 示例讲解Hash表的构成。

 

  3.冲突.

  可以想象，数据数量一旦增多，必然发生不同key值通过Hash函数计算的地址值相同的情况，我们称这种情况成为——冲突。

  为解决冲突，即为产生冲突的关键字寻找下一个哈希地址，可以采取多种方法：

（开放定址法 ， 再Hash法 ，链地址法 等）

  此时，我选择最后一种方法来讲解，其余的方法读者有兴趣课自行找寻资料进行学习.

  4.链地址法——结合数组和链表，即通过Hash函数计算得到相同地址的元素链在第一个元素的后面。此时，存储形式就是一个个节点了，包括数据的Key值和指针域。

 

    5.数据结构的用途就是实现对数据的操作：增----删----查----改 ，效率当然越高越好.

      就我们所知的：

  数组查找方便，通过下表可直接定位，但增，删的效率较慢，因为改变的代价是其他数据也要进行相应的移动。

     链表在插入，删除等操作上显然体现了其优势，因为只用改变数据链域中的指向即可。但链表的查找操作却仍是需要逐一遍历，效率较低。

Hash的结构很容易解释其平衡查找和删除插入操作的效率问题

  6.阀值.

首先，Hash表仍是以数组为基础的，即数组大小初始就要设定且不能改变，当我们无法预知数据总量时，无法准确估计数组大小。若数组初始设定的过大，则浪费内存，若太小，则会出现数组下的链表过长，甚至长于数组的长度，此时，查找效率明显降低。

为解决这个问题，我们需要设定一个阀值，用作控制平衡的量度.

此时，我设定的阀值的是：某一条链上的节点总数和数组大小的比值。这这是个数值，更是个规则。建设Hash表过程中，不能超过这个规则的设定。一旦超过，则需要ReHash。

 

  7.ReHash

用更大的数组重新计算地址，并按照上述规则建设Hash表，直至满足阀值的要求。

 

三.代码实现

 

 

public class MyHash {
	private static int size;// 数组的初始大小
	private static int newSize;//新数组的大小
	Node[] array;//初始数组
	Node[] newArray;//新数组
	static int length = 0;// 当前存储的节点数
	double p = 0.7;//阀值
	static int time = 1;//reHash的次数统计

	public static void main(String[] agr) {//主函数
		MyHash hash = new MyHash();
		hash.test();
	}

	public MyHash() {//构造函数
		size = 16;
		array = new Node[size];// 初始化数组
	}

	private void test() {// 测试方法
		// 添加
		Random random = new Random();//创造随机数
		long start1 = System.currentTimeMillis();//当前时间
		for (int i = 0; i < 100000; i++) {
			int num = random.nextInt(10000);//循环10万次
			add(num);//添加至Hash链表中
		}

		System.out.println();

		long start2= System.currentTimeMillis() ;

		// 检查是否超过阀值，若超过则reHash
 	        overP();
		System.out.println("遍历数组------------------------->");
		long start3 = System.currentTimeMillis();
		for (int j = 0; j < size; j++) {
			System.out.println("第" + j + "个位置");
			Node node = array[j];
			System.out.print(node.getKey() + " ");
			node = node.getNext();
			while (node != null) {
				System.out.print(node.getKey() + " ");
				node = node.getNext();
			}
			System.out.println();
		}
		System.out.println("实现Hash创建所用时间为："
				+ (start2-start1));
		System.out.println("实现Hash搜索所用时间为："
				+ (System.currentTimeMillis() - start3));

	}

	/**
	 * 根据key值计算地址
	 * 
	 * @return：地址
	 */
	public int Hash(int key, int size) {//求余数
		return key % size;
	}
	

	/**
	 * 将节点加入到Hash表中
	 */
	public void add(int key) {

		int add = Hash(key, size);// 先计算地址，判断该位置是否为空
		
		Node node = array[add];
		if (node == null) {// 为空,即可以加入该key值
			array[add] = new Node();
			array[add].setKey(key);
			length++;
		} else {// 不为空，用链地址法处理冲突
			while (node.getNext() != null) {
				node = node.getNext();
			}
			Node next = new Node();
			node.setNext(next);
			next.setKey(key);
			length++;
		}
	}

	/**
	 * 查找
	 * @param key
	 */
	public boolean find(int key) {
		int add = Hash(key, size);// 计算地址
		if (array[add].getKey() == key) {
			return true;
		} else {
			Node next = array[add].getNext();
			while (next != null) {
				while (next.getKey() != key) {
					next = next.getNext();
				}
				return true;
			}
			return false;

		}

	}


	/**
	 * 改
	 */
	public void alter(int key, int cover) {
		int index = Hash(key, size);
		if (array[index].getKey() == key) {
			array[index].setKey(cover);
		} else {
			Node next = array[index].getNext();
			while (next.getKey() != key) {
				next = next.getNext();
			}
			next.setKey(cover);
		}

	}

	/**
	 * 判断是否超过阀值
	 */
	public void overP() {
		for (int i = 0; i < size; i++) {
			int num = 0;
			if (array[i] != null) {
				Node next = array[i].getNext();
				while (next != null) {// 某一串，有下个节点
					num++;
					next = next.getNext();
				}
			}
			if (num >= (0.7 * size)) {// 某一串的个数超过阀值
				System.out.println("超过阀值,重新Hash----------------------->");
				reHash();
			}
			break;
		}
	}

	/**
	 * 再Hash
	 */
	private void reHash() {
		time++;
		newSize = time * size;
		newArray = new Node[newSize];
		for (int i = 0; i < size; i++) {
			Node node = array[i];// 原数组
			while (node != null) {
				int add = Hash(node.getKey(), newSize);// 计算新地址
				Node newNode = newArray[add];
				if (newNode == null) {// 数组上为空
					newArray[add] = new Node();
					newArray[add].setKey(node.getKey());// 设置Key值
				} else {// 数组该位置不为空，找下一个
					while (newNode.getNext() != null) {
						newNode = newNode.getNext();
					}
					Node newNext = new Node();
					newNode.setNext(newNext);
					newNode.setKey(node.getKey());
				}
				node = node.getNext();// /循环至下一个
			}
		}

		size = newSize;
		array = newArray;// 将新数组赋给原先数组

		overP();
	}
}

 

 

运行结果如下：

 

 写道

................

第1917个位置
7677 3837 7677 1917 9597 5757 1917 3837 3837 1917 1917 3837 3837 9597 3837 3837 9597 1917 9597 5757 1917 5757 3837 1917 5757 9597 3837 5757 3837 9597 9597 7677 1917 3837 5757 5757 3837 3837 1917 5757 3837 5757 3837 0
第1918个位置
1918 3838 1918 9598 1918 9598 5758 7678 3838 1918 5758 5758 7678 9598 7678 1918 3838 5758 5758 5758 1918 9598 5758 1918 3838 3838 9598 7678 9598 1918 1918 7678 9598 1918 1918 9598 5758 3838 5758 3838 5758 1918 1918 1918 1918 3838 7678 3838 1918 0
第1919个位置
9599 1919 5759 1919 1919 7679 3839 3839 7679 5759 7679 3839 5759 3839 9599 3839 5759 5759 1919 9599 7679 3839 3839 5759 5759 5759 1919 1919 9599 5759 9599 9599 7679 3839 3839 9599 9599 5759 1919 3839 0

实现Hash创建所用时间为：6827
实现Hash搜索所用时间为：1394