一般的线性表、树,数据在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。
若想能直接找到需要的记录,必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应,这就是哈希表。
哈希表是一种数据结构,它可以提供快速的插入操作和查找操作。
哈希表是基于数组结构实现的,所以它也存在一些缺点:
数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重。
这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。
所以在以下情况下可以优先考虑使用哈希表:
不需要有序遍历数据,并且可以提前预测数据量的大小。
以下为本人看过的一个很好的例子,形象的说明为什么在比较两个对象时,必须要重载equals和hasCode方法。
1.hashcode是用来查找的,如果你学过数据结构就应该知道,在查找和排序这一章有
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的余数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除8求余数直接找到存放的位置了。
2.但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals(),为什么还要重写hashCode()呢?
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊
分享到:
相关推荐
哈希表数据结构实现代码,符合ADT要求,头文件放ADT函数接口定义和存储结构定义,cpp文件放实现,在控制台查看输出,C语言实现,功能多,注释多,轻松易懂,可用来初学或者作业完成
哈希表 哈希表_使用C语言实现哈希表数据结构_HashTable
哈希表 数据结构 课程设计 C++ 报告 资源整合 希望支持
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名
含需求分析、概要设计、详细设计、调试分析、使用说明、测试结果、附件。...待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
2.按照学号字段建一个哈希表,实现按学号进行查找 务必用哈希结构实现 3.按照姓名字段构建哈希表结构,实现姓名的模糊查询。姓名取中文姓氏作为哈希地址 4.排序 实现多关键字排序 5.分别使用堆排和快排显示成绩前10...
现在只能实现关键字为数字,存储单位为为字符串类型的,给大家简单的提供下HASH表的存储原理
数据结构里哈希表的实验报告 构造二叉树,构造哈希表等 c语言版
数据结构输出一个哈希表,这是我自己写的程序,输出完全没有问题,用C++编写,安全可靠。
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
数据结构课程设计, hash表,哈希表。
/******************* 数据结构哈希表算法实现 ********************/
C语言数据结构 除留余数法 二次探测再散列解决冲突
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
数据结构课程设计--哈希表实验报告.doc
很简单的一个.........................................................
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
哈希表的数据结构哈希表的数据结构哈希表的数据结构哈希表的数据结构
1、讲解和演示哈希表的建立和数据查询功能的实现原理; 2、讲解和演示哈希表用于映射类(CMap)的开发方法;
数据结构 (课程设计)哈希表实现数据结构 (课程设计)哈希表实现