热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

散列表的查找过程及优势与劣势

散列表是一种存储和查找方法,通过散列函数计算记录的散列地址来存储和访问记录。与线性表、树、图等结构不同的是,散列技术的记录之间不存在逻辑关系,只与关键字有关联。散列表的优势在于快速的查找速度,但也存在劣势。散列表最适合解决查找与给问题。

散列过程

整个散列过程其实就是两步。

1. 在存储的时候,通过散列函数计算记录的散列地址,并按此散列地址存储该记录。

就像张三丰我们就让他在体育馆,那如果是“爱因斯坦”我们让他在图书馆,如果是“居里夫人”,那就让她在化学实验室。如果是“巴顿将军”,这个打即时战略游戏的高手,我们可以让他到网吧。总之,不管什么记录,我们都需要用同一个散列函数计算出地址再存储。



2. 当査找记录时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录。说起来很简单,在哪存的,上哪去找,由于存取用的是同一个散列函 数,因此结果当然也是相同的。


  • 所以说,散列技术既是一种存储方法,也是一种查找方法。然而它与线性表、 树、图等结构不同的是,前面几种结构,数据元素之间都存在某种逻辑关系,可以用连线图示表示出来,而散列技术的记录之间不存在什么逻辑关系,它只与关键字有关联。因此,散列主要是面向査找的存储结构。

散列表的优势与劣势

散列技术最适合的求解问题是査找与给定值相等的记录。对于査找来说,简化了比较过程,效率就会大大提高。但万事有利就有弊,散列技术不具备很多常规数据结构的能力。

比如那种同样的关键字,它能对应很多记录的情况,却不适合用散列技术。一个班级几十个学生,他们的性别有男有女,你用关键字“男”去査找,对应的有许多学生的记录,这显然是不合适的。这个时候可以用班级学生的学号或者身份证号来散列存储,此时一个号码唯一对应一个学生才比较合适。

同样散列表也不适合范围查找,比如査找一个班级18-22岁的同学,在散列表中没法进行。想获得表中记录的排序也不可能,像最大值、最小值等结果也都无法从散列表中计算出来。


  • 我们说了这么多,散列函数应该如何设计?这个我们需要重点来讲解,总之设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。重复一遍,设计一个合适的散列函数最重要!

哈希冲突

另一个问题是冲突。在理想的情况下,每一个关键字,通过散列函数计算出来的地址都是不一样的,可现实中,这只是一个理想。

我们时常会碰到两个关键字key1 ≠ key2,但是却有f (key1) = f (key2),这种现象我们称为冲突(collision),并把key1和 key2称为这个散列函数的同义词(synonym)。出现了冲突当然非常糟糕,那将造成数据査找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少,但是不能完全避免。于是如何处理冲突就成了一个很重要的课题,这在我们后面也需要详细讲解。


  • 处理哈希冲突是个大坑……需要深入了解的东西很多。这里简单预告下,通常有两类方法处理冲突:开放定址(Open Addressing)法和拉链(Chaining)法。有兴趣可以跳到后面章节先了解下。

推荐阅读
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例,帮助开发者更好地理解和应用该方法。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法,提供了多个代码示例及应用场景,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 在 Windows 10 中,F1 至 F12 键默认设置为快捷功能键。本文将介绍几种有效方法来禁用这些快捷键,并恢复其标准功能键的作用。请注意,部分笔记本电脑的快捷键可能无法完全关闭。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 本文详细介绍了如何在BackTrack 5中配置和启动SSH服务,确保其正常运行,并通过Windows系统成功连接。涵盖了必要的密钥生成步骤及常见问题解决方法。 ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • 本文详细介绍了如何使用 Yii2 的 GridView 组件在列表页面实现数据的直接编辑功能。通过具体的代码示例和步骤,帮助开发者快速掌握这一实用技巧。 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • 本文详细介绍了Java中org.eclipse.ui.forms.widgets.ExpandableComposite类的addExpansionListener()方法,并提供了多个实际代码示例,帮助开发者更好地理解和使用该方法。这些示例来源于多个知名开源项目,具有很高的参考价值。 ... [详细]
author-avatar
mobiledu2502912527
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有