第9章节查找4-哈希表.pptVIP

第9章 查找 （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 5 4 8 1 9 7 6 2 12 11 10 3 9.4 哈希查找表 例2 ： 若干术语 冲突现象举例： 在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。 二、哈希函数的构造方法 1、直接定址法 2、除留余数法 4、数字分析法 5、平方取中法 7、随机数法 三、冲突处理方法 1、开放定址法（开地址法） 例： 讨论： 2. 二次探测法 2、链地址法(拉链法） 3、再哈希法（双哈希函数法） 四、哈希表的查找及分析 讨论： 作业 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）。造出Hash表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 * * 嘉应学院 数学系 数据结构讲义 - 哈希表 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5 4 8 1 9 7 6 2 7 2 8 5 1 9 6 4 5 2 8 1 9 7 6 4 12 11 5 2 8 1 11 7 6 4 12 9 10 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5 2 8 1 11 7 6 4 12 9 10 （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） 5 4 8 1 9 7 6 2 12 11 10 3 6 7 8 11 5 2 1 4 12 9 10 3 6 7 8 11 5 2 1 4 12 9 10 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记录。 哈希表 它既是一种查找方法，又是一种存贮方法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 哈希表：即散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元； 将2001011810202的所有信息存入V[02]单元； …… 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]！ 一、哈希表的概念 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。 （注：H（k）＝k称为散列函数） 解：根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入