哈希表的一些概念 代码（自己写）

首先，我们要明确一点是hash表是基于数组，这个数组是我们输入的数据项的数组

比如：我创建了一个数据项

package endual;

public class DataItem {

	private int iData ; //key值相当于这个数据项的ID ,这个相当于People信息的身份证号码
	private Object object ; //这个数据相当于人们要存放数据用的数据比如People的信息等等
	
	
	public Object getObject() {
		return object;
	}

	public void setObject(Object object) {
		this.object = object;
	}

	public DataItem(int iData) {
		super();
		this.iData = iData;
	}

	public int getiData() {
		return iData;
	}

	public void setiData(int iData) {
		this.iData = iData;
	}
	
	
}

 

这似乎很麻烦对吧，因为在创建的数组项中我们要输入关于这个数据项的ID，还要输入这个数据项的真的我们要存放的数据Object 这似乎不怎么好。

 

那么当然了，你可以将这个key值写入到object中，但是在哈希表的实现中，我们来取得这个key值的时候，要先取得object然后再取得key值了。你是否能理解？？？（你完全可以把我说的这些是废话，真的因为教科书上都没这么写）

 

然后是哈希表的部分代码

 

package endual;

public class HashTable {

	private DataItem[] hashArray ; //hash表是基于数组的
	private int arraySize ; //创建hash表的时候，要先确定这个量要多少大
	private DataItem nonItem ; //hash表有一个是无法填满的
	
	public HashTable(int arraySize) {
		super();
        this.arraySize = arraySize ; //输入的哈希表的大小
		this.hashArray = new  DataItem[this.arraySize] ; //创建输入创建哈希表的大小
		nonItem = new DataItem(-1) ; //用于删掉的数据项,将这个数据项放入到空的地方，如果遇到这个关键词是-1的那么说明这个数值的地方是空的
		
	}


。。。。。。
。。。。。。
。。。。。。
。。。。。。

 

 

   很抱歉你没有看到全部的代码，但我费尽心思的想让你先看下哈希表的理论，然后再去看代码，入门你喜欢直接看代码，那么你可以先去看，但是我保证你看的糊里糊涂呵呵。

 

 

哈希表的一些理论

 

 

哈希表是一种数据结构 基于数组的 

哈希表的 增加 删除 查找都是 1

确实 无法遍历 数组是定死的

哈希表是一种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。

不论哈希表中有多少的数据，插入和删除只需要接近常量的时间，1.

哈希表的使用就是一秒钟的时间。但是哈希表的速度明显是要比前面看到过的快的。并且编程的实现也是比较容易的。

哈希表也自己的确定的，那就是它的辅助空间是数组，数组创建后，空间是难以扩展的。所以我们在创建哈希表的时候，一定要

先考虑好到底有多个数据要被插入进来的。

还有也没有一种简单的方法来遍历表中的数据项的。

所以，如果不需要遍历这个数据项的，并且可以提前预测数据量的大小，那么哈希表在速度和易用性上是无与伦比的。

 

其实很简单的几句话。但是真的没有触及到哈希表创建的核心。

所以我为你准备了一个人博客

http://blog.csdn.net/v_july_v/article/details/6256463

 

于是代码来了

 

package endual;

public class HashTable {

	private DataItem[] hashArray ; //hash表是基于数组的
	private int arraySize ; //创建hash表的时候，要先确定这个量要多少大
	private DataItem nonItem ; //hash表有一个是无法填满的
	
	public HashTable(int arraySize) {
		super();
        this.arraySize = arraySize ; //输入的哈希表的大小
		this.hashArray = new  DataItem[this.arraySize] ; //创建输入创建哈希表的大小
		nonItem = new DataItem(-1) ; //用于删掉的数据项,将这个数据项放入到空的地方，如果遇到这个关键词是-1的那么说明这个数值的地方是空的
		
	}
	
	//用for循环的方法来遍历这个哈希表
	public void displayHashTable() {
		
		System.out.println("Table :") ;
		for(int j=0; j < this.arraySize; j++) {
			
			if(this.hashArray[j] != null) { //如果这个hashArray[j]数据项是存在的，那么我们去输出它的key值
				
				System.out.println(hashArray[j].getiData() + " ");
				
			}else {
				System.out.println("**");
			}
			
			System.out.println("**");
			
		}
		
	} //end 显示的方法
	
	public int hashFunc(int key) { //那么我们可以肯定的是key的值是很大的数多对吧，要不取余数的时候，不都是0 了啊
		
		return key % this.arraySize ; //取得余数
		
	} //取得hash值的转换函数（哈希函数）
	
	
	//插入数据了
	public void insert(DataItem item) {
	
		//假设table不是为空的
		int key = item.getiData() ; //取得数据项的关键值
		int hashVal = this.hashFunc(key) ; //通过hash函数的转换获得hash值
		
		//两个条件要同时的满足
		//1.数组中的这个hash值的位子啊，不能有东西
		//2.这个数组的如果为空，也就是有数据项，那么这个数据项的关键词不能-1
		while (hashArray[hashVal] != null && hashArray[hashVal].getiData() != -1) {
			
			hashVal++ ; //如果数组中有数据项的，那么我们到数组的下个标号下面去看。
			hashVal %= this.arraySize ; //再转回hashVal的，因为当前hashVal的已经有人用了，用了就占据了数据的位子了
		}
		
		this.hashArray[hashVal] = item ; //找到这个空的null,将值放进去

	} //end insert
	
	//删掉一个数据项，根据关键字
	public DataItem delete(int key) {
		
		DataItem item = null ;
		//我们先求得关键词的hash值
		
		int hashVal = this.hashFunc(key) ;
	    
		
		while(this.hashArray[hashVal] != null) { //遇见空的停止掉
			if(this.hashArray[hashVal].getiData() == key) {
				item = this.hashArray[hashVal] ; //那么这个就是我们要寻找的
				this.hashArray[hashVal] = this.nonItem ;
				return item ;
			}
			hashVal++ ;
			hashVal %= this.arraySize ; //这个是定值是不能在改变了的
		}

		return null ;

	} //end delete
	
	//find
	public DataItem find(int key) {
		
		DataItem item = null ;
		int hashVal = this.hashFunc(key) ;
		while(this.hashArray[hashVal] != null) { //遇见空的停止掉
			if(this.hashArray[hashVal].getiData() == key) {
				item = this.hashArray[hashVal] ; //那么这个就是我们要寻找的
				return item ;
			}
			hashVal++ ;
			hashVal %= this.arraySize ; //这个是定值是不能在改变了的
			
		}

		return null ;
	}
	
	

	
} //end calss

 

 

 

 

 

   测试的类

 

package endual;

public class HashTableApp {

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

		HashTable ht = new HashTable(30) ;
		DataItem d1 = new DataItem(56) ;
		DataItem d2 = new DataItem(562) ;
		DataItem d3 = new DataItem(536) ;
		DataItem d4 = new DataItem(526) ;
		DataItem d5 = new DataItem(556) ;
		ht.insert(d1) ;
		ht.insert(d2) ;
		ht.insert(d3) ;
		ht.insert(d4) ;
		ht.insert(d5) ;
		ht.displayHashTable() ;
	}

}