`
hwfantasy
  • 浏览: 21489 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

迟到的Hash表

阅读更多
  本来已经躺在床上准备呼呼大睡了,突然想到hash表的博客还没发表,于是大半夜爬了起来发了这篇文章,希望没有扰人清梦就好了。本来一直以为是早就发了的,然后今天晚上躺在床上才忽然意识到还没有发,最近过的有点浑浑噩噩的,悲剧啊。
  这个代码是自己模拟哈希表实现的一个简单的学生统计系统,具体是实现的散列表中的开散列,即用数组保存一组数据,这一组数据中通过链表连结彼此,于是达到增加,查找,替换,删除的功能。
  hash的预映射算法比较简单,即将学生学号的各个位相加,得到的个位数数值即为散列值,因为个位数所以数组大小为10.
private int handdata(Student stu) {
		int num = stu.numb;
		while (num > 9) {//循环运算直到num变为个位数
			num = num / 10000 + num % 10000 / 1000 + num % 1000 / 100 + num
					% 100 / 10 + num % 10;//将各个位的值相加的运算
		}
		return num;
	}

  接下来要设计学生的类,这也是hash表中数组中保存的对象的类。
public class Student {
	public String name="11";
	public int numb=11111;
	public int gride=11;
	public Student before=null;
	public Student next=null;
	
	/**
	 * 重新构造方法以传入数值
	 * @param name
	 * @param numb
	 * @param gride
	 */
	public Student(String name,int numb,int gride){
		this.name=name;
		this.gride=gride;
		this.numb=numb;
	}
	
	//这个构造方法用来实现默认的对象
	public Student(){		
	}
	
	//改变对象下一个和上一下结点的方法
	public void changenext(Student s){
		next=s;
	}
	
	public void changebefore(Student s){
		before=s;
	}
}

  创建hash表和向其中加入元素的方法
  这里要注意的是在加入新对象时记得去掉默认的对象
	/**
	 * 创建hash表的方法
	 * @param stu
	 */
	public void createHash(Student stu) {
		for (int i = 0; i < 10; i++) {
			Student st = new Student();
			hash[i] = st;
		}//首先默认对数组每个下标值对应的加入一个对象
		int hashcode = handdata(stu);//获得散列值
		hash[hashcode] = stu;//加入对象
	}

	/**
	 * 向hash表内加入元素的方法
	 * @param stu
	 */
	public void addHash(Student stu) {
		int hashcode = handdata(stu);
		if (hash[hashcode] == null) {
			hash[hashcode] = stu;
		} else {//如果此散列值对应的不为空,那么去掉默认的对象(如果有),加入新对象
			Student stut = hash[hashcode];
			if (stut.name.equals("11")) {
				hash[hashcode] = stu;
			} else {
				while (stut.next != null) {
					stut = stut.next;
				}
				stut.next = stu;
			}
		}
	}

  查找表中已存在的元素很简单,即将它的学号处理得到散列值然后遍历hash表即可(这里给予的值可以是学生类的对象,也可以是学生的学号,大体上没什么区别)
public Student seekHash(Student stu) {
		int hashcode = handdata(stu);
		Student stu2 = hash[hashcode];
		while (stu2.numb != stu.numb) {//反复查找直到找到对应的对象
			stu2 = stu2.next;
		}
		System.out.println("姓名:" + stu2.name + "\t学号:" + stu2.numb + "\t分数:"
				+ stu2.gride);
		System.out.println("查找完成。");
		return stu2;
	}

  替换表中元素和删除表中元素其实差不多,都是找到这个对象然后改变它父结点和子结点中指针的指向来达到目的的,其中要注意的就是找到的这个结点可能没有父结点或子结点,这时需要分开讨论(由于删除牵涉到2个需要讨论的结点之间的操作,所以比替换略复杂)
/**
	 * 替换hash表元素的方法
	 * 
	 * @param stu1
	 * @param stu2
	 */
	public void changeHash(Student stu1, Student stu2) {
		int hashcode = handdata(stu1);
		Student stu = seekHash(stu1);
		if (stu.before != null) {//分before和next讨论
			Student stu3 = stu.before;
			stu3.next = stu2;
			stu2.before = stu3;
		} else {
			hash[hashcode] = stu2;
		}
		if (stu.next != null) {
			Student stu4 = stu.next;
			stu4.before = stu2;
			stu2.next = stu4;
		}
	}

	/**
	 * 删除hash表元素的方法
	 * 
	 * @param stu
	 */
	public void deleteHash(Student stu) {
		int hashcode = handdata(stu);
		Student stu0 = seekHash(stu);
		if (stu0.before != null && stu0.next != null) {//各种讨论
			Student stu1 = stu0.before;
			Student stu2 = stu0.next;
			stu1.next = stu2;
			stu2.before = stu1;
		} else if(stu0.before == null && stu0.next == null){
			hash[hashcode] = new Student();
		}else if(stu0.before == null && stu0.next != null){
			Student stu3=stu0.next;
			stu3.before=null;
		}else if(stu0.before != null && stu0.next == null){
			Student stu4=stu0.before;
			stu4.next=null;
		}
	}

  以上就是我的简单的开散列,下面附上实例结果,分别为创建添加,替换,删除后的遍历结果(查找已在替换和删除中体现)
引用
数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:lihao4 学号:2 分数:84
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。

姓名:lihao4 学号:2 分数:84
一次查找完成。

数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:lihao5 学号:2 分数:88
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。

姓名:lihao5 学号:2 分数:88
一次查找完成。

数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:11 学号:11111 分数:11
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。
分享到:
评论

相关推荐

    C语言实现的Hash表(代码)

    Hash表是一种数据结构,它通过使用哈希函数将键(key)映射到数组的索引位置,从而实现快速的查找、插入和删除操作。在C语言中,我们可以利用结构体和指针来构建一个简单的Hash表。下面将详细介绍Hash表的概念、哈希...

    oracle分区表之hash分区表的使用及扩展

    Oracle分区表中的Hash分区是一种基于哈希算法的分区策略,适用于处理无法清晰定义分区范围的大型数据表。这种分区方式通过计算分区键的哈希值来决定数据存储在哪个分区,以此达到数据分散和负载均衡的目的。Hash分区...

    c语言hash表源码

    哈希表(Hash Table)是一种数据结构,它通过计算一个关联数组中的索引来确定一个特定元素的存储位置,使得在平均情况下,查找、插入和删除操作的时间复杂度达到O(1)。C语言中的哈希表实现是程序员常用的数据结构...

    HASH_hash_stm32hash_stm32hash表_stm32f407_

    在STM32F407上实现的哈希(Hash)算法是数字签名、数据完整性验证等安全应用中的关键组成部分。哈希算法能够将任意长度的输入数据转化为固定长度的输出,通常称为哈希值或消息摘要。 哈希算法的主要特性包括: 1. *...

    hash表的应用

    Hash表应用 (必做) (查找) [问题描述]  设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; ...

    Hash表模板类

    在"hash表模板类"这个压缩包中,你可能找到了一个实现了以上功能的C++源文件。通过阅读和理解代码,你可以学习到自定义哈希表的实现细节。此外,附带的测试代码和可运行文件可以帮助你验证该哈希表模板类的正确性,...

    基于HASH表和SYN计算的TCP包重组方法.rar

    "基于HASH表和SYN计算的TCP包重组方法"是一种优化的重组策略,旨在提高数据恢复的效率和准确性。 TCP报文段重组的核心是确保数据的正确性和完整性。在传统的TCP实现中,通常使用滑动窗口协议来跟踪接收到的报文段,...

    Hash表的建立和查找

    "Hash表的建立和查找" Hash表是一种高效的数据结构,它通过哈希函数将关键字映射到索引上,以便快速地存储和查找数据。Hash表的建立和查找是数据结构课程的重要内容,本文将详细介绍Hash表的建立和查找的知识点。 ...

    uthash表操作函数

    hash表操作函数 HASH_ADD_INT HASH_ADD_STR

    自己实现的hash表

    在编程领域,哈希表(Hash Table)是一种高效的数据结构,它通过特定的哈希函数将数据映射到一个固定大小的数组中,以实现快速的查找、插入和删除操作。哈希表的关键在于设计良好的哈希函数,该函数能够尽可能均匀地...

    高手打造最快的Hash表源码(和Blizzard的对话)

    Hash表是一种在计算机科学中广泛使用的数据结构,它通过一种特定的哈希函数将键(Key)映射到数组的索引位置,从而实现快速的查找、插入和删除操作。在游戏开发,尤其是在大型在线游戏中,高效的数据存储和检索对于...

    C#两级嵌套hash表

    封装hashtable的两级hash表,两个键值索引和访问。适合存放稀疏数据,如稀疏矩阵,稀疏表等结构,由于提供key-value的索引遍历,数据稀疏的情况下,相比于传统矩阵遍历的速度更快。

    打造最快的Hash表(和Blizzard的对话)

    ### 打造最快的Hash表(和Blizzard的对话) #### Hash表基础知识与应用场景 本文将深入探讨如何构建高效的Hash表,并特别关注Blizzard在游戏开发过程中所采用的技术。Hash表是一种利用散列函数来实现快速查找的数据...

    hash表操作

    该文档消息描述了hash表的创建、数据插入、数据删除、数据查找以及hash表销毁等操作

    打造最快的Hash表

    哈希表(Hash Table)是一种数据结构,它通过哈希函数将输入(通常是字符串)映射到一个固定大小的数组的索引上,使得数据的查找、插入和删除操作能够达到近乎常数时间的复杂度,即O(1)。在编程中,哈希表的高效性能...

    hash表学习基础程序

    `study-hash`这个文件可能是对哈希表学习的代码实现,包括了哈希函数的设计、冲突处理方法的实现,以及可能的一些性能测试。通过阅读和理解这个程序,你可以更深入地掌握哈希表的工作原理和实际运用。在实践中,不断...

    IT笔试面试--链地址Hash表的代码实现,运行正确+详细注释

    链地址Hash表的代码实现 链地址Hash表是一种常用的Hash算法,它的优点在于可以快速查找数据,同时占用的内容空间也非常小。 链地址Hash表的实现可以分为四个步骤: 1. 定义Hash表和基本数据节点 在这里,...

    Hash表

    总结文档`hash表.doc`和`hash总结.doc`可能涵盖了哈希表的基本概念、原理、哈希函数的设计、冲突解决策略以及哈希表在实际应用中的案例分析。深入阅读这些文档将有助于进一步理解哈希表的工作机制及其在软件开发中的...

    PE导入表-函数列表-HASH值

    了解和分析PE导入表及函数的HASH值在逆向工程、病毒分析和恶意软件检测中至关重要。通过查看导入表,安全专家可以识别程序依赖的库和可能的恶意行为。同时,计算函数的HASH值可以作为一种快速检查技术,以确定代码...

Global site tag (gtag.js) - Google Analytics