用java实现hashmap -

黑色骑士

浏览: 4018 次
性别:
来自: 绍兴

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

用java实现hashmap

hash

虽然很想很早就想写一个hash表，但一直都未去实现。通过这次机会，算是对hash表有了一个比较直观的了解，主要有以下几点（都是个人见解）：
1.哈希表的目的在于加快查找速度，用一个形象的比喻就是hash是将一个排好序的数据存入数组中，所以在查找时能通过这个索引迅速找到所需要的元素，在hash表中，数组才是主体，链表只是辅助，甚至可以不存在。
2.产生这个索引（在hash中是key）的函数和方法各种各样，而判别这个方法优劣就是让其尽可能少得产生冲突，因为产生冲突后，就会调用处理冲突的方法，无论哪一种方法都不是很合适，以链表为例，显然链表是不适合查找的，所以这个方法对表性能的影响是很大的。这里我才用了和系统差不多的方法，采用了&运算，其实类似于mod，但速度更快。
3.处理冲突的方法也有不少。其中我比较明白的是再散列法和拉链法。在散列法的思想很简单，就是产生冲突后重新计算hash函数地址（索引值）直到找到空的空间放数据。而拉链法则是运用的链表的逻辑连续特性，使不同的数据存在同一个哈希地址下。我采用了第二种，所以对其优缺点比较了解，缺点很明显就是增加查找的复杂度，而相对与再散列法的优点还是很大的，可以避免重复的计算hash地址。
4.如何resize，当装载数与数组长度的比例大于等于比例因子，这是说明数组容量快要饱和，为了避免产生大量的冲突，必须采用resize。
而在写代码的过程中也考虑了很久。比如在数组中存什么，数组长度定义多少之类。这里我说说我的方法。数组中我存的是链表的首节点，因为链表的特性，只要知道头就可以获得整个链表，于此匹配的，我也采用了头插法，当产生冲突，我把它放在链表的头位置。这样代码可以减少不少。至于数组长度我定义为2^n，原因与&运算有关，因为2^n-1的二进制所有位都为1，这样的与运算可以使冲突尽量减少。当产生冲突时，数组长度扩大一倍，感觉也是比较合理的。
以下是部分代码

/**
 * 结点类
 * @author zrq
 *所有数据类都必须继承这个结点类
 */
public class Node {
    private  String account;//账号是唯一标示
    private  String password;
    private  Node Next;

    public int hashcode()
    {
    	int hash=1;
    	hash=Integer.parseInt(account);
    	return hash;
    }

	public String getAccount() {
		return account;
	}

	public void setAccount(String account) {
		this.account = account;
	}

	public String getPassword() {
		return password;
	}

	public void setPassword(String password) {
		this.password = password;
	}

	public Node getNext() {
		return Next;
	}

	public void setNext(Node next) {
		Next = next;
	}

}

由于我是采用了数字作为测试数据，所以节点中的属性是直接定义的（account是唯一的）。重写了hashcode（），产生的方法就是采用了account这个唯一的属性（不通用）。

public class MyHashMap {
	private int initial_size = 16;// 数组初始大小
	private int finally_size = 16;// 用来记录现在数组大小
	private double balance = 0.75;// 装载因子
	private Node[] mapNodes;//组成数组
	private int count = 0;// 用于计数
	int hash;
	int index;

	// 初始化时开辟数组空间
	public MyHashMap() {
		mapNodes = new Node[initial_size];
	}

	public void put(Node node) {
		hash = node.hashCode();// 可修改
		index = hash & (finally_size - 1);// 获得索引位置
		Node fi = mapNodes[index];
		if (fi == null) {
			mapNodes[index] = node;
			count++;
			if (count > finally_size * balance)
				reSize();

		} else {
			// System.out.println("test " + mapNodes[index].head.getAccount());
			node.setNext(fi);
			mapNodes[index] = node;
		}
	}
    /**
     * 通过account查找的方法
     * @param x：account
     * @return：  password
     */
	public String GetValue(String x) {
		Node s = new Node();
		s.setAccount(x);
		boolean f = false;
		int hash = s.hashcode();
		index = hash & (finally_size - 1);
		Node n = mapNodes[index];
		while (n != null) {
			if (n.getAccount().equals(x)) {
				f = true;
				break;
			}
			n = n.getNext();
		}
		if (f)
			return n.getPassword();
		else {
			System.out.println(finally_size);
			return "null";
		}
	}

/**
 * 当达到装载因子时扩容
 */
	public void reSize() {
		count=0;
		Node[] copy = new Node[finally_size * 2];
		for (int i = 0; i < finally_size; i++) {
			Node node = mapNodes[i];
			Node dnext;
			while (node != null) {
				//System.out.println("de"+node.getAccount());
				dnext = node.getNext();
				int index = node.hashcode() & (finally_size * 2 - 1);
				if (copy[index] == null) {
					node.setNext(null);
					copy[index] = node;
					count++;
				} else {
					Node t = copy[index];
					node.setNext(t);
					copy[index] = node;

				}
				node = dnext;
			}

		}
		finally_size = finally_size * 2;
		mapNodes = copy;
	}
}

写的比较急，没怎么优化。
以下是测试类。我用1000000个连续的号码进行存储和查找的测试。系统的时间大概在2600ms，我的大概在3000ms。查找100000个数据，我的约为90ms，系统在120ms左右，当然这和我的node设置的针对性也有关系。
以下是myhashmap的测试主函数（将da放的位置改变就可以测试不同的时间）

	 public static void main(String[] args) {
	 // TODO Auto-generated method stub
	 File fi = new File("F:\\test.txt");
	
	 try {
	 MyHashMap map = new MyHashMap();
	 // HashMap< String, String> map=new HashMap<String, String>();
	 Scanner scan = new Scanner(fi);
	
	 while (scan.hasNext()) {
	 String s = scan.next();
	 Node node = new Node();
	 node.setAccount(s);
	 node.setPassword(s);
	 map.put(node);
	 }

	 int x=100000;
	 Date da = new Date();
	 long n = da.getTime();
	 while(x-->0)
	 {
	 map.GetValue(""+x);
	 }
	 Date de = new Date();
	 long t = de.getTime();
	 System.out.println(t - n + "ms");
	 } catch (FileNotFoundException e) {
	 // TODO Auto-generated catch block
	 e.printStackTrace();
	 }
	
	 }

以下是系统的测试主函数

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		File fi = new File("F:\\test.txt");

		try {
			HashMap<String, String> map = new  HashMap<String, String>();
			Scanner scan = new Scanner(fi);
			int x = 100000;
			while (scan.hasNext()) {
				String s = scan.next();
				map.put(s, s);
			}
			Date da = new Date();
			long n = da.getTime();
			while (x-- > 0) {
				map.get("" + x);
			}
			Date de = new Date();
			long t = de.getTime();
			System.out.println(t - n + "ms");
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

hash的内容还有很多，先写到这。至于哈希算法，很多在安全领域涉及，比如MD5（深奥啊），以后再补充吧。

分享到：