`
endual
  • 浏览: 3557087 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

哈希表的一些概念 代码(自己写)

 
阅读更多

首先,我们要明确一点是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() ;
	}

}
 

 

 

 

 

 

 

分享到:
评论

相关推荐

    哈希表源代码-哈希表模型

    在这个"哈希表源代码"压缩包中,我们可以期待找到实现哈希表的源代码,这对于理解哈希表的工作原理以及在实际编程中应用哈希表非常有帮助。 哈希表的基本概念: 1. 键值对:哈希表由一系列键值对组成,每个键对应...

    哈希表对象的源代码

    本主题将深入解析哈希表对象的源代码,探讨其核心概念和实现机制。 首先,哈希函数是哈希表的核心,它的主要任务是将任意大小的键转换为固定长度的索引。一个好的哈希函数应尽量使不同的键映射到不同的索引,以降低...

    哈希表C++代码实现

    在C++中,虽然标准库提供了`std::unordered_map`和`std::unordered_set`等容器来实现哈希表,但理解哈希表的底层工作原理并能自己编写实现,对于深入理解和优化算法至关重要。 首先,哈希表的基本组成包括两个部分...

    用哈希表查找的源代码

    这段代码展示了一个简单的哈希表实现,涉及到哈希函数设计、数据结构定义、冲突解决策略的基础概念以及如何向哈希表中添加数据。然而,代码中的某些部分,如`toascii`函数的具体实现、完整的冲突解决策略以及`hlist`...

    哈希表数据结构ADT实现代码

    C语言是一种静态类型语言,不支持类的概念,因此,哈希表可以通过结构体(struct)来实现。结构体中可能包含数组、链表或其他数据结构,用于存储键值对,并定义上述ADT操作的函数。 **哈希函数** 哈希函数将键转化...

    哈希表基本概念.docx

    ### 哈希表基本概念 #### 一、哈希表定义 哈希表(Hash Table),也称为散列表或哈希映射,是一种高效的数据结构,它通过使用哈希函数将键(Key)映射到桶(Bucket)的数组索引来实现数据的快速查找、插入和删除...

    哈希表的实现

    以上代码实现了一个基本的哈希表,其中哈希函数使用了简单的除留余数法,这种方法对于均匀分布的键可以得到较好的哈希效果,但如果有大量键模运算后结果相同,会导致冲突增多。实际应用中,可能会采用更复杂的哈希...

    哈希表查找(C语言实现)

    以上代码示例展示了如何在C语言中使用哈希表进行查找操作,其中哈希函数简单地采用取模运算,实际应用中应根据关键字类型和数据特点设计更合适的哈希函数。 总结,哈希表查找是一种高效的查找技术,其关键在于设计...

    数据结构 C语言 哈希表.docx

    本篇文章将围绕一个C语言中的哈希表实现案例展开,详细解析哈希表的基本概念、设计思路及其实现过程。通过阅读本文,您将了解到哈希表在C语言编程中的应用,并能够掌握如何构建一个简单的哈希表来解决实际问题。 ##...

    基于哈希表的代码相似度检测系统源代码

    【哈希表在代码相似度检测中的应用】 在软件开发过程中,确保代码的原创性和避免抄袭是至关重要的。为了达到这个目的,开发人员通常会利用代码相似度检测系统来检查代码之间的相似性。本项目“基于哈希表的代码...

    C语言实现的Hash哈希表

    在C语言中实现哈希表,我们需要理解哈希函数的设计、冲突解决策略以及动态扩容等核心概念。 哈希函数是哈希表的核心,它的主要任务是将输入的关键字(key)转化为数组的下标。一个理想的哈希函数应具备以下特性:...

    C 哈希表 完整代码及报告

    通过这个实验,学生能够深入理解哈希表的工作原理,熟悉拉链地址法解决冲突的方法,以及如何用C语言实现这些概念。此外,实验还涵盖了查找的基本概念,如顺序查找、二分查找、分块查找,以及动态查找表,如二叉排序...

    易语言源码易语言哈希表学习例程源码.rar

    哈希表(Hash Table)是数据结构中的一个重要概念,它在易语言中也有着广泛的应用。哈希表通过特定的哈希函数将数据映射到一个固定大小的数组中,实现快速查找、插入和删除操作。这份"易语言哈希表学习例程源码.rar...

    哈希表设计 代码加报告

    1. **背景介绍**:解释哈希表的基本概念和用途,以及为什么选择哈希表作为实验主题。 2. **设计目标**:明确实验的目标,比如实现一个高效、低冲突的哈希表。 3. **算法描述**:详细介绍所采用的哈希函数和冲突解决...

    哈希表相关概念、hash函数、hash冲突解决方案、代码示例

    哈希表是一种高效的数据结构,它利用哈希函数将键(key)转化为数组索引,以便快速访问、插入和删除数据。哈希表的核心在于它的哈希函数,它能够将不同键映射到不同的存储位置,理想情况下,每个键都能均匀地分布在...

    哈希表实例源码

    哈希表(Hash Table)是一种数据结构,它通过计算一个关联值(称为“键”或“索引”)的散列函数,将数据快速存取到...通过研究这个实例,你将能够更好地掌握哈希表这一核心概念,并为未来的学习和工作奠定坚实的基础。

    哈希表的设计与实现.rar

    通过阅读文档,我们可以理解哈希表的设计思路,学习如何构建和优化自己的哈希表实现。 7. **应用案例**:哈希表在很多领域都有应用,如数据库索引、缓存系统(如Redis的哈希类型)、字符串匹配(如Rabin-Karp算法)...

    用C语言实现一个简单的哈希表(hash table)

    总结,这个C语言实现的哈希表是一个基础教学案例,涵盖了哈希表的核心概念,包括哈希函数设计、冲突解决以及在C语言中的实际编码。通过对这个程序的学习,你可以深入理解哈希表的工作原理,并为将来更复杂的数据结构...

Global site tag (gtag.js) - Google Analytics