曾经见过一句话,不记得具体了,但是大意就是:一个好的数据结构和一个差的程序代码远远比一个好的程序代码和一个差的数据结构要好。
慢慢的开始同意说这句话的人了。
数组和链表是数据结构中最基础的两个结构,其他几乎许多结构如队列、树、表都可以利用其实现。以前曾经实现过用数组和链表实现的队列,两者的差别很明显:
1.数组由于要先开辟内存空间,所以所需要的空间比较大,并且一般都会有浪费;队列采用离散存储方式,需要的空间比较小;
2.数组存在唯一序列号,查询、修改数据比较方便;队列在以上方面浪费时间比较多,但是添加数据不限空间,删除数据也不会有闲置空间;
总值,两者的取舍就得看实际情况中对时间和空间的要求了。
但是,想想:如果把两者结合一起又会如何呢?能实现两者的均衡利用吗?
于是又一种新的数据结构得到了使用,哈希表便是把这两者结合的一种运用方式:定义一个固定长度的数组,数组中存放链表实现数据的存储。
基础步骤是:
1.设定数组长度;
2.对所要存储的对象以一个特定int值对长度取余;
3.将余数相同的对象以链表方式存入同一个数组元素中。
所需要考虑的问题最基本的有:
1.数组长度是否合理;
2.链表长度是否合理。
代码的基本思路是:
1.创建一个节点类。
属性:节点数据(E data)、节点指向的下一个节点(HashLinkNode next)、用来确定余数的特殊值(int value);
方法:构造方法,获得特殊值的方法;
2.创建哈希表类
属性:表长(int length)、表数组(Mylink con[])、表冲突数(int strif)、表中数据总量(int count);
方法:构造方法,获得表数据总量的方法,向表中添加数据的方法,获得所有数据的方法,显示哈希表结构的方法,(根据指定长度)重新构造哈希表的方法。
3.学生类和测试类。
遇到的问题:
1.向哈希表数组元素,即链表中用add()添加数据时,如果该链表本来为空,出现空指针。
这是自己创建链表时一直没有解决的问题,今天想到可以用链表的构造方法先创建节链表,然后将该临时链表赋给数组元素。
if(con[i]==null){
MyLink<E> tempLink=new MyLink<E>(e);
con[i]=tempLink;
}
2.写获取所有哈希表数据时,返回数据类型的确定。
首先想到的是创建泛型的数组:E es=new E[count];但是,java本身好像还没有办法实现这样数组的创建;
然后,想到的是返回E[]类型的数据,创建数组时先用Object os=new Object[count];然后返回时再转型,但是,始终出现错误。泛型使用时要注意的东西很多,一次性避免对于现在的我来说还是比较困难的,只能一次一次的猜测和尝试,不怕麻烦大概就是程序员必备的素质。不怕。
当然,后来想着别返回泛型数组了,可以用Queue啊。但是,Queue太容易出现空指针了,用add()时要注意,当然还是没有找到好的解决方法。
所以最后还是找到LinkedList,试了一下add(),很好。
3.打印哈希表结构时,总是重复显示多次内容。
for循环是问题所在,当然也是通过多次测试性的System.out.print()找到问题并解决的额。
4.rehash时也出现了很纠结但是又很低级的问题,具体就不说了
结论就是,在避免麻烦复制粘贴已有代码时,也要再回过头来看一下每行代码的必要性,他们不仅仅可能是多余的,更有可能会成为错误所在。而这时发生错误时要发掘是很困难的,因为错误并不是在这一行,所以先检查一遍,磨刀不误砍柴工。
经历过才懂得就是这个道理吧。自己写过和看过是完全不同的感受。就算没有时间把要写的和想写的写完,但是写好自己喜欢的。
还需要想的问题:
1.这种结合数组和链表的方式是不是已经是最好了,还有其他解决方式吗?
2.有可能把数组和树结合起来吗?
3.rehash的算法是否能更简单,能不用把所有数据取出来再添加吗?或许能够利用他们在hash表中的结构再简单重新排序一下就行了,比如length再加长1个单位时,所有链表的root节点是不用变的,以后的再看各自原排在链表的第几位再按规律添加至下几个数组元素中。
4.hash表的length合适与否,究竟怎样安排,靠冲突指数?那冲突指数的设定呢?还是怎样都是“视情况而定”?
。。。。。。
多提问题,哪怕很简单很白痴,也似乎没有意义。
分享到:
相关推荐
问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法...
设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希...
C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成...
在这个特定的C++程序中,哈希表被用来实现一个数字排序算法,特别是针对大整数范围内的数据。程序的目标是处理多组测试数据,每组数据包括两个整数n和m,以及n个在[-500000, 500000]区间内的整数。使用哈希表可以...
C语言基于哈希表实现通讯录 在本文中,我们将探讨使用C语言基于哈希表实现通讯录的方法。哈希表是一种高效的数据结构,能够快速地存储和查找数据。在本文中,我们将通过设计和实现一个通讯录系统,来展示哈希表的...
### 哈希表实现与电话号码查询:深入解析与C语言代码分析 #### 哈希表基础知识 哈希表是一种数据结构,它通过使用哈希函数将键(key)映射到值(value)的存储位置,从而提供快速的数据访问能力。哈希表在理想情况...
数据结构的课程设计 哈希表实现电话号码查询系统
哈希表是一种高效的数据结构,它通过特定的函数(哈希函数)将数据映射到一个固定大小的数组中,从而实现快速的插入、查找和删除操作。在本项目"用C++实现的电话号码查询系统"中,哈希表被用来存储电话号码及其对应...
在压缩包中的"hash表学习"文件中,可能包含了关于哈希表实现的具体代码示例,包括哈希函数的定义、冲突解决策略的实现以及插入、查找和删除操作的算法。通过阅读和理解这些代码,你可以更深入地了解哈希表的实际应用...
(1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,报告全面,下载即用。 数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,...
本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。 (1)按提示输入相应的联系人的相关...
总结来说,这个电话号码查询系统通过哈希表实现了高效的记录存储和检索。哈希函数的设计和再哈希策略确保了冲突的最小化,使得数据查找和插入的时间复杂度接近O(1)。通过结构化的程序设计,用户可以方便地管理、查询...
《哈希表实现电话号码查询系统》 哈希表是一种高效的数据结构,广泛应用于各种数据库和查询系统中,尤其在电话号码查询系统中,它的快速查找能力显得尤为重要。本课程设计的目标是通过实现哈希表,提高对数据结构的...
《哈希表实现电话号码查询》 在计算机科学中,数据结构是编程的基础,而哈希表作为一种高效的数据结构,广泛应用于各种信息查询系统。本报告主要探讨如何使用哈希表来实现电话号码的快速查询,以满足对学生信息管理...
报告书主要围绕使用哈希表实现电话号码查询这一主题展开,涵盖了从需求分析、系统设计到实现和总结的全过程。以下是相关知识点的详细说明: 1. **哈希表(Hash Table)**:哈希表是一种数据结构,它通过计算一个...
总之,C++中的哈希表实现涉及到哈希函数设计、冲突解决策略的选择以及相关的插入、查找和删除操作。通过`HashTest.cpp`和`Hashtable.h`,我们可以深入理解这些概念,并通过实际代码来学习和测试哈希表的功能和性能。
哈希表是一种高效的数据结构,它通过特定的算法——哈希函数,将任意大小的键(key)映射到一个固定大小的数组中,从而实现快速查找、插入和删除操作。在C语言中,实现哈希表需要理解其基本原理,并掌握如何利用...