自定义哈希表的性能评测

作为一个程序员或一个软件工程师，hash(散列)必然是熟解的。

对于百万级，甚至更多的数据的数据，我们如何实现存储并不太难，可我们要实现快速的增添查找删，显然普通的数组和链表是满足不了的。数组可以满足快速的查找，链表可以实现随意的删除，我们由此不难得到一种数据结构：数组挂链表的结构，称挂链式。

以一般的数据结构实现哈希过程，在实际中会遇到比较大的问题，我们在此选择使用挂链式，作为解决hash冲突的一种解决策略。当有不同的key在hash()后得到想的hashcode的时候，我们选择在哈希表结点上悬挂链表。而当我们的数据虽时间变化的时候，显然，冲突越来越严重，我们需要解决这个问题。在冲突达到一定程度时，我们队哈希表进行扩张，对原哈希表的数据进行rehash（）。

不难想象到，rehash()是一个浪费时间与空间的过程，可这是没有办法的事，因为两全其美的事不存在，我们只能根据实际情况，取舍。

自定义哈希表的结构

①hash（）：哈希表实现快速增删查的根本，通过hash（）对每一个key 得到唯一的一个索引，而这个索引就如身份证号，查找删除数据时只需知道与此数据相匹配的索引；

②解决冲突的方法：冲突指的是当不同的数据的key通过hash（）得到相同的索引位置而提供的解决方法，此处此方法为挂链式；

③rehash（）：当哈希表中的数据达到一定的值时，成为阀值，因为此刻由于数据的增多，索引的速度必然受到影响，而解决的方法就是对数组拓展，重新的hash（）.

class HuHash{

  private Node<Item> [] list=new Node<Item> [len];

  public boolean put(K k,V v){

     if(冲突严重){

         rehash()

     }

     int index=hash(k)%len;

     Node<Item> node=new Node<Item>(k,v);  

     if(list[index]==null){

        

     }

     

  }

  public boolean get(K k){

  

  }

 

  public boolean hash(K k){

  

  }

  

  public boolean rehash(){

  

  }

}

class Node<Item>{

  private Node parent;

  private Node next;

}

class Item{

   

}

性能对比（见附件）：

代码实现如下：

package hash实现;

/**
 * 哈希的实现类
 * 
 * @author lenovo
 * 
 */
public class MyHash<K, V> {

	private int len;
	private Node[] list;
	private int count; // 计数器

	public MyHash(int len) {
		this.len = len;
		list = new Node[len];
		count = 0;
	}

	/**
	 * 添加元素的方法
	 * 
	 * @param key
	 *            ：键
	 * @param value
	 *            ：
	 * @return
	 */
	public void put(K key, V value) {
		if (count >= 1.25 * len) { // 冲突的严重性
			rehash();
		}
		int index = hash(key) % len;
		Item<K, V> it = new Item(key, value);
		Node node = new Node(it);
		if (list[index] != null) { // 判断是否为空结点
			// 添加到链表头
			Node temp = list[index];
			node.setNext(temp);
		}
		list[index] = node;
		count++;
	}

	public V get(K k) {
		int index = hash(k) % len;
		Node temp = list[index];
		while (temp != null) { // 判断此数组索引是否为空
			if (temp.getItem().getK().equals(k))
				return (V) temp.getItem().getV();
			temp = temp.getNext();
		}
		return null;
	}

	/**
	 * 根据键移除hash表中的数据
	 * 
	 * @param k
	 * @return 若存在则返回true
	 */
	public boolean remove(K k) {
		if (count == 0) {
			throw new RuntimeException("哈希表中无元素，删除操作拒绝！");
		}
		int index = hash(k) % len;
		Node temp = list[index];
		while (temp != null) { // 判断此数组索引是否为空
			if (temp.getItem().getK().equals(k)) {
				list[index] = temp.getNext();
				count--;
				return true;
			}
			temp = temp.getNext();
		}
		return false;
	}

	/**
	 * 得到哈希表中元素的个数
	 * 
	 * @return
	 */
	public int size() {
		return count;
	}

	/**
	 * SDBM散列方法
	 * 
	 * @param k
	 *            ：键
	 * @return 哈希值
	 */
	private int hash(K k) {
		String str = (String) k;
		int hash = 0;
		char[] chars = str.trim().toCharArray();
		int num = 0;
		while (num < chars.length) {
			hash = (int) chars[num] + (hash << 6) + (hash << 16) - hash; // 进行移位运算
			num++;
		}
		return (hash & 0x7FFFFFFF); // 按位与（hash和0x7ffffff转换为二进制）
	}

	/**
	 * 再散列方法
	 */
	private void rehash() {
		len = len * 15; // 表长扩大的倍数
		Node[] temp = new Node[len]; // 存放rehash后数据的数组
		Node node;
		int index;
		for (int i = 0; i < list.length; i++) {
			node = list[i];
			while (node != null) {
				index = hash((K) node.getItem().getK()) % len;
				temp[index] = node;
				node = node.getNext();
			}
		}
		list = temp; // 复制数据
	}

}

 

package hash实现;
/**
 * 链表结点类,存放键值对
 * @author lenovo
 *
 */
public class Node {
	
	private Node next;
	private Item item;
	
	public Node(Item item){
		this.item=item;
		next=null;
	} 

	public Item getItem() {
		return item;
	}

	public void setItem(Item item) {
		this.item = item;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
	
}

 

package hash实现;
/**
 * 键值对
 * @author lenovo
 *
 */
public class Item<K,V> {

	private K k;
	private V v;
	
	public Item(K k,V v){
		this.k=k;
		this.v=v;
	}
	
	public K getK() {
		return k;
	}
	public void setK(K k) {
		this.k = k;
	}
	public V getV() {
		return v;
	}
	public void setV(V v) {
		this.v = v;
	}
	
	
}

 

其他参考的hash函数：

/**
	 * 一位接一位的hash函数
	 * 
	 * @param k
	 * @return
	 */
	private int oneByOneHash(K k) {
		String str = (String) k;
		int hash = 0;
		for (int i = 0; i < str.length(); ++i) {
			hash += str.charAt(i);
			hash += (hash << 10);
			hash ^= (hash >> 6);
		}
		hash += (hash << 3);
		hash ^= (hash >> 11);
		hash += (hash << 15);
		return hash;
	}

 

/**
	 * FNVHash 函数
	 * 
	 * @param k
	 * @return
	 */
	private int FNVHash(K k) {
		String str = (String) k;
		final int p = 16777619;
		int hash = (int) 2166136261L;
		for (int i = 0; i < str.length(); i++)
			hash = (hash ^ str.charAt(i)) * p;
		hash += hash << 13;
		hash ^= hash >> 7;
		hash += hash << 3;
		hash ^= hash >> 17;
		hash += hash << 5;
		return hash;
	}