数据结构：哈希表和查找算法

除留余数法-数据结构文档 在数据结构中，哈希表是一种常用的数据结构，通过哈希函数将关键码映射到哈希表中的索引上。今天，我们将讨论除留余数法和乘余取整法这两种常用的哈希函数。 **除留余数法** Hash(key) = ⌊ B*(A*key mod 1) ⌋ 其中，A、B均为常数，且0<A<1，B为整数。该哈希函数的特点是，以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。 另一种形式的除留余数法是： Hash(key) = key mod p 其中，p是一个整数。该哈希函数的特点是，以关键码除以p的余数作为哈希地址。 在设计哈希表时，如何选取合适的p是一个重要的问题。通常，取p≤m且为质数（也可以是不包含小于20质因子的合数），其中m为哈希表的长度。 **乘余取整法** 乘余取整法是另一种常用的哈希函数，定义为： Hash(key) = key mod 1 该哈希函数的特点是，取A*key的小数部分作为哈希地址。 例如，欲以学号最后两位作为地址，则哈希函数应为： H(k) = 100*(0.01*k % 1) 实际上，这也可以用除留余数法实现：H(k) = k % 100。 **查找表** 在数据结构中，查找表是一种常用的数据结构，用于存储和查找数据元素。查找表可以分为静态查找表和动态查找表两种。静态查找表的查找方法主要有顺序查找和折半查找两种，而动态查找表的查找方法则更为复杂。 **查找方法** 查找方法是指在查找表中查找某个数据元素的过程。查找方法可以分为静态查找和动态查找两种。静态查找是指在静态查找表中查找数据元素，而动态查找是指在动态查找表中查找数据元素。 **评估查找方法** 评估查找方法的优劣可以通过平均查找长度（ASL）来衡量。ASL是指在查找某个数据元素时所需的平均比较次数。 ASL = ∑(Pi \* Ci) 其中，n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）；Ci是找到第i个记录时所经历的比较次数。 显然，ASL值越小，时间效率越高。