平均查找长度的计算方法如下：

顺序查找，从表的一端开始，顺序扫描线性表，依次将扫描到的节点关键字和给定值k相比较。等概率条件下平均查找长度：ASL = (n++2+1)/n= (n+1)/2。

二分法查找，前提是线性表是有序表。假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

在等概率条件下平均查找长度：ASL =（1/n） ( j 2^(j-1) )(j是从1到h)，ASL = og2(n+1)-1。

原因：用二叉树来描述，树的高度d与节点树的关系为：n=(1+2+4+ 2^(d-1))=2^d - 1；所以d = log2(n+1)，每一层只需要比较一次，所以最多需要比较log2(n+1)次。

分块查找，又称索引顺序查找，由分块有序（每一块中的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即分块有序。）的索引表和线性表组成。例如把r1n分为 b 块，则前 b-1 块节点数为 s = n/b，最后一块允许小于或等于s。索引表是一个递增有序表。

平均查找长度分为两部分，索引表的查找+块内的查找。如果以二分查找来确定块，则 ASL = log2(b+1)-1 + (s+1)/2。如果以顺序查找来确定块，则 ASL = (b+1)/2 + (s+1)/2。如果以哈希查找来确定块，则ASL=1 + (s+1)/2。

链表用在数据量大的时候，一般以指针实现，二叉树是一种数据结构，能用的地方很多，常用的有：排序、dfs、bfs等

哈希表是一种用于快速查找的，它是规定一个关键值，已达到1次或几次就能查找到要查找的元素

哈希就是Hash。

一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入-又叫做预映射pre-image。通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

扩展资料:

哈希值是由哈希函数从一个给定的数据计算出来的。哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。

这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。