( ! ) Notice: Undefined index: mobile in /var/www/html/head.php on line 16
Call Stack
#TimeMemoryFunctionLocation
10.0001230192{main}( ).../view.php:0
20.0001230936include( '/var/www/html/head.php' ).../view.php:2
30.0010250296isMobile( ).../head.php:30
数学思维训练网 - 小学计算思维课程(17)-哈希搜索

小学计算思维课程(17)-哈希搜索

小学计算思维课程(17)-哈希搜索

本书共26课,如果您有好的建议,请联系作者:浙江省新昌县城西小学 唐明 147885198@qq.com


第十七课:哈希搜索

上节课我们介绍的“二分搜索”算法,它的速度已经够快了,那么有没有更快的办法呢?今天我们要学的“哈希搜索”就是其中的佼佼者,在很多时候,只要你输入搜索关键字,它可以直接找到目标信息,真是一种神奇的算法。

在“哈希搜索”中,最重要的是明白“哈希”的意思,哈希是英文“hash”的中文音译,它的基本做法是把所有的搜索关键字用一定的计算方法得到它的hash数字,使用这个数字就可以立刻找到这个关键词(在计算机科学中,这个过程称为“映射”)。

所以,哈希搜索中的“哈希算法”就是最重要的部份,一个简单的哈希算法是将战舰代码的每个数位相加,取其总和的末位数字。这个数字决定了该把这艘战舰放置在哪一类中,因此一共有10类,比如编号为2345的战舰,将代码各位数字相加为2+3+4+5=14,取末位为4,所以这艘战舰将被归类到数字4的类中。

准备:

1.25张四位数随机数卡片代表战舰。

2.10个类别的数字标签(从0-9)放在桌子上。

3.将所有战舰代码进行哈希计算,并放在对应的标签下,注意要将所有战舰背面朝上。

4.不要忘记选出你的秘密战舰,并告诉你的搭档。

活动:

和你的搭档再玩一次战舰游戏。这次,锁定对手的秘密战舰的速度应该很快了吧,比如你的目标是战舰5678,那么5+6+7+8=26,只要到分类为6的标签寻找目标即可。

问题:

1.这次你一共用了多少次找到了对手的战舰?

2.用这种方法,大家的最少用了几次?你觉得最好的成绩只需要几次?

3.大家最多用了几次找到,你觉得最差的成绩可能需要几次?

4.如果秘密战舰不在队列中会发生什么情况?一共需要几次才能发现?

5.你认为一般需要几次才能找到秘密战舰?

6.如果你想让你的秘密战舰不容易被发现,你需要把它藏在哪一类里面?

7.如果你希望尽快找到对手的秘密战舰,你希望它被归在哪一类里面呢?

上面的游戏中,我们的“哈希函数”只能产生10个类别,所以有很多战舰被归到同一类中(计算机科学称为“哈希碰撞”)。如果能设计一种“哈希函数”,让一艘战舰对应一个类别,那么这时的哈希搜索就是最快的搜索算法,因为它可以根据“哈希值”立即锁定关键词储存的位置。计算机科学家已经设计了几十种哈希算法,期待我们的同学能设计一种简单易用且“哈希碰撞”最少的算法。

最后,回忆一下我们学过的三种搜索方法各自的优点和缺点是什么?(可以从搜索速度、数据要求等方面讲述)