注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(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