哈希表的设计与实现（线性探测再散列法解决冲突）？数据特征处理之特征哈希（Feature Hashing）

本文目录

• 哈希表的设计与实现(线性探测再散列法解决冲突）
• 数据特征处理之特征哈希（Feature Hashing）
• 简要回答哈希表这种数据结构应用在查找操作中的优势
• 哈希游戏公开吗听说最近很火
• 哈希表的实际应用

哈希表的设计与实现(线性探测再散列法解决冲突）

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
基本概念
* 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
常用的构造散列函数的方法
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数） 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p《=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
处理冲突的方法
1. 开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k《=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1. di=1,2,3,…, m-1，称线性探测再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k《=m/2)称二次探测再散列; 3. di=伪随机数序列，称伪随机探测再散列。 == 2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。 3. 链地址法(拉链法) 4. 建立一个公共溢出区
查找的性能分析
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。 查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素： 1. 散列函数是否均匀； 2. 处理冲突的方法； 3. 散列表的装填因子。 散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度 α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。 实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。 了解了hash基本定义，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢? 这里简单说一下： （1) MD4 MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。 （2) MD5 MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好 （3) SHA-1 及其他 SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。 那么这些Hash算法到底有什么用呢? Hash算法在信息安全方面的应用主要体现在以下的3个方面： （1) 文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。 MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。 （2) 数字签名 Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。 （3) 鉴权协议 如下的鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。 MD5、SHA1的破解 2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、H**AL－128、MD4和RIPEMD等四个著名密码算法的破译结果。 次年二月宣布破解SHA-1密码。
实际应用
以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢? 大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是点对点的意思的软件）， 它采用了"多源文件传输协议”(MFTP，the Multisource FileTransfer Protocol)。在协议中，定义了一系列传输、压缩和打包还有积分的标准，emule 对于每个文件都有md5-hash的算法设置，这使得该文件独一无二，并且在整个网络上都可以追踪得到。 什么是文件的hash值呢? MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。 当我们的文件放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个文件的hash值，他就是这个文件唯一的身份标志，它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候， 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后（如名称等）这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。 一般来讲我们要搜索一个文件，emule在得到了这个信息后，会向被添加的服务器发出请求，要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通，看看是不是可以从他那里下载所需的文件。 对于emule中文件的hash值是固定的，也是唯一的，它就相当于这个文件的信息摘要，无论这个文件在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行文件的下载上传过程中，emule都是通过这个值来确定文件。 那么什么是userhash呢? 道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是唯一的，它是我们在emule世界里面的标志，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎么改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是文件信息，而是我们每个人的信息。 那么什么是hash文件呢? 我们经常在emule日志里面看到，emule正在hash文件，这里就是利用了hash算法的文件校验性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常复杂的过程，目前在ftp,bt等软件里面都是用的这个基本原理，emule里面是采用文件分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met文件，直到整个任务完成，这个时候part文件进行重新命名，然后使用move命令，把它传送到incoming文件里面，然后met文件自动删除，所以我们有的时候会遇到hash文件失败，就是指的是met里面的信息出了错误不能够和part文件匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有文件信息，还有一种情况就是上一次你非法关机，那么这个时候就是要进行排错校验了。 关于hash的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的操作系统密钥原理，里面都有它的身影，特别对于那些研究信息安全有兴趣的朋友，这更是一个打开信息世界的钥匙，他在hack世界里面也是一个研究的焦点。 一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。 哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。 对于动态查找表而言，1) 表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key)作为关键字为key的录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数) 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。 现实中哈希函数是需要构造的，并且构造的好才能使用的好。 用途：加密，解决冲突问题。。。。 用途很广，比特精灵中就使用了哈希函数，你可 以自己看看。 具体可以学习一下数据结构和算法的书。
字符串哈希函数
（著名的ELFhash算法） int ELFhash(char *key) return h%MOD; }

数据特征处理之特征哈希（Feature Hashing）

***隐藏网址***

一、特征哈希（Feature Hashing/Hashing Trick）简介

大多数机器学习算法的输入要求都是实数矩阵，将原始数据转换成实数矩阵就是所谓的特征工程（ Feature Engineering ），而特征哈希（feature hashing，也称哈希技巧，hashing trick）就是一种特征工程技术。它的目标就是将一个数据点转换成一个向量。
我们先看一下对分类数据（categorical data）和文本数据（text data）进行特征工程处理的一般方法。

分类变量（category variable）就是一组有有限值（finite number of values）的变量。如身份证号、广告类别等。最常见的对分类变量的处理是使用独热模型（one-hot encoding）：创建NN个二元变量，其中NN是该分类变量所有可能的取值数量。

而对于文本数据的特征处理，最简单的方法是词袋模型（bag-of-word model）：创建NN个二元变量，其中N是词汇的数量（即不同单词的数量）。对于每个文档来说，创建一个NN维向量，文档中包含的某个词汇的数量即是这个向量中词汇对应的索引的值。

可以看到，这两种方法非常类似，都创建了高维稀疏的矩阵。而特征哈希是以哈希表（hash table）的方式来实现这两种转换方法。下面简要介绍一下哈希表。

二、哈希表（Hash Table）

哈希表是一种数据结构，它是根据键值（key）来直接访问内存存储位置的数据结构。每个哈希表都是用一个哈希函数（也叫散列函数，hash function）来实现键-值（key-value）对的映射。这种函数可以将任何一种数据或者消息压缩成摘要（即散列值），使得其数据量变小且格式固定。理想的散列函数会把不同的键散列到不同的块中，但是大多数哈希表都存在哈希碰撞（hashing collision）的可能，即不同的键可能会被映射到相同的值上（后面会解释，这一点不影响机器学习模型的效果）。

在运用哈希表的时候，通常我们需要定义输出的范围，例如假设我们希望将输出范围定义在0-N之间，那么我们就可以使用一个函数，可以将输入数据散列到之间即可。假设我们创建如下的哈希函数，可以将单词映射成五种类别，即0-4索引：
哈希表有如下特性：

相同的输入可能有相同的输出（一般情况下比例不高）

不同的输出一定对应不同的输入

正向计算很简单，反向计算很困难

根据输入查找输出效率很高

三、简单的案例

我们以垃圾邮件检测（spam）为例（这属于文本分类的一个应用），假设有如下两封邮件，第一封邮件是垃圾邮件，第二封邮件不是垃圾邮件：

i make ten thousand dollars per week just surfing the web! (spam)

are you **** for a meeting early next week? (not spam)

make: 1

ten: 2

thousand: 3

dollars: 4

per: 5

week: 6

just: 7

surfing: 8

the: 9

web: 10

are: 11

you: 12

****: 13

for: 14

a: 15

meeting: 16

early: 17

next: 18

总共19个词汇量，我们创建一个19维的向量，得到如下结果：

i make ten thousand dollars per week just surfing the web! (spam)

-》

are you **** for a meeting early next week? (not spam)

-》

接下来我们就可以使用分类模型来训练，预测标记垃圾邮件，并过滤垃圾邮件了。但是，有个很简单的方法来规避这种审查，如某封邮件如下：

ii mayke are you th0usands of **** for a $$$s surf1ing teh webz meeting early next week

-》

这封邮件里面包含了某些用户自己创造的单词，这些单词在我们的词汇表中没有，但是实际上我们依然可以识别出来，它是一封垃圾邮件。但是，用上述词袋模型转换的结果却是和前面第二封邮件类似的向量。显然，分类模型会把它归为正常邮件中。因此，上述特征工程显然不能满足要求。

除此之外，使用上述特征工程方法还有一个巨大的问题就是通常会创建非常高维的稀疏向量。假设我们有100万邮件作为训练集，每封邮件平均只有几十个单词，但词汇表可能有数十万，这样创建出来的输入数据是一个高维稀疏矩阵，这对很多机器学习算法来说并不是友好的输入。

如果使用上述的哈希特征方法，就可以将所有的原始数据转换成指定范围内的散列值。这样做有几个好处：

即便对于不在词汇表中的单词，我们依然可以计算出一个散列值，因此不容易被规避，也不需要事先准备词汇表，新特征的转换对输入特征的长度不影响（因为事先已经定义好了散列范围）

只需要散列新来的数据，并不需要重新对所有数据进行哈希处理，所以支持在线学习

经过哈希特征工程之后，原来非常稀疏的向量可能会变得不那么稀疏

尽管有散列冲突，但是研究和实践表明，这种影响很小。

哈希特征工程的比较大的缺点是缺乏可解释性，因为特征被处理成无法解释的散列值了。尽管如此，这个技巧才很多时候非常有用。

特征哈希的使用技巧

使用哈希特征的时候需要选择散列的范围，这个并没有统一的标准。较小的散列范围会导致较多的冲突，影响准确性，较大的范围会占用较高的内存和花费较多的训练时间。因此，在实际情况中，要根据你的目标选择，如果不考虑训练时间的话，可以考虑使用较大范围的散列结果。

简要回答哈希表这种数据结构应用在查找操作中的优势

优势：

从时间和空间的角度分析：

1. 时间高效：利用哈希可使插入、查找、删除、修改、替换操作的时间复杂度达到O(1)，这是其他查找方式无法达到的（比如树形查找O(logn)、二分查找O(logn)、顺序查找O(n)等）。即使出现碰撞，整体理论值也可以接近O(1)。

2. 空间可接受：哈希的比较合适的空间消耗以O(2n)最佳，对于其他同类算法（主要是树形查找方式），要分为两类。第一种是以叶子存放有效值的树(如b+树、线段树)，其空间消耗可认为是O(4n)；第二种是所有节点均存放有效值，空间消耗可认为O(n)。

哈希游戏公开吗听说最近很火

哈希游戏目前作为游戏市场上大火游戏，很多人都会关心它的未来趋势如何。首先哈希游戏采用了密码学算法，其中的哈希算法为游戏带来了安全的系统环境，从而更高效的兼顾了玩家的利益。
哈希是一种加密算法，可以将任意长度的输入值映射成为一个长度固定的值，称为哈希值、散列值（Hash Value）、杂凑值或者消息摘要。它是一种单向密码体制，指一个从明文到密文的过程中不可逆映射，只有加密过程，没有解密过程。
哈希表是一种组合的数据结构， 也 是一种牺牲空间去换取时间的数据结构 ，属于 是时间和空间之间的平衡 ， 通常的实现方式是数组加链表 ， 哈希表的核心是 哈希函数 ，哈希函数的设计可以完美的解决哈希冲突这样关键的问题。
哈希函数是一个公开函数，指的是 哈希表中元素的关键键值映射为元素存储位置的函数 ，该函数是 一个接受输入值的函数 ，也就是说 输入创建了一个输入值的确定值 那么， 对于任何 x 输入值，每当运行散列函数时，都会收到相同的 y 输出值。这样，每个输入都有一个确定的输出。 并且是不可逆的，对于哈希函数而言，只要是输入值不变，那么输出值是不变的是唯一的。
散列表 是根据关键 键 而直接进行访问的 数据结构， 也就是说，它通过把关键 键 值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
常用的构造哈希算法---哈希函数的方法
【数字分析法；随机数法；直接寻址法；除留余数法；折叠法；平方取中法】
1. 数字分析法：就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址
2. 随机数法：一般是用于关键字长度不同的方面，选择一随机函数，取关键字的随机值作为散列地址。
3. 直接寻址法：指取关键字或者取关键字的某个线性函数值为散列地址。
4. 除留余数法：不仅可以对关键字直接取模，也可以在折叠、平方取中等方面运算之后取模。
5. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不相同，然后取这几部分的叠加再去除进位作为散列地址。
6. 平方取中法：取关键字平方后的中间几位作为散列地址。

哈希表的实际应用

以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢?
大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是对等连接的软件）， 它采用了多源文件传输协议”（MFTP，the Multisource FileTransfer Protocol）。在协议中，定义了一系列传输、压缩和打包还有积分的标准，emule 对于每个文件都有md5-hash的算法设置，这使得该文件独一无二，并且在整个网络上都可以追踪得到。
什么是文件的hash值呢?
MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。
当我们的文件放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个文件的hash值，他就是这个文件唯一的身份标志，它包含了这个文件的基本信息，然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候， 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后（如名称等）这个值就更显得重要。而且服务器还提供了，这个文件当前所在的用户的地址，端口等信息，这样emule就知道到哪里去下载了。
一般来讲我们要搜索一个文件，emule在得到了这个信息后，会向被添加的服务器发出请求，要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通，看看是不是可以从他那里下载所需的文件。
对于emule中文件的hash值是固定的，也是唯一的，它就相当于这个文件的信息摘要，无论这个文件在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行文件的下载上传过程中，emule都是通过这个值来确定文件。
那么什么是userhash呢?
道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是唯一的，它是我们在emule世界里面的标志，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎么改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是文件信息，而是我们每个人的信息。
那么什么是hash文件呢?
我们经常在emule日志里面看到，emule正在hash文件，这里就是利用了hash算法的文件校验性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常复杂的过程，在ftp,bt等软件里面都是用的这个基本原理，emule里面是采用文件分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met文件，直到整个任务完成，这个时候part文件进行重新命名，然后使用move命令，把它传送到incoming文件里面，然后met文件自动删除，所以我们有的时候会遇到hash文件失败，就是指的是met里面的信息出了错误不能够和part文件匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有文件信息，还有一种情况就是上一次你非法关机，那么这个时候就是要进行排错校验了。
关于hash的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的操作系统密钥原理，里面都有它的身影，特别对于那些研究信息安全有兴趣的朋友，这更是一个打开信息世界的钥匙，他在hack世界里面也是一个研究的焦点。
一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K）。若结构中存在关键字和K相等的记录，则必定在f(K）的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
哈希表不可避免冲突（collision）现象：对不同的关键字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2）。具有相同函数值的关键字对该哈希函数来说称为同义词（synonym）。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key）和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集（区间）上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。
对于动态查找表而言，1) 表长不确定；2）在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key）作为关键字为key的录在表中的位置，通常称这个函数f(key）为哈希函数。（注意：这个函数并不一定是数学函数）
哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。
现实中哈希函数是需要构造的，并且构造的好才能使用的好。
用途：加密，解决冲突问题。
用途很广，比特精灵中就使用了哈希函数，你可以自己看看。
具体可以学习一下数据结构和算法的书。