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

网上的相关教程非常多,基础知识自行搜索即可。 习题主要选自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方法或添加新的方法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】写代码,你应该知道九类规则

网上有太多讲编码规范、编码习惯的文章,但我总是念的多,实际去认真阅读理解的少。或多或少的按照自己的思维去编写代码。这种习惯让我吃大亏,比如一个指针未赋值导致偶尔...

43350
来自专栏AI研习社

NumPy 将停止支持 Python 2,这里有一份给数据科学家的 Python 3 使用指导

Python 已经成为机器学习和数据科学的主要编程语言,同时 Python 2 和 Python 3 共存与 Python 的生态体系内。不过,在 2019 年...

352110
来自专栏数据结构与算法

带修改莫队算法

update in 2017.12.24: 以前写的≈shit,实在看不下去了,重写一遍 pre 很早之前就学习了莫队算法。 老师讲课的时候就提到过带修改莫...

32570
来自专栏CDA数据分析师

教你一招:用 50 行 Python 代码制作一个计算器

简介 在这篇文章中,我将向大家演示怎样向一个通用计算器一样解析并计算一个四则运算表达式。当我们结束的时候,我们将得到一个可以处理诸如 1+2*-(-3+2)/5...

21870
来自专栏屈定‘s Blog

设计模式--组合模式的思考

组合模式是一种抽象树形结构的模式,其在业务开发中也是一种很有用的设计模式,下面开始分析.

43230
来自专栏编程

Python教学——第六天

今天我们要说说dict,在第四天里我们说到了tuple,list也知道了list比tuple好用多了,至少能添加删除还能修改里面的值 在Python里,我们知道...

20470
来自专栏每周一脱topic

Effictive python学习总结连载(1)

python从读研开始就在用了,拿来做过web后台、安全分析、爬虫、测试框架等等,挺强大的。最近借放假和看书和整理的机会,系统的总结下。主要是2方面:一个是书或...

22120
来自专栏AI科技大本营的专栏

实操 | 内存占用减少高达90%,还不用升级硬件?没错,这篇文章教你妙用Pandas轻松处理大规模数据

编译 | AI科技大本营(rgznai100) 参与 | 周翔 注:Pandas(Python Data Analysis Library) 是基于 Num...

27640
来自专栏代码世界

计算机基础,Python基础--变量以及简单的循环

一、计算机基础 1.CPU   相当于人体的大脑,用于计算处理数据。 2.内存    用于存储数据,CPU从内存调用数据处理计算,运算速度很快。 PS:问:...

28770
来自专栏C/C++基础

C++ 模板元编程简介

模板元编程(Template Metaprogramming,TMP)是编写生成或操纵程序的程序,也是一种复杂且功能强大的编程范式(Programming Pa...

1.5K30

扫码关注云+社区

领取腾讯云代金券