哈希表基本原理详解

短命女 2022-03-19 13:21 231阅读 0赞

这篇文章是参考视频

# 思胜 ASP.Net C＃培训-7-3-下午-1-哈希表基本原理.wmv #

http://v.youku.com/v\_show/id\_XMjYwNjEwMDg0.html

所做的学习笔记..

===================================================================

在实际上的程序实现中, 有1个经典原理, 叫做**数量决定质量.**

**    ** 这个原理是什么意思呢,  举个例子, 当我们查询从一些数量比较小的数据里查询时, 算法和代码的好坏其实不明显. 但是当数据数量变得巨大,甚至从海量数据里查询时, 算法和代码的质量差别就十分明显了.

下面讲解几种查询算法.

**1.线性检索**

**1.1 定义**

线性检索就是按照数据的顺序逐个来比教,直到找到符合条件的数据.

**1.2 时间复杂度  O(n)**

**          ** 假如我们要从n个数据中找出1个随机决定的数据. 使用线性检索法来在n个数据中从头到尾开始比较.

最好的情况下, 第1个就是要找的数据, 这样的话只需查找1次.

最坏的情况下, 最后1个才是要找的数据, 这样的话需要查找n次.

当执行很多次查询时, 平均每次查询需要查找n/2次啦(其实应该不止n/2, 因为如果要找的数据不在这个数据集这中, 也会查找n次),  而时间复杂度是关于n的表达式, 这个表达式跟执行的时间成正比.

这个求时间复杂度的方法类似于求导数, 也就是所有常熟都被忽略, 所以线性检索的时间复杂度是O(n)

这个时间复杂度说大不大, 但也绝不算小啦.

**1.3 优点**

逻辑易懂, 实验方法简单. 当数据量不大的时候十分使用.

例如我们要做1个同学程序, 对于1个正常人来讲, 同学录里名单的数量不会很多, 通常200个到顶了, 那么在1个用户里的名单信息里查找其中1个名单, 使用线性检索是可行的.

**1.4** **缺点**

**          ** 对查找海量数据相当无力, 例如, 移动通讯商的客户信息, 通常几千万条数据, 如果要查找某个号码的用户信息, 使用线性检索去逐个逐个比较是很不明智的.

**     2.定点检索**

首先说明一下, 这的定点检索 跟 上面的线性检索并不是平行的, 它们是从不同角度去看得出的不同名词. 也就说, 数据查询中分定点检索和非定点检索, 而在定点检索中, 我们可以用线性检索这个方法...

**2.1 定义**

**         ** 根据数据集的**唯一key**为条件去查找**具体一条数据**的查找就是定点检索.

就如上面1.4 提到的根据某个手机号码去查找对应的用户信息, 这就是1个定点检索.

定点检索有两个特征.

第一就是以唯一标识为条件, 例如要查找开户时间为2012/01/01 的手机号码, 这个是以开户时间为条件,这个就不是线性检索.

第二个特征是查找某一个数据的检索, 如过查找的结果是1个列表, 例如要查找用户号码是136开头的电话号码的用户列表, 这个就不是定点检索了.

对于非定点检索, 例如要找出符合条件的一段数据, 一般而言只能用线性检索来找(逐个比较), 另1个方法就是关系数据表里的索引技术. 这个是后话了.

**     3. 针对海量已排序数据的定点检索, 可以尝试折半查找法(二分法).**

**      3.1 折半查找法的定义和原理: **

可以参考这里: http://nvd11.blog.163.com/blog/static/200018312201311232528276/

**        3.2 折半查找法的时间复杂度是 O(log2^n)**

**          ** 当然这里有个前提就是数据已经排序, 因为排序也是1个复杂耗时间的行为.

**3.3 优点**

优点当然是优秀的时间复杂度了,   O(log2~n) 与 线性的O(n)的区别?

假如要查找从1堆海量**已经排序**数据中找1条数据, 数据数量有n= 1267650600228229401496703205376 (2的100次方, 现实里的数据库基本不可能有这么多数据啦), 用线性查找法的话可能找到天荒地老都找不到(平均要查找n/2次),  而对于O(log2^n) 来讲, 只需查找100次!

**  3.4 缺点**

缺点也很明显啦, 当然就是需要数据已经排序啊.

假如数据未排序, 那么则需要先将数据排序.

通用的排序法的时间复杂度,例如冒泡法\--> O(n^2) 传说中的几何级数增长...

快速排序法的时间复杂度, 例如快排, 二叉树,希尔  -\-> 大概是O(n\*log^2n)

所以对于离散未排序的数据,使用排序\+折半查找法的话,时间复杂度是O(n\*log2^n)+O(log2^n), 比线性检索还更恶劣啊.

**4. 针对海量排序无关数据的定点检索, 推荐使用哈希表(HashTable).**

什么是排序无关呢, 就是你爱排序就排序, 实际上也可以当做无必排序啦...

哈希表在.net 里还被改进为字典表(Dictionary), 在java里被改进为哈希图(Hashmap), 但它们的基本原理是一样的.

**4.1 时间复杂度 O(1)**

**            ** 没写错, 时间复杂度就是O(1), 也就是说哈希表的查找所需时间相当稳定, 不会随数据量的增加发生明显变化, 逆天了.

**4.2 实现哈希表的先决条件** **       **

**            4.2.1 直接寻址**

直接寻址的意思就意思是,  只要知道任何有效的地址, 就可以直接去访问对应地址的内容.

举个例子, 假如我知道你家的门牌号是12楼 02房, 那么我就可以直接跳到12楼 02房间去找你... 而不用从1楼跑到12楼.. 很逆天的技术啊~

**4.2.2 地址(Address)与哈希码的映射**

**                 ** 这个地址(内存)归属于操作系统, 是操作系统可以认可数据空间的唯一标识. 地址形式长度不超过当前操作系统位数的的倍数.

解释一下, 这个地址一般就是指内存的地址, 操作系统位数指的的是32位/64位系统的32或64, 如果系统是32位的, 那么这个地址长度就不能超过32位, 也就是这个地址必须在  0 ~ (2^31 -1) 之间.  (具体参考:http://nvd11.blog.163.com/blog/static/200018312201312484316245/)

还有哈希码归属于framework, 属于受控内存范围, 将整个托管内存进行编号(形式也不操过当前操作系统系统的位数).  在受控的托管内存内, 任何1个哈希码与唯一的存储空间相对应, 同时其也必精确地对应到操作系统地址,操作系统地址与托管内存的哈希码有等价的对应关系.   Framwork的CLR(Common Language Runtime) 内部可以保存和维护完整的映射表, 并能快速地转化.

**4.2.3 哈希函数的出现**

**                ** 哈希函数并没有唯一的版本, 绝大部分情况下, 其设计目标就是针对指定的数据内容计算其对应的哈希码,  计算要求必须保证结果**必须在某个****指定范围之内**且结果与制定的数据具有等价映射性.**  根据其内部的自定义的评判依据, 不同的数据(key）必须计算出不同的哈系码，而相同的数据(key)必须用哈希函数算出相同的哈希码, 与计算时间与次数无关(也就是说今天算的和昨天算的结果必须相同). ** **不同的数据必须算出不同的哈希码。**造成任何类型的数据都可以算出其等价的哈希码。在相同环境下，计算用的哈希函数必须为同样的版本（也就是说不能有两个不同的哈希函数）。

**             4.2.4 表(table), 桶(bucket) 及键值对(key-vlaue pair) 的出现：**

**             表：**

**                 ** 某程序实例(哈希表/字典表/哈希图实例），想CLR申请到一块足够大小的存储空间，且此空间还可以自动扩容。整个空间被称为表(table). 也就是说表是内存里的1个空间。

**桶：**

预料到数据会有一定的数量，表往往会申请到其预计容量的2-10倍; 为了提升空间的使用效率。往往在内部自动对表空间进行进一步的划分，划分出的单元被成为桶(bucket)

**键值对：**

在任何1个桶的内部，所有的数据空间可以被划分，每1个空间都必须可以存储下来两份制定数据，其中第一份数据表达了本单元的唯一标识(key)。 第二份数据表达了希望进行保存的全部数据实例(value).  这两份数据被统称为键值对。在桶内，所有的数据都以键值对的形式存储。**每1个存储键值对的****存储单元都必须被唯一编号****，且编号与哈希码必须建立等价的映射关系**。

**4.3 先决条件满足后， 开始执行存储及检索**

存储时，首先必须针对存储的数据进行合理的分析， 分析其唯一标识， 作为j键(key)， 且此key可以为任何的数据类型。 而整个存储作为值(value).     接着，将key 送入哈希函数（作为参数），计算得到唯一的哈希码。 通过唯一哈希码换算得到桶内的唯一编号，进而得到操作系统的唯一地址（内存地址），进而可以直接将key 和 value 存入对应的地址空间。完成存入。

由于哈希函数计算得到的哈希码有明显的散列存储的特征（但必须在1个特定范围内，简单来讲必须在申请到的内存空间（表）内），所以会导致在表内的实际存储位置与存放的顺序完全无关， 呈现出散列存储的特点。

检索时，首先必须通过各种方式获取待检索数据的唯一标识键(key), 将键送入哈希函数，计算得到的哈希码， 其哈希码必然与存储时的哈希码等同， 进而得到相同的桶内编号。进而得到相同的操作系统地址， 进而发行**直接寻址**。从对应的键值对中取出其中的键， 与手头的键进行比对， 如果比对成功，则获取本键值对的值，并对外返回，以表达检索结果。完成检索。

**4.4 总结**

**               ** 整个过程中，存入的理论计算次数为一次， 检索时的理论计算次数为1次，所以此种方案中。其整个过程的时间复杂度就是O(1)了

其实之所以会快速， 实际上就是把数据放入内存， 然后利用内存的直接寻址技术...

**               **

**    **