我们喜欢使用数组进行数据的查找,就是因为数组是一种“随机存取”的数据结构,我们根据数组的起始地址和数组元素的下标值就可以直接计算出每一个数组元素的存储位置,所以它的查找时间是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 08:49:40
先简单介绍下哈希函数 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进 […] 继续阅读 >>


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