数据结构课件-11-4散列查找.pptxVIP

;;;11.4.1散列函数;取给定学号的后三位，不需要经过比较，便可直接从查找表中找到给定学生的记录。;一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以H(key)作为关键字为key的记录在表中的位置，通常称这个函数h(key)为散列函数。;11.4散列查找;11.4散列查找;3)很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。;11.4散列查找;11.4散列查找;散列函数;散列函数;;;;11.4散列查找;;;;;;;11.4散列查找;11.4.2冲突处理;11.4散列函数;;对增量di有三种取法：;;2）再散列法

;;假设某散列函数的值域[0,m-1]，

向量HashTable[0,m-1]为基本表，每个分量存放一个记录，另设一个向量OverTable[0,v]为溢出表。将与基本表中的关键字发生冲突的所有记录都填入溢出表中。

如一组关键字序列为{19，14，23，01，68，20，84，27，55，11，10，79}，散列函数为H（key）=keymod13，采用公共溢出区法得到的结果为：;11.4.3散列表查找算法;;;;例题:关键字集合

{19,01,23,14,55,68,11,82,36};例题:关键字集合

{19,01,23,14,55,68,11,82,36};例题:关键字集合

{19,01,23,14,55,68,11,82,36};19;19;ASL(失败)=？;19;19;19;将所有散列地址相同的记录都链接在同一链表中。;;11.4.4查找性能分析;|查找性能分析;;总结;11.4.5分布式散列表;11.4.6作业;