Hash表实现原理与`其算法应用探讨.doc

Hash表实现原理及其算法的应用探析 　　摘 要Hash表是一种重要的数据结构，广泛应用于快速查找、匹配算法，同时在信息安全、数据库设计和海量信息处理方面有着重要的作用，本文首先介绍Hash表的的实现原理，进一步从Hash算法的常见应用场景探析其在各领域的广泛作用，渐进的讨论了数据结构中散列的思想，最后总结Hash算法的应用原则，帮助从业人员能够快速理解Hash的思想，并能够理解应用 【关键词】hash原理 hash算法 hash表 hash应用 1 引言 Hash即散列，是指设计一个散列函数把一个任意长度的输入转变为固定长度的输出，输出作为散列的hashkey，通常情况下，输入空间远大于输出空间，因此散列映射是一种压缩映射，但是不同的输入有可能会映射为相同的输出，所以通过hashkey不能唯一确定输入。Hash表是一种根据hashkey直接访问的数据结构，通过把关键字散列为一个hash值，然后根据hash值直接访问数据，理论上可以达到近似O（1）时间复杂度的访问速度，加快了查找速度。同时Hash也是一种重要的算法思想，在很多领域有着广发的应用。接下来本文通过对hash表的原理进行深入解析，进一步从应用的角度探析Hash算法的几个常见应用场景 2 hash表原理解析 2.1 基本原理 利用一个很大的数组存储数据，同时设计一个散列函数使得每个元素的关键字通过散列得到的散列值可以与数组下标对应起来，这样的一个数组称之为Hash表，但是因为每个数据的关键字通过散列函数得到的散列值有可能不是一一对应的，这时就会产生冲突，因此Hash表在设计的时候应该尽量选择较好的散列函数来避免或减少冲突 2.2 Hash函数构造与冲突处理 Hash表中元素是由Hash函数确定的。将数据的关键字Key作为输入变量，通过一定的映射关系，计算出的Hash值，即为该元素的存储地址Addr。表示为： Addr=H（key） 为此在建立一个哈希表之前需要构造一个合适的哈希函数，常见的哈希函数设计方法有：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。常见的有：开放定址法、再哈希法、链地址法、建立一个公共溢出区等 2.3 应用原则 一个不好的哈希函数，会造成很多冲突的情况，而解决冲突会浪费大量时间，因此应尽力避免冲突。理论上是可以设计出一个几乎完美，几乎没有冲突的函数的。然而这样函数设计很浪费时间而且编码一定很复杂因此，Hash函数还需要易于编码和实现。 同时设计一个优有时需要根据实际应用的要求对Hash表结构进行相应的改进 3 hash算法的常见应用场景 Hash算法应用比较广泛，例如快速查找，负载均衡、安全领域都有使用。Hash算法最常见的几种应用为：Hash表，快速查找算法；一致性Hash算法，缓存系统；SHA加密算法 3.1 著名的hash算法 3.1.1 MD4 MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。适用在32位字长处理器上用高速软件实现，基于 32 位操作数的位操作来实现 3.1.2 MD5 MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好 3.1.3 SHA-1及其他 SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法 3.2 Hash算法快速查找应用 Hash算法在快速查找中的应用很广泛，HashMap应该说是Java中最经典的一个应用范例。HashMap本身是用一个Hash表和一个链表来实现的。通过对key进行hash，再进行二次hash，将得到的结果同Hash表长度-1进行位与（）运算确定该key在Hash表中的位置（index） 3.3 Hash算法在信息安全方面的应用 3.3.1 文件校验 校验算法中较为常见的有奇偶校验和循环冗余检验，但是这两种算法没有检测数据被修改的能力，他们能够一定程度的纠正信道传输中的错误，但不能防止恶意破坏数据。但是散列算法中MD5的“数字指纹”特性，可以提供这种能力，它是一个被最广泛使用文件