谁能帮我解释一下“哈希表”的详细含义?谢谢了
发布网友
发布时间：2022-05-06 14:39
共4个回答
懂视网
时间：2022-04-22 16:35
散列表
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
我们从上图开始分析
有一个集合U，里面分别是1000，10，152，9733，1555，997，1168
右侧是一个10个插槽的列表（散列表），我们需要把集合U中的整数存放到这个列表中
怎么存放，分别存在哪个槽里？这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数，我们对应这图来看
1000%10=0，10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中
152%10=2那么就存放到2的槽中
9733%10=3 存放在编号为3的槽中
通过上面简单的例子，应该会有一下几点一个大致的理解
集合U，就是可能会出现在散列表中的键
散列函数，就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中，如例子中的取余数
散列表，存放着通过计算后的键
那么我们在接着看一般我们会怎么去取值呢？
比如我们存储一个key为1000，value为'张三' ---> {key:1000,value:'张三'}
从我们上述的解释，它是不是应该存放在1000%10的这个插槽里。
当我们通过key想要找到value张三，是不是到key%10这个插槽里找就可以了呢？到了这里你可以停下来思考一下。
散列的一些术语（可以简单的看一下）
散列表中所有可能出现的键称作全集U
用M表示槽的数量
给定一个键，由散列函数计算它应该出现在哪个槽中，上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。
1000和10都被存到了编号0的这个槽中，这种情况称之为碰撞。
看到这里不知道你是否大致理解了散列函数是什么了没。通过例子，再通过你的思考，你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了，那么我估计你应该是懂了。
常用的散列函数
处理整数 h=>k%M （也就是我们上面所举的例子）
处理字符串：
function h_str(str,M){
return [...str].reduce((hash,c)=>{
hash = (31*hash + c.charCodeAt(0)) % M
},0)
}hash算法不是这里的重点，我也没有很深入的去研究，这里主要还是去理解散列表是个怎样的数据结构，它有哪些优点，它具体做了怎样一件事。
而hash函数它只是通过某种算法把key映射到列表中。
构建散列表
通过上面的解释，我们这里做一个简单的散列表
散列表的组成
M个槽
有个hash函数
有一个add方法去把键值添加到散列表中
有一个delete方法去做删除
有一个search方法，根据key去找到对应的值
初始化
- 初始化散列表有多少个槽
- 用一个数组来创建M个槽
class HashTable {
constructor(num=1000){
this.M = num;
this.slots = new Array(num);
}
}散列函数
处理字符串的散列函数，这里使用字符串是因为，数值也可以传换成字符串比较通用一些
先将传递过来的key值转为字符串，为了能够严谨一些
将字符串转换为数组, 例如'abc' => [...'abc'] => ['a','b','c']
分别对每个字符的charCodeAt进行计算，取M余数是为了刚好对应插槽的数量，你总共就10个槽,你的数值%10 肯定会落到 0-9的槽里
h(str){
str = str + '';
return [...str].reduce((hash,c)=>{
hash = (331 * hash + c.charCodeAt()) % this.M;
return hash;
},0)
}添加
调用hash函数得到对应的存储地址(就是我们之间类比的槽)
因为一个槽中可能会存多个值，所以需要用一个二维数组去表示，比如我们计算得来的槽的编号是0，也就是slot[0]，那么我们应该往slot[0] [0]里存，后面进来的同样是编号为0的槽的话就接着往slot[0] [1]里存
add(key,value) {
const h = this.h(key);
// 判断这个槽是否是一个二维数组, 不是则创建二维数组
if(!this.slots[h]){
this.slots[h] = [];
}
// 将值添加到对应的槽中
this.slots[h].push(value);
}删除
通过hash算法,找到所在的槽
通过过滤来删除
delete(key){
const h = this.h(key);
this.slots[h] = this.slots[h].filter(item=>item.key!==key);
}查找
通过hash算法找到对应的槽
用find函数去找同一个key的值
返回对应的值
search(key){
const h = this.h(key);
const list = this.slots[h];
const data = list.find(x=> x.key === key);
return data ? data.value : null;
}总结
讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。
补充一个小知识点
v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。
热心网友
时间：2022-04-22 13:43
[编辑本段]基本概念
* 若结构中存在关键字和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、HAVAL－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) { unsigned long h=0; while(*key) { h=(h<<4)+*key++; unsigned long g=h&0Xf0000000L; if(g) h^=g>>24; h&=~g; } return h%MOD; }
热心网友
时间：2022-04-22 15:01
热心网友
时间：2022-04-22 16:35
参考资料：http://ke.baidu.com/view/329976.htm?fr=ala0_1
