哈希法 哈希法又名散列法,因其英文单词Hash而得名,是一种完全不同的查找方法 前面我们所介绍的三种查找方法的共同特点在于:通过对关键字的一系 列比较,逐步缩小査找范围,直到确定结点的存储位置或确定査找失败 而哈希法则希望不经过任何比较,一次存取就能得到所査元素,因此必 须在记录的存储位置和它的关键字之间建立一个确定的对应关系,使得 每个关键字和结构中一个唯一的存储位置相对应,这样查找时只需对结 点的关键字进行某种运算就能确定结点在表中的位置。因此哈希法的平 均比较次数和表中所含结点的个数无关。 打个比方让我们更清楚的认识哈希法的不同。假定某教室有35个座位,如果 不加限定让学生任意就座,则要找某个学生时就要将待找学生与当前座 位上的学生二一做比较,这就是我们前面所介绍的查找方法的大致思路( 而哈希法则要限定学生所坐的位置,比如可规定学生座位的编号应与其 学号的末两位相同,则学号为993605的学生应坐编号为5的座位。这样我 们要找某个学生时只需根据其学号的末两位到相应座位上去找即可 必 比较了。在这个例子里,学生好比记录学号则为关键字对 键字进行的操作则是取其末两位,用以确定记录的返回本章首页 下一页 上一页 哈希法 哈希法又名散列法,因其英文单词Hash而得名,是一种完全不同的查找方法。 前面我们所介绍的三种查找方法的共同特点在于：通过对关键字的一系 列比较，逐步缩小查找范围，直到确定结点的存储位置或确定查找失败。 而哈希法则希望不经过任何比较，一次存取就能得到所查元素，因此必 须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得 每个关键字和结构中一个唯一的存储位置相对应，这样查找时只需对结 点的关键字进行某种运算就能确定结点在表中的位置。因此哈希法的平 均比较次数和表中所含结点的个数无关。 打个比方让我们更清楚的认识哈希法的不同。假定某教室有35个座位，如果 不加限定让学生任意就座，则要找某个学生时就要将待找学生与当前座 位上的学生一一做比较，这就是我们前面所介绍的查找方法的大致思路。 而哈希法则要限定学生所坐的位置，比如可规定学生座位的编号应与其 学号的末两位相同，则学号为993605的学生应坐编号为5的座位。这样我 们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不 必一一比较了。在这个例子里，学生好比记录，学号则为关键字，对关 键字进行的操作则是取其末两位，用以确定记录的位置