(1) 为什么要使用hash这种数据结构?
众所周知,在编写的程序中,对数据的查找和处理是司空见惯的,特别是对一大堆数据而言。而作为最基本的数据结构,数组和链表而言,它们各具优势与缺陷。数组由于其存储的地址连续性及长度固定性,在查找操作上极具优势,只需要一次换算就能找到相应位置的数据,但是在插入、删除等操作上,却需要重新构造一个新的数组,这在空间及时间上是及其浪费的;而链表这种数据结构刚好相反,由于物理地址空间是随机分布的,各个节点之间是用索引相互串联起来的,所以其查找效率低的可怕,为了查找一个数据就不得不全部遍历一遍,但是对于插入、删除等操作而言,链表就极具优越性,它只需要改变操作位的索引即可,不需要像数组那样重新构造,这样效率也就极大的提高了。
由上可见,数组和链表在不同的操作上各具其优势,那么,我们所需要的就是如何做到这两种优势的融合,诞生出一种新的数据结构,既在查找上具有数组的速度,在插入和删除上也具有链表的效率。Hash就是为了实现这种效果而产生的,它天生就是为了提高查找和其他操作等效率而存在的,那么Hash到底是以一种什么样的结构存在呢,它又是如何做到效率的提高呢?
(2) 什么是Hash?
Hash这种算法的概念,可以理解为一种分组处理的方法,把大的数据分组成小的数据量,再在上面进行处理,以此来提高效率。它将任意输入的数据同过Hash()函数的运算得出该数据的hash值,也可理解为是该数据的标识,hash通过该数据的hash值对其进行处理。每个数据都通过这种方法进行映射处理,把不同的数据映射到一个用数组数据结构建立的表,这种表称为hash表或者散列,其地址空间是有限的。这种通过hash()函数的映射是一种压缩映射,也就是说hash表上的空间远远小于输入的数据的空间,不同的数据输入可能会映射成相同的hash值输出,因此,不可能从hash值来唯一确定输入的数据数值,这就是hash()函数所做的。
对于不同的数据,当其hash值一样时,就把它加入到该hash表中对应的位置,如果该位置尚且为空则大可直接放入,否则就在该hash表的位置上构建一个链表,把该数据用链表的方式加入到该位置上。
由此可见,hash是一种数组和链表的融合,在两者的优势上取的平衡,当然随着数据量的增加,这种平衡可能会被打破,这时我们就需要重新构造一个hash,这个过程叫做reHahs(),这个会在后面详细讲述。当你需要查找并处理一个数据是,你可以通过hash()函数映射到其所在的hash表上的位置,然后再在该位置上的链表结构上查找和处理该数据,查找的代价也就是在链表中,但由于这个链表比起原数据量少的多,几乎没有什么迭代的代价可言了,所以其操作速度也就大大提升。就这样达到了在数组与链表上取得平衡,提高了数据处理效率。
(3) reHash()?
在上面已经说过,虽然在hash结构建立后取得了平衡,但是由于数据量及其类型往往是动态的,所以当输入数据量过多时,这种平衡就必然会被打破,这样也必然使该hash的效率降低,性能递减,因此,我们必须设置一个阈值来作为这个平衡的容差标准。当超过这个阈值时,就不得不重新定义及构造一个新的hash,当然这样的情况不会很平凡,所以对效率的影响不至于很大。那么这个阈值要根据什么来定义呢?
我们知道,hash对于效率的提高是通过分组来实现的,在hash表上的快速定位后,在只有少量数据的链表上进行操作。也就是说,由于hash表的地址是有限的,输入数据不断增加时,链表的长度也会随之增加,当大部分的链表上的数据超过过一定的量后,就会使得该hash结构的效率降低。
为此,我们rehash()所要做的就是当超过阈值后,加长hash表的地址空间,改变hash()函数,重新分配数据,以此来解决链表过于冗余的现状。
当然,阈值的设置因使用情况和所需处理的数据而定,主要目的就是为了保持平衡,保持效率。
分享到:
相关推荐
Hash表应用 (必做) (查找) [问题描述] 设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; ...
HASH函数及其应用_朱全民.ppt
Hash_算法及其应用.doc
hash函数与消息认证讲义 包括 5.1 Hash函数概述 5.1.1 Hash函数定义 5.1.2 Hash函数的安全性 5.1.3 Hash函数的迭代构造法 5.2 Hash函数MD5 5.2.1 MD5算法 5.2.2 MD5的安全性 5.3 安全Hash算法SHA-1 5.3.1 SHA-1...
数据库理论 hash index ppt;数据库理论 hash index ppt数据库理论 hash index ppt;数据库理论 hash index ppt
js单页hash路由原理与应用实战详解.docx
hash算法的讲解与应用,很适合入门与提高,讲解到位,相互交流。
hash应用与实践 入门提高 详尽 基础的介绍
理解内存页面调度的机理,掌握几种理论调度算法实现,并通过实验比较各种调度算法的优劣。此外通过实验了解HASH表数据结构的使用。
hash_map
Hash算法在智能门锁中的应用.doc
MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...
uthash开源的hash函数实现,里面的uthash.h可用
uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论...
由于项目中要用到hash,最近在研究Hash算法有关资料,这是在网上收集的有关hash算法程序,对学习hash算法有一定的帮助,果断大出来分享给大家,呵呵!
哈希表应用C++_STL_hash 哈希表应用C++_STL_hash 哈希表应用C++_STL_hash
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
hash树建立的过程,hash树在关联规则的发现过程的应用。
内容描述:用于crypto中hash爆破的强大工具。 优势:相较于其他hash工具,具有更快的算力,使用方便简洁。 适用:适用于md5,sha256等典型hash加密方式,反推出所需的源码。
stm32f407平台上实现的hash算法