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