您好,欢迎来到有书房!

Hash和Hash表

分类:知识大全作者:互联网王者 发布时间:2019-02-06 17:25:49阅读:1.7万+

引言:Hash,又叫散列或者哈希,狭义上是一种算法,可以说是一种压缩映射。意思是把任意长度的输入值通过算法变换成固定长度的输出,该输出就是Hash值。

        Hash,又叫散列或者哈希,狭义上是一种算法,可以说是一种压缩映射。意思是把任意长度的输入值通过算法变换成固定长度的输出,该输出就是Hash值。Hash值的空间通常远小于输入的空间,不同的输入可能会有相同的输出,所以不可能从Hash值来确定唯一的输入值。但是可以根据同一哈希值的输入值集合起来形成一个库。因此可以进行一定程度上的反查。广义上Hash是一种思想,这种思想下可以有很多不同的算法,只要符合哈希定义,都可以统称为哈希算法。


        Hash Table(哈希表),也称为散列表,是一种数据结构,它允许用户通过将键映射到一个唯一的地址(哈希地址)来进行快速访问。通过将关键字映射到表中一个位置, 可以直接访问记录, 以提高查找的速率,相比较其他的查找结构,哈希表查找的时间复杂度更低。


        比如若关键字为key,则其值存放在f(key)的存储位置上,不需比较便可直接取得所查记录。称这个对应关系f为哈希函数,按这个思想建立的表为哈希表。哈希表的主要特点是能够在几乎常量时间内完成查找、插入和删除操作。数组寻址容易,插入和删除困难,而链表寻址困难,插入和删除容易,而哈希表寻址容易,插入删除也容易。


        不过对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)==f(key2),这种现象称为哈希冲突。处理冲突的方法主要有以下几种,第一种是开放定址法,即每次尝试一个新的哈希地址直到找到空闲的位置;第二种是链地址法,即每个冲突的键都会链接到一个额外的链表中;第三种是再哈希法,即使用多个哈希函数,这样可以创建更多可能的哈希地址空间,当然也有其他很多方法可以处理。


        因此哈希表通常意义上由哈希函数、哈希表数据以及处理冲突的方法。哈希表的设计应考虑到计算哈希函数所需时间、关键字的长度、哈希表的大小、关键字的分布情况和记录的查找频率等因素。总的来说,哈希表的数据结构有巨大的优势,因此在计算机语言开发、数据库设计、操作系统开发、网络程序开发等领域都有着广泛的应用。


声明:本文内容版权归原作者所有,未经授权,禁止转载!

声明:本站仅提供内容存储、展示服务,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的虚假信息,谨防诈骗。如发现有害或侵权内容,可联系本站删除!

发表评论

评论

联系
我们

平台负责人邮箱
282271588@qq.com

关注
公众号

关注官方公众号

下载
安卓版

下载安卓版

回到
顶部