查找表是由同一类型的数据构成的集合，集合间存在着松散的关系，因此查找表是一种应用灵便得结构。
1.关键字：
主关键字：可唯一的识别一个记录的关键字（学号）
次关键字：可识别若干个记录的关键字（姓名：重名）
查找——根据给定的值，在查找表中的值等于给定的值
2.对查找表进行的操作：
可以理解为：增删改查
查找表分类： 静态查找
动态查找
当我们在数据结构中讨论查找表（也称为搜索表）时，我们通常根据查找过程中表是否发生变动来将其分类为静态查找和动态查找。以下是这两种查找类型的解释：
静态查找：
- 定义：在静态查找中，查找表中的数据在查找过程中不会发生变化。换句话说，我们只对查找表中的元素进行查询操作，而不进行插入或删除操作。
- 应用场景：通常用于只需要查询而不需要修改的数据集，如字典、电话簿等。
- 常用算法：顺序查找（线性查找）、二分查找（如果数据已排序）、哈希查找（如果可以使用哈希函数将数据映射到特定位置）等。
- 特点：由于数据在查找过程中不会发生变化，所以静态查找通常更注重查找效率，例如使用哈希表可以实现常数时间的查找。
动态查找：
- 定义：在动态查找中，查找表中的数据在查找过程中可能会发生变化。这通常涉及到在查找表中插入或删除元素。
- 应用场景：需要频繁插入、删除和查找元素的数据结构，如数据库、文件系统等。
- 常用数据结构：二叉搜索树（BST）、平衡二叉搜索树（如AVL树、红黑树）、B树、B+树、哈希表（虽然哈希表主要用于静态查找，但在某些实现中也可以支持动态操作）等。
- 特点：动态查找需要同时考虑查找效率以及插入和删除操作的效率。例如，在二叉搜索树中，插入和删除操作可以保持树的结构相对平衡，从而确保查找效率。而在哈希表中，插入和删除操作可能会导致哈希表的重构，以维持哈希表的性能。
总结：静态查找和动态查找的主要区别在于查找表中的数据在查找过程中是否会发生变化。静态查找更关注于查询效率，而动态查找需要同时考虑查询、插入和删除操作的效率。
3.查找算法的评价指标：关键字的平均比较次数ASL
ASL，即Average Search Length（平均查找长度），是衡量查找算法效率的一个重要指标。它表示在查找过程中，平均需要和待查找值进行比较的关键字次数。这个指标能够直观地反映查找算法的时间性能。
具体解释如下：
- 定义：
- ASL是指在查找过程中，为了找到目标元素，算法平均需要比较的关键字次数。
- 通常假设查找表中每个元素被查找的概率相同，即每个元素的查找概率Pi = 1/n，其中n为查找表中元素的个数。
- 计算方式：
- 对于每个元素i，设其被查找的概率为Pi，找到该元素所需的比较次数为Ci。
- 则ASL可以表示为：ASL = Σ(Pi * Ci)，其中Σ表示对i从1到n的求和。
- 在实际计算中，如果假设每个元素被查找的概率相同，即Pi = 1/n，则ASL可以简化为：ASL = (ΣCi) / n，即所有元素比较次数之和除以元素个数。
- 意义：
- ASL越小，说明查找算法的时间性能越好，即算法在查找过程中需要比较的关键字次数越少。
- 反之，如果ASL较大，则说明算法在查找过程中可能需要进行较多的比较操作，时间性能较差。
- 示例：
- 以顺序查找为例，假设查找表中有n个元素，且每个元素被查找的概率相同。在最坏情况下（即目标元素位于查找表的最后一个位置），每次查找都需要与查找表中所有元素进行比较，因此Ci = n。所以，顺序查找的ASL = (1+2+...+n) / n = (n+1)/2。