数据结构 -散列的基本知识、函数应用及练习

概述本文章向大家介绍数据结构 - 散列的基本知识、函数应用及练习，主要包括散列的定义、特点、常见散列函数、散列碰撞的一般解决方法、散列函数应用等等，需要的朋友可以参考一下

散列的基本知识

定义

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

特点：

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

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

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

常见散列函数

除法散列法

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

平方散列法

斐波那契散列法

散列碰撞的一般解决方法

拉链法

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

线性寻址法

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

散列函数应用

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

基本练习

编写一个简易Hash类:

属性

this.table 线性存储空间

方法

simpleHash( )简易的哈希函数

show( )显示整个存储信息

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

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

课后习题（书中第八节习题）

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

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

习题思路

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

总结

以上是内存溢出为你收集整理的数据结构 - 散列的基本知识、函数应用及练习全部内容，希望文章能够帮你解决数据结构 - 散列的基本知识、函数应用及练习所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。