大家好，又见面了，我是你们的朋友全栈君。
网上的相关教程非常多，基础知识自行搜索即可。
习题主要选自Orelly出版的《数据结构与算法javascript描述》一书。
参考代码可见:https://github.com/dashnowords/blogs/tree/master/Structure/Hash
散列的基本知识
-
定义
哈希表是一种根据关键码去寻找值的数据映射结构，最直观的应用就是字典（现实的字典，不是数据结构的字典概念）。
-
特点：
- 插入，删除，取用较快，查找较慢（例如查询最值，需要借助其他数据结构来提升效率）。
- 散列函数应该使位置结果尽可能分散，以减少位置碰撞。
- 设计良好的Hash表能在常数级时间下寻找到需要的数据。
-
常见散列函数
- 除法散列法
使用×××键对存储空间长度取模，所以存储空间长度一般取质数(取质数可以减小散列碰撞，不难理解)。
-
平方散列法
- 斐波那契散列法
-
散列碰撞的一般解决方法
- 拉链法
位置发生碰撞时使用链表或其他数据结构将碰撞元素连接起来。
- 线性寻址法
当发生哈希碰撞时，从当前位置向后寻找到第一个没有使用的位置，将要加入的数据放在该处。一般在可使用空间大于待存数据量2倍时使用。
散列函数应用
散列函数相关的应用非常广，例如webpack打包时在文件名中添加的哈希值，将给定信息转换为固定位数字符串的加密信息等都是散列的实际应用，感兴趣的读者可以自行搜索加密，摘要算法相关关键词进行学习。
基本练习
编写一个简易Hash类:
- 属性
this.table线性存储空间
- 方法
simpleHash( )简易的哈希函数show( )显示整个存储信息put(value)将一个值存入哈希表中find(value)根据实际需要编写的查找方法
课后习题（书中第八节习题）
- 使用线性探测法创建一个字典，用来保存单词的定义。该程序需要包含两个部分：第一部分从文本中读取一组单词和其定义，并将其存入散列表；第二部分让用户输入单词，程序找出该单词的定义。
- 用开链条法重新实现练习1。
习题思路
练习时可以先引入例题中的Hash类，然后通过extends来继承Hash类并复写set/get方法或添加新的方法。
转载于:https://blog.51cto.com/13869008/2311035
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107224.html原文链接：https://javaforall.net
