上节内容提要(2) 顺序查找、 ASL=∑Pi*Ci=1∑(n-i+1)=+1 n 2 折半查找ASL≤log2n 分块查找(索引顺序查找】sgm+1+ n为表长,S为块长 树表查找(二叉排序树)、 上一页 ASL≈log2n 停止放映 哈希查找哈希函数常用的构造方法:数字分析法、平方 下一页 取中法、折叠法、除留余数法(求模取余法)、直接定址法 处理冲突有两种方法:开放地址法(线性探测再散列、二次探测再散 列)、链地址法 第3页下一页 上一页 停止放映 第 3 页 上节内容提要（2） – 顺序查找、 – 折半查找 ASL  – 分块查找（索引顺序查找） –n为表长，S为块长 – 树表查找（二叉排序树）、 ASL  – 哈希查找 哈希函数常用的构造方法：数字分析法、平方 取中法、折叠法、除留余数法（求模取余法）、直接定址法 ⚫ 处理冲突有两种方法：开放地址法（线性探测再散列、二次探测再散 列 ）、链地址法 i=1 n 1 2 n+1 n i=1 n ASL =  Pi*Ci =  (n-i+1) =