Hash表的建立及增删改查相关操作

1、什么是hash？

 

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

也许这么听大家肯定会对hash不知所云，晕晕乎乎。说实话，我也是这样。所以根据我自己的理解呢，hash就是把一段数据通过某种方法映射成另外一个值（相当于x映射为f(x)），也就是一个单向加密的过程。这个方法可以自己定义，也可以去网上找现成的，比如MD5的加密算法就用到了hash。

 

 

 

2、为什么要用hash？

 

当然是用来加密数据了~~~不错，不过这却不是我要说的。hash还可以用来干许多事比如说快速建立索引及查找。举个最现实的例子：QQ同时在线人数平均在几千万~近两亿（极端情况不考虑），每个用户都是一个User的类保存在腾讯的服务器上，存储这些数据也许可以用数组，也可以用链表，不过我们很快就会发现这种方法的缺陷。假如说这时，有一个用户上线了，腾讯的服务器必须先检测是否该QQ号是否已经登录了。若是，则向原来登录的客户机发送离线消息，然后再让新的用户上线；若不是，则直接让该用户上线。不管是哪种情况，都需要进行查找遍历。如果用数组或链表，那么都得从头开始排查，最差的情况是里头有多少元素就要排查多少次，这已经大大降低了查询效率，况且一个时刻上线下线的人数少说也得数以百计，并且之后还伴随着添加和删除过程（相对来说，数组是查询快，增删操作慢，而链表正好相反），那么这么看来，单纯的用数组或是链表是行不通的了。

那么我们应该怎么解决呢？用hash，当然！不过具体要怎么实行？首先我们建立一个模型：一个长度为n的数组，每一个数组元素存的是一段链表的头节点，链表长度为m（每个链表的m值相互无关），而链表的每个节点存储的则是一个User类的对象，这样无形中就形成了一个二维的数据存储结构，我们称之为数组加链表模型。假如有0~99这100个数需要存到这种模型中，我们可以让数组的第一个元素专门存储第一位为0的数（即一位数），链表长度为10，存储的数据分别为0、1、2、3、4、5、6、7、8、9；第二个元素存储第一位为1的数……以此类推，直到全部存进。现在我们要查找65，假设数组名为a，我们只需要找到a[6]，然后再循环查找链表的下一个节点，直到找到65，只需要5次。而用链表查找，则需要查找65次。当然如果用数组定义的话直接a[65]就能得到，但是如果需要在65与66之间再插入一个值就比较麻烦了，而上述数组加链表模型依然能轻松的解决这一问题。

现在我们回到QQ用户的问题，若是对于不同的用户能够尽可能的把他们分散到数组加链表模型的各处的话，查找和增删等操作就迎刃而解了，采取一种什么样的机制让他们分散呢？这就是hash方法了。我们知道每个用户的QQ号是唯一的，所以我们可以用该数值来进行hash运算。假如QQ同时在线人数为1亿，我们采取取模的hash算法，我们建立一个数组名为a，长度为100000的数组加链表模型，然后用QQ号的值对100000取模，比如说QQ号为123456789，取模后为56789，那么我们就把他存入a[56789]的链表中。当然不止一个QQ号取模后结果为56789，对于这些QQ号，新来一个就把他加到链表的最后一个节点的后面并设置链表相邻元素间的指向关系。全部遍历一遍建立好了之后再找某个QQ号就可以先取模，然后到指定的数组链表上去找了，在这里最多只需要10000次即可找到（针对九位数的QQ）或确定不存在。

 

 

 

3、需要注意的方面：

 

首先是hash方法的确定，在这方面每个人有自己的想法，根据hash算法和初始容量然后初步确定数组长度n的大小，要使得数据尽量散列开来（所以hash函数一般翻译为“散列”嘛）。

其次就是随着用户的增多会导致链表的越来越长，当数组长度不变之后每个元素的链表长度却在一个劲地增加，长此以往，这个模型就会变得越来越像纯链表，也就慢慢偏向无效率了。所以在适时的时候，即链表长度和数组长度达到某一关系后我们就应该扩充数组长度了，当数组长度一变，取模的值也就变了，就是说原来的hash结果已经改变了，无法再适用到新的长度的数组上，所以我们需要对原来的每个元素重新hash一次，称之为rehash过程。可以想象，rehash的代价是巨大的，但是这也是必须的。

 

 

 

4、拓展方面：

 

其实既然有了数组加链表模型，那么我们可以继续设置数组加数组加链表模型，或者在前面套n个数组，但是前提条件是该用户类必须有n个字段值是唯一的，若QQ设置用户昵称也不能一样，那么我们在第二个数组里可以对用户昵称再进行hash一下，建立一个索引，然后加入链表中。

 

 

 

以下是简单实现的一个数组加链表模型：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class HashTest {

	int prime;

	public HashTest() {
		Scanner sc = new Scanner(System.in);
		int count = 0;
		System.out.println("请输入需要添加的个数（值由系统随机生成）：");
		count = sc.nextInt();
		long start = System.currentTimeMillis();
		MyThread th = new MyThread();
		th.start();
		int size = 2 * (int) Math.sqrt(count);
		prime = Prime(size);
		User DataArray[] = new User[size];
		h: for (int i = 0; i < count; i++) {
			System.out.println(i);
			int value = random();
			int addr = hash(value);
			// 排查重复
			User checkuser = new User();
			try {
				checkuser = DataArray[addr];
			} catch (ArrayIndexOutOfBoundsException aioobe) {
				aioobe.printStackTrace();
				System.out.println(DataArray.length);
			}
			while (checkuser != null) {
				if (checkuser.getid() == value) {
					continue h;
				}
				checkuser = checkuser.getnext();
			}
			User u = new User(value);
			DataArray = addto(addr, u, DataArray);
		}
		th.setflag(false);
		System.out.println("共用了"
				+ ((System.currentTimeMillis() - start) / 1000) + "秒");
		System.out.println("添加成功。\t\n是否继续操作：\t\n1：继续\t0：退出");
		int choose = new Scanner(System.in).nextInt();
		while (choose != 0 && choose != 1) {
			System.out.println("输入错误，请重新输入");
			sc = new Scanner(System.in);
			choose = sc.nextInt();
		}
		if (choose == 0) {
			System.exit(0);
		} else {
			System.out
					.println("请输入需要进行的操作：\t\n1：增加\t2：删除\t\n3：修改\t4：查询\t\n0：退出");
			int result = new Scanner(System.in).nextInt();
			while (result != 1 && result != 2 && result != 3 && result != 4
					&& result != 0) {
				System.out.println("输入错误，请重新输入");
				sc = new Scanner(System.in);
				result = sc.nextInt();
			}
			switch (result) {
			case 1:
				add(DataArray);
				break;
			case 2:
				del(DataArray);
				try {
					Thread.sleep(2000);
					query(DataArray);
				} catch (Exception e) {
				}
				break;
			case 3:
				fix(DataArray);
				try {
					Thread.sleep(2000);
					query(DataArray);
				} catch (Exception e) {
				}
				break;
			case 4:
				query(DataArray);
				break;
			case 0:
				break;
			default:
			}
			System.exit(0);
		}
	}

	/**
	 * 获取质数
	 * 
	 * @param len
	 *            数组长度
	 * @return 离len数值最近的最大的质数
	 */
	int Prime(int len) {
		int sqr = (int) Math.sqrt(len);
		while (len > 2) {
			for (int i = 2; i < sqr; i++) {
				if (len % i == 0) {
					break;
				}
				if (i == sqr - 1) {
					return len;
				}
			}
			len--;
		}
		return len;
	}

	/**
	 * 生成随机数
	 * 
	 * @return 生成的随机数
	 */
	int random() {
		return new Random().nextInt(900000000) + 100000000;
	}

	/**
	 * 哈希算法
	 * 
	 * @param value
	 *            传入的值
	 * @param prime
	 *            计算数组长度所得的质数
	 * @return 哈希算法后的结果
	 */
	int hash(int value) {
		int sum = 0;
		while (value / 10 != 0) {
			sum += Math.pow(8, value % 10);
			value /= 10;
		}
		return sum % prime;
	}

	/**
	 * 添加元素
	 * 
	 * @param addr
	 *            数组的第几号元素
	 * @param u
	 *            加入的User对象
	 * @param Array
	 *            加至的数组
	 */
	User[] addto(int addr, User u, User[] Array) {
		if (addr > Array.length) {
			throw new RuntimeException("地址超出数组长度，添加失败");
		}
		if (Array[addr] == null) {
			Array[addr] = u;
		} else {
			User user = Array[addr];
			// 链表节点数
			int amount = 0;
			while (user.getnext() != null) {
				amount++;
				user = user.getnext();
			}
			user.setnext(u);
			u.setlast(user);
			if (amount > Array.length * 0.8) {
				// 链表节点过多，扩展数组
				System.out.println("链表节点过多，扩展数组");
				Array = rehash(Array);
			}
		}
		return Array;
	}

	/**
	 * 当数组需要扩张时的重新散列方法
	 * 
	 * @param Array
	 */
	User[] rehash(User[] Array) {
		User[] reArray = new User[(int) (Array.length * 1.5 + 100)];
		List<User> list = new ArrayList<User>();
		prime = Prime(reArray.length);
		for (int i = 0; i < Array.length; i++) {
			for (User u = Array[i]; u != null; u = u.getnext()) {
				list.add(u);
				try {
					// 把原本的上下链关系全部断开
					u.getlast().setnext(null);
					u.setlast(null);
				} catch (NullPointerException npe) {
					System.out.println("空指针");
				}
			}
		}
		for (int i = 0; i < list.size(); i++) {
			// 逐个添加
			User u = list.get(i);
			int addr = hash(u.getid());
			addto(addr, u, reArray);
		}
		Array = reArray;
		return Array;
	}

	void add(User[] DataArray) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入需要添加的个数（值由系统随机生成）：");
		int count = sc.nextInt();
		long start = System.currentTimeMillis();
		MyThread th = new MyThread();
		th.start();
		h: for (int i = 0; i < count; i++) {
			int value = random();
			int addr = hash(value);
			User checkuser = DataArray[addr];
			while (checkuser != null) {
				if (checkuser.getid() == value) {
					continue h;
				}
				checkuser = checkuser.getnext();
			}
			User u = new User(value);
			DataArray = addto(addr, u, DataArray);
		}
		th.setflag(false);
		System.out.println("花费了"
				+ ((System.currentTimeMillis() - start) / 1000)
				+ "秒后增加成功，即将显示结果……");
		try {
			Thread.sleep(2000);
		} catch (Exception e) {
		}
		query(DataArray);
	}

	void del(User[] DataArray) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入需要删除的用户的id值：");
		int id = sc.nextInt();
		int addr = hash(id);
		User u = DataArray[addr];
		if (u != null) {
			if (u.getid() == id) {
				DataArray[addr] = u.getnext();
				System.out.println("元素已成功删除，即将显示结果……");
				return;
			} else {
				while (u.getnext() != null) {
					u = u.getnext();
					if (u.getid() == id) {
						if (u.getnext() == null) {
							u.getlast().setnext(null);
							System.out.println("元素已成功删除，即将显示结果……");
							return;
						} else {
							u.getlast().setnext(u.getnext());
							u.getnext().setlast(u.getlast());
							System.out.println("元素已成功删除，即将显示结果……");
							return;
						}
					}
				}
			}
		}
		System.out.println("未找到相应元素，即将显示结果……");
	}

	void fix(User[] DataArray) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入需要修改的用户的id值");
		int id = sc.nextInt();
		int addr = hash(id);
		User u = DataArray[addr];
		while (u != null) {
			if (u.getid() == id) {
				System.out.println("请设置其名字：");
				Scanner scan = new Scanner(System.in);
				String name = scan.next();
				u.setname(name);
				System.out.println("已成功更新数据，即将显示结果……");
				return;
			}
			u = u.getnext();
		}
		System.out.println("未找到相应元素，即将显示结果……");
	}

	void query(User[] DataArray) {
		int all = 0;
		int mount = DataArray.length;
		System.out.println("共有" + mount + "个元素");
		for (int i = 0; i < mount; i++) {
			int num = 1;
			User u = DataArray[i];
			if (u != null) {
				while (u.getnext() != null) {
					num++;
					u = u.getnext();
				}
			} else {
				num = 0;
			}
			all += num;
			System.out.println("第" + i + "个元素的链表中共有" + num + "个对象");
		}
		System.out.println("共有" + all + "个对象");
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new HashTest();
	}

	class User {
		private int id;
		private User nextuser, lastuser;
		private String name;

		public User() {
		}

		public User(int id) {
			this.id = id;
		}

		public int getid() {
			return id;
		}

		public void setnext(User u) {
			this.nextuser = u;
		}

		public User getnext() {
			return nextuser;
		}

		public void setlast(User u) {
			this.lastuser = u;
		}

		public User getlast() {
			return lastuser;
		}

		public void setname(String name) {
			this.name = name;
		}

		public String getname() {
			return name;
		}
	}

	class MyThread extends Thread {
		public boolean flag = true;

		public void run() {
			while (flag) {
				System.out.println("正在添加中，请等待……");
				try {
					Thread.sleep(5000);
				} catch (Exception e) {
				}
			}
		}

		public void setflag(boolean flag) {
			this.flag = flag;
		}
	}

}