我们都知道,当我们要在一个集合中查找数据时,如果这个集合是顺序表且我们能确定要找的数据在顺序表中的位置的话,我们就能通过下标直接找到元素,这无非是我们要追求的最高效的查找策略!但是现实总是那么骨感,在大多数情况下,要在茫茫数据海洋中找某些关键信息,是不可能直接找到的。因为我们并不知道我们要找的数据与其所在位置之间是否存在某种关联。 所以我们在存储数据时,建立如同顺序表形式的可以按照下标进行查找的存储集合,然后我们可以认为建立要存的关键信息和其在集合中的下标之间的关系,这样我们在找想找的信息时,就可以确定信息在集合中的下标了,这样就可实现较为高效的查找了。而我们所说的这个集合就称为哈希表,建立的下标与信息的关系可以通过哈希函数(自定义合理的函数)来实现。 哈希表在查找,加密等很多方面都有广泛用途。 今天我用拉链法建立了简单的哈希表其结构如图所示: 源码 #include <iostream> #include<array> #include<memory> 继续阅读 >>


畅柯 18/12/26 23:43:15
详解哈希表(上)什么是哈希表不可逆性“碰撞”现象如何构造一个哈希算法:构造哈希函数的方法处理冲突的方法: Hi~ o( ̄▽ ̄)ブ 本篇博客分为上下两部分,上半部分主要讲解哈希表的基础知识,下半部分主要是功能代码实现。 φ(≧ω≦*)♪ 什么是哈希表 哈希,就是把任意长度的输入通过散列算法变换成固定长度的输出。 哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。 通俗理解的说,就是通过一个函数算法,把需要存储的东西经过这个算法转化成一个更简单的东西(关键码值),然后将这个关键码值作为所存储东西的地址,直接通过地址进行查找,简化了查找算法。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。 既然哈希表的核心,就是一个函数,那么,我们就可以通过研究函数的性质来研究哈希表。 ︿( ̄︶ ̄)︿ 不可逆性 首先来看一个简单的函数: f(key)=a 继续阅读 >>


赖鑫 18/12/21 01:00:04
注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量,n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位几乎需要对所有关键字进行重新映射。 总结:一致性哈希算法主要关注的是在分布式架构中,当节点数目发生变化的时候(增加/删除),怎样使再哈希的数据量最少。 一致性哈希的引出 在分布式系统中,节点的宕机、某个节点加入或者移出集群是常事。对于分布式存储而言,假设存储集群中有10台机器(node),如果采用传统Hash方式对数据分片(item)(即数据根据哈希函数映射到某台机器上存储),哈希函数应该是这样的:hash(item) % 10。根据上面的介绍,当node数发生变化(增加、移除)后,数据会被重新“打散”,导致大部分数据不能落到原 继续阅读 >>


董恒毅 18/06/26 21:06:58
我们喜欢使用数组进行数据的查找,就是因为数组是一种“随机存取”的数据结构,我们根据数组的起始地址和数组元素的下标值就可以直接计算出每一个数组元素的存储位置,所以它的查找时间是O(1),而与数组的个数无关。 我们在这个思想的基础上,可以联想到,如果有一种数据结构,让我们在进行关键字查找的时候,不用在类似于数组这样的数据结构上进行遍历与比较就可以直接通过某种关系就可以查找到该关键字在数组中的位置,使其时间复杂度从O(n)降到O(1),那就可以大大提高查找的效率。我们的前辈们基于这种想法发明了散列方法,也就是哈希或关键字地址计算方法。 基本思想 我们试图寻找一种关系,可以根据我们要存储的关键字(key)然后使用这种关系直接计算出它应该存储的位置(p),一旦建立起这种关系,那么我们在之后一旦需要查找此关键字的话,只需计算此对应关系所产生的值就可以直接得到关键字所在的地址,那么查找的时间复杂度也就降到了O(1),我们将刚才所说的转换为一种数学关系: p(位置)= H(key) 其中H就是对应关系,我们称之为哈希函数,p被成为散列地址。因此,哈希 继续阅读 >>


董恒毅 17/06/01 22:12:17
什么是哈希表 1.哈希表又称为散列表,是根据关键码值(Key value)而直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中的一个位置来访问记录,以加快查找速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表。  记录的存储位置=f(关键字) f是散列函数 这里的对应关系f称为散列函数,又称为哈希(Hash函数), 采用散列技术将记录存储在一块连续的存储空间,这块连续的存储空间称为散列表或哈希表(Hash table)。  2.哈希表hashtable(key,value)就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当做数组的下标,将value存储在以该数字为下标的数组空间里. 通过散列算法,变换成固定长度的输出,该输出就是散列值,这种是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值.简单的说就是一种将任意长度的消息压缩到某一固 继续阅读 >>


杨龙飞 17/02/10 21:07:12
一、哈希表 //哈希表 typedef struct dictht { //哈希表数组 dictEntry * […] 继续阅读 >>


常宫小戎 15/06/22 16:49:40
先简单介绍下哈希函数 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进 […] 继续阅读 >>


常宫小戎 14/03/05 21:25:33
1