MyHash实现

经过一段时间的研究学习，对于Hash有了更深一步的了解和认识，下面谈谈一些基本概念及自己设计的一个MyHash的实现。

1、基本概念：

Hash，一般翻译做“散列”，也有直接音译为“哈希”。

哈希就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值。

Hash主要用于信息安全领域中加密算法，把一些不同长度的信息转化成杂乱的128位编码,这些编码值叫哈希值。也可以说哈希就是找到一种数据内容和数据存放地址之间的映射关系。

哈希表就是一种根据关键码值直接进行访问的数据结构。

 

2、哈希表的优缺点：

那么为什么使用哈希表呢？它一定有特定的优点我们才会使用它。看看这个图表，相信大家就了解了吧~~

数组具有查找迅速但是对其进行插入删除操作较困难的特点，而链表容易插入删除但查找困难。。。是否有一种数据结构能够将两者的优点集合呢？哈希表就是一个两全其美的选择~~他是直接根据key值找到相应的存储位置，对其进行访问，插入删除操作类似于链表的相关操作。哈希表是基于快速存取的角度设计的，它的优点非常明显，存取速度能达到常量级O(1)

当然它也有一定的缺点：

1、使元素丧失了有序性

2、元素不能够紧密的排列，需要足够大的空间

3、两个或多个不同项被散列到同一位置是不可避免的 ——冲突

  【冲突：对不同的关键字可能得到同一散列地址 即key1≠key2，而f(key1)=f(key2) 】

3、常用的构造构造哈希函数的方法：

v1.直接寻址法

v2.数字分析法

v3.平方取中法

v4.叠加法

v5.随机数法

v6.除留余数法

比较常用的是除留余数法，下面详细介绍一下此方法：

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址 。

即 H(key) = key MOD p     (p<=m)  

例如： 给定一组关键字为:          12, 39, 18, 24, 33, 21 

         H(key) = key MOD 9     3    3    0    6    6   3  

这里对P要有什么限制条件呢？                                         

12, 39, 18, 24, 33, 21

若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3 

若取 P=18,则他们对应的哈希函数值将为12,3,0,6,15,3

若取p=24，则他们将对应的哈希函数值将为： 12,15,18,0,9,21 

一般结论：选取的P较小，“冲突”的可能性较大

4、解决冲突的方法：

1、拉链法：即构造成数组链表的形式

2、在哈希法：设计两种甚至多种哈希函数

3、开放地址法：线性/二次/随机探测再散列

4、建域法：建立一个公共溢出区存储发生冲突的记录

5、下面是一个我实现的MyHash：解决冲突是采用的第一种方法

package MyHash2;

import java.util.Collection;
import java.util.Iterator;

/**
 * MyHash类
 * @author Administrator
 *
 * @param <T>
 */
public class MyHash<T>implements Collection<T>{
	private Entry[] table;
	private int hashTableSize;
	private int Capacity=16;//初始大小
	private float LoadFactor= 0.75f;//默认装载因子
	private int tableThreshold;//最大承载大小
	private int modCount=0;
	
	/**
	 * 结点类
	 * @author Administrator
	 *
	 * @param <T>
	 */
	private static class Entry<T>{
		T value;//数值
		int hashvalue;//hash值
		Entry<T> next;//指针
		public Entry(T value,int hashvalue,Entry<T> next){
			this.value=value;
			this.hashvalue=hashvalue;
			this.next=next;
		}		
	}
	
	/**
	 * 构造函数
	 */
	public MyHash(){
		table=new Entry[Capacity];
		hashTableSize=0;
		tableThreshold =(int)(table.length * LoadFactor);
	}

	/**
	 * 添加数据
	 */
	public boolean add(T item){
		int hashvalue=item.hashCode();//计算hashvalue
		int index=hashvalue%table.length;//计算下标
		//System.out.println("item.hashCode()="+hashvalue+"   table.length="+table.length+"    index="+index);		
		Entry<T> entry;
		entry= table[index];
		//不为空，则查找该数据是否已存在;为空则加入
		while(entry!=null){
			if(entry.value.equals(item)){
				System.out.println("该数据已经存在");
				return false;
			}
			entry=entry.next;
		}
		modCount++;
		entry =new Entry<T>(item,hashvalue,(Entry<T>) table[index]);
		table[index]=entry;
		hashTableSize++;
		//检查hash表是否已超过最大承载量
		if(hashTableSize>tableThreshold){
			int newTableSize=2 * table.length + 1;
			rehashing(newTableSize);
		}
//		System.out.println("添加数据"+item+"成功");
		return true;
	}
	
	/**
	 * 移除数据
	 */
	public boolean remove(Object item){
		int index =item.hashCode()%table.length;
		Entry<T> current;
		Entry<T> previous=null;
		current=table[index];
		//对应下标的数组位置有数据
		while(current!=null){
			//找到要删除的数据
			if(current.value.equals(item)){
				modCount++;
				//该数据不是链表的第一个数据，则将前一个数据的指针指向下一个数据
				if(previous!=null){
					previous.next=current.next;
				}else{//该数据是链表的第一个数据，则将下一个数据挪到当前下标处
					table[index]=current.next;
				}
				hashTableSize--;
				System.out.println("删除了数据："+current.value+"  index为"+index);
				return true;
			}else{//向下继续找要删除的数据
				previous=current;
				current=current.next;
			}
		}
		return false;
	}
	
	/**
	 * 查找某数据
	 * @param item
	 * @return
	 */
	public boolean find(Object item){
		int index=item.hashCode()%table.length;//计算出下标
		Entry<T> entry=table[index];
		//对数组下标下的链表进行查找
		while(entry!=null){			
			//与对应下标内的数据进行equals比较
			if(entry.value.equals(item)){
				System.out.println("查找到数据："+entry.value+"  index为"+index);
				return true;
			}			
			entry=entry.next;
		}
		System.out.println("查找失败，数据不存在");
		return false;
	}
	
	/**
	 * 清除所有数据
	 */
	public void clear(){
		int len=table.length;
		//遍历———清空数据
		for(int i=0;i < len; i++){
			table[i] = null;  
		    modCount++;  
		    hashTableSize = 0;  
        }
	}

	/**
	 * rehash方法
	 * @param rehashSize
	 */
	public void rehashing(int newTableSize){
		System.out.println("Hash重构");
		Entry[] newTable =new Entry[newTableSize];//新HashTable
		Entry[] oldTable = table;//原HashTable
		int index;
		Entry entry;
		//循环，将原HashTable内的数据重新计算地址，存入新HashTable
		for(int i=0;i<table.length;i++){
			entry=table[i];
			if(entry!=null){
				//先将该位置的原数据清除，设为NUll
				table[i]=null;
				//向新HashTabele中添加该数据
				while(entry!=null){
					Entry newEntry=entry.next;
					index=entry.hashvalue%newTableSize;
					entry.next = newTable[index];  
					newTable[index] = entry;  
                    entry = newEntry;  
				}
			}
		}
		table=newTable;
		//重新设置装载量大小
		tableThreshold = (int) (table.length * LoadFactor);  
		//将原HashTable清空
		oldTable = null;  
	}
	
//	/**
//	 * 计算HashCode的方法
//	 * @return
//	 */
//	public int hashcode(Object item){
//		int index = item.hashCode()%table.length;
//		return index;
//	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return hashTableSize;  
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return hashTableSize == 0;  
	}
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public Iterator<T> iterator() {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean addAll(Collection<? extends T> c) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}
	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}
	
	
}

 

Test测试类：

加入150万个数据（打印Size、添加数据所需的时间）—>查找一个特定数据（打印该数据、数据所在数组位置的下标、查找时间）—>删除一个数据（打印Size）—>再次查找该数据（查找失败）—>清空全部数据

Hash重构十七次

添加数据时间为：1906

此时Size为1500000

查找到数据：100000  index为290089

查找数据时间为：0

删除了数据：100000  index为290089

此时Size为1499999

查找失败，数据不存在

查找到数据：100000  index为290089

清除全部数据了，此时Size为0

发现多次执行同一程序，添加数据的时间与之前相比会少。。。