数据结构篇--分离链表vs线性探测

实验目的：从内存占用量、查找成功所需探测次数等方面来比较分离链表和线性探测。

假设：Item和link各占用一个机器字(machine word)的内存空间。

分离链表

假设表有 $M$ 个列表，每个列表的平均链长为 $4$。则：

• 总项数 $N=\alpha \times M=4M$ ，因为平均链长为 $4$，意味着负载因子 $\alpha =4$。
• 成功查找每个项所需的平均探测次数为 $2$，因为
  首先，假设某个列表的长度为 $L$，那么成功查找第 $1$ 个项所需的探测次数为 $1$，成功查找第 $2$ 个项所需的探测次数为 $2$，… ，查找第 $L$ 个项所需的探测次数为 $L$，从而成功查找每个项所需的平均探测次数等于$(1+2+\cdots +L)/L=\frac{L(L+1)}{2L}=\frac{L+1}{2}\approx \frac{L}{2}$。
  接着，每个列表的平均长度为 $\alpha$，那么成功查找每个项所需的平均探测次数就等于$\frac{\alpha }{2}=2$。
• 内存占用量为 $9M$ 个机器字，因为
  • 存储项需要 $4M$ 个机器字，因为共有 $N=4M$ 个项。
  • 存储链接需要 $5M$ 个机器字，因为 $4M$ 个项对应有 $4M$ 个next指针，$M$ 个列表对应有 $M$ 个头指针。

线性探测

下面分别从两个角度来比较分离链表和线性探测：

• 相同内存占用量下，比较两者在查找成功时所需的平均探测次数。
• 相同的查找成功时所需的平均探测次数下，比较两者的内存占用量。

对比查询性能

假设线性探测跟分离链表有相同的内存占用量，即 $N=4M$，$M^{\prime }=9M$，则：

• 线性探测的装载因子 $\alpha =N/M^{\prime }=4/9$。
• 线性探测在查找成功时所需的平均探测次数为 $1.4$，因为根据性质14.3，线性探测在查找成功时所需的平均探测次数公式为 $\frac{1}{2}(1+\frac{1}{1-\alpha })$。
• 跟分离链表相比，线性探测在查找成功时所需的平均探测次数少了 $0.3=(2-1.4)/2$。

对比内存占用量

假设线性探测跟分离链表在查找成功时所需的平均探测次数相同，也是 $2$，则

• 线性探测的装载因子 $\alpha =2/3$，因为根据性质14.3，线性探测在查找成功时所需的平均探测次数公式为 $\frac{1}{2}(1+\frac{1}{1-\alpha })=2$。
• 线性探测占用的内存量为 $6M$，因为假设线性探测跟分离链表里存储的项数相同，都为 $4M$，那么线性探测占用的内存量 $M=N/\alpha =4M\times 3/2=6M$。
• 跟分离链表相比，线性探测所需的内存占用量少了 $0.33\approx (9M-6M)/9M$。

结论

通过对比在相同假设下（项和链接各占一个机器字）分离链表和线性探测在内存占用与查找性能方面的表现，可以得出以下结论：

1. 在相同内存占用量下，线性探测表现出更优的查找性能。

   • 当两者都占用 $9M$ 个机器字内存时，分离链表（$N=4M$ 项，$\alpha =4$）的平均查找成功探测次数为 $2$ 次。
   • 而线性探测（$N=4M$ 项，装载因子 $\alpha =4/9$）的平均查找成功探测次数仅为 $1.4$ 次。
   • 这意味着线性探测比分离链表快 30%。

2. 在达到相同的查找性能时，线性探测能实现更低的内存占用。

   • 当两者都达到平均查找成功探测次数为 $2$ 次时，分离链表需要 $9M$ 个机器字内存。
   • 而线性探测（$N=4M$ 项，装载因子 $\alpha =2/3$）只需 $6M$ 个机器字内存。
   • 这意味着线性探测比分离链表节省约 33% 的内存。

综合来看，从性能（查找速度）和内存效率的角度，线性探测在这些比较场景下都展现出优于分离链表的表现。

总结

虽然分离链表在实现上可能更简单，并且性能退化更平稳，但在相同的资源约束下（内存或查找时间），线性探测在单位性能下能够更有效地利用内存，或在单位内存下提供更快的查找速度。 这表明在许多应用中，如果主要目标是优化性能和内存效率，开放寻址方法（如线性探测）通常是更好的选择。