词条 | 哈希函数 |
释义 | § 哈希函数简介 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。表示为: Addr = H(key) § 两个主要问题 ⑴构造一个合适的哈希函数 均匀性 H(key)的值均匀分布在哈希表中; 简单 以提高地址计算的速度 ⑵冲突的处理 冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)= H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。 若已知哈希函数及冲突处理方法,哈希表的建立步骤如下: Step1. 取出一个数据元素的关键字key,计算其则哈希表中的存储地址D=H(key)。若存储地址为D的存储空间还没有被占用,则将该数据元素存入;否则发生冲突,执行Step2。 Step2. 根据规定的冲突处理方法,计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用,则存入;否则继续执行Step2,直到找出一个存储空间没有被占用的存储地址为止。 |
随便看 |
百科全书收录594082条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。