野生前端的数据结构基础练习(5)——散列

举报
大史不说话 发表于 2018/10/31 11:24:21 2018/10/31
【摘要】 网上的相关教程非常多,基础知识自行搜索即可。习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Hash散列的基本知识定义哈希表是一种根据关键码去寻找值的数据映射结构,最直观的应用就是字典(现实的字典,不是数据结构的字典概念)。特点:插...

野生前端.jpg

网上的相关教程非常多,基础知识自行搜索即可。

习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。

参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Hash

散列的基本知识

  • 定义

    哈希表是一种根据关键码去寻找值的数据映射结构,最直观的应用就是字典(现实的字典,不是数据结构的字典概念)。

  • 特点:

    • 插入,删除,取用较快,查找较慢(例如查询最值,需要借助其他数据结构来提升效率)。

    • 散列函数应该使位置结果尽可能分散,以减少位置碰撞。

    • 设计良好的Hash表能在常数级时间下寻找到需要的数据。

  • 常见散列函数

    使用×××键对存储空间长度取模,所以存储空间长度一般取质数(取质数可以减小散列碰撞,不难理解)。

    • 平方散列法

    • 斐波那契散列法

    • 除法散列法

  • 散列碰撞的一般解决方法

    位置发生碰撞时使用链表或其他数据结构将碰撞元素连接起来。

    当发生哈希碰撞时,从当前位置向后寻找到第一个没有使用的位置,将要加入的数据放在该处。一般在可使用空间大于待存数据量2倍时使用。

    • 线性寻址法

    • 拉链法

散列函数应用

散列函数相关的应用非常广,例如webpack打包时在文件名中添加的哈希值,将给定信息转换为固定位数字符串的加密信息等都是散列的实际应用,感兴趣的读者可以自行搜索加密摘要算法相关关键词进行学习。

基本练习

编写一个简易Hash类:

  • 属性

    • this.table 线性存储空间

  • 方法

    • simpleHash( )简易的哈希函数

    • show( )显示整个存储信息

    • put(value)将一个值存入哈希表中

    • find(value)根据实际需要编写的查找方法

课后习题(书中第八节习题)

  1. 使用线性探测法创建一个字典,用来保存单词的定义。该程序需要包含两个部分:第一部分从文本中读取一组单词和其定义,并将其存入散列表;第二部分让用户输入单词,程序找出该单词的定义。

  2. 用开链条法重新实现练习1。

习题思路

练习时可以先引入例题中的Hash类,然后通过extends来继承Hash类并复写set/get方法或添加新的方法。


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。