请输入您要查询的百科知识:

 

词条 哈希函数
释义

§ 哈希函数简介

哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。表示为:

Addr = H(key)

§ 两个主要问题

⑴构造一个合适的哈希函数

均匀性  H(key)的值均匀分布在哈希表中;

简单   以提高地址计算的速度

⑵冲突的处理

冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)= H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。

若已知哈希函数及冲突处理方法,哈希表的建立步骤如下:

Step1. 取出一个数据元素的关键字key,计算其则哈希表中的存储地址D=H(key)。若存储地址为D的存储空间还没有被占用,则将该数据元素存入;否则发生冲突,执行Step2。

Step2. 根据规定的冲突处理方法,计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用,则存入;否则继续执行Step2,直到找出一个存储空间没有被占用的存储地址为止。

随便看

 

百科全书收录594082条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/21 20:25:37