野生前端的数据结构基础练习（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方法或添加新的方法。