哈希表(Hash Table)

发布时间:2017-3-27 16:34:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"哈希表(Hash Table) ",主要涉及到哈希表(Hash Table) 方面的内容,对于哈希表(Hash Table) 感兴趣的同学可以参考一下。

参考:

Hash table - Wiki

Hash table_百度百科

从头到尾彻底解析Hash表算法

谈谈 Hash Table

我们身边的哈希,最常见的就是perl和python里面的字典了,字典有什么性质,给定键就可以直接找到值,字典封装了一种映射关系(散列函数),它和数组完全不同,数组是根据地址来访问值。

定义:给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

这个世界上没有十全十美的东西,所以我们要学会取舍。任何技术的实现都没有最好的只要最合适的,也就说实现的最佳方案是和应用场景息息相关的。
很多时候,我们想对数据进行快速的存取(比如缓存的实现),并用一个key来标记自己存取的数据。我们可以把它叫做key-value的结构。
说到“快速”我们很快想到数组,因为数组可以在O(1)的时间复杂内完成指定位置元素的读写操作。
所以在理想状态,如果一个数组足够长,且存在一个函数可以将每一个key映射到唯一的一个数组下标,那么我们就可以很完美的解决问题。但往往资源都是有限的,我们没有那么大的空间,也不能设计一个无比负责的映射算法保证每一个key对应到一个唯一的数组下标。所以我们会选择一些折中的方案。

hash table便是为解决这类问题而存在的。


上一篇:MySQL 各种超时参数的含义
下一篇:HTML5 & CSS3初学者指南(1) – 编写第一行代码

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款