哈希算法

有学号和姓名为下的五个学生：5 tom、8 jane、12 bit 、17 lily 、40 sunny

我们可以利用哈希算法根据id将学生姓名存入，再根据id检索。

学生ID相当于KEY ，名字相当于VALUE

代码如下：

package com.algorithm.hash;

public class hash {
	//哈希函数
	public static int Hash(int key){
		return key%17+3;
	}

	public static void main(String[] args) {
		String[] stu = new String[20];
		//根据哈希函数，将学生姓名存入数组。
		stu[Hash(5)] = "tom";
		stu[Hash(8)] = "jane";
		stu[Hash(12)] = "bit";
		stu[Hash(17)] = "lily";
		stu[Hash(20)] = "sunny";
		System.out.println("学号为5的学生姓名："+stu[Hash(5)]);
	}
}

 从上可以知道：哈希算法检索的时候效率非常高，直接就可以找到需要的值。

 

看下面的题目：

有两个集合，

{ 2, 4, 5, 8, 65, 81 };
{ 8, 5, 45, 57, 89, 6, 4, 65, 1, 5, 2 };

如何找到相同的元素

 

第一种方法。将一个集合的每一个元素拿来到到另一个的集合中查找。

 

第二种方法。将较大的集合排序后，把较小的集合中的每个元素拿来到较大的集合中查找。可以用二分查找

 

第三种方法。采用哈希算法。将一个集合中的值经过哈希运算后，放入数组。第二个集合的元素利用哈希算法查找是否在数组中存在。代码如下：

 

package com.algorithm.hash;

public class hash {
	//哈希函数
	public static int Hash(int key){
		return key%17+3;
	}
	
	public static void main(String[] args) {
		int[] M = new int[] { 2, 4, 5, 8, 65, 81 };
		int[] N = new int[] { 8, 5, 45, 57, 89, 6, 4, 65, 1, 5, 2 }; 
		int[] hashtable= new int [20];
		for (int i = 0; i < M.length; i++) {
			int key = Hash(M[i]);
			hashtable[key] = M[i];
		}
		for (int i = 0; i < N.length; i++) {
			int key = Hash(N[i]);
			if(hashtable[key] == N[i]){
				System.out.println(N[i]);
			}
		}
	}
}

 有上面的代码就可以看出哈希算法在检索方面的优势。