对缓存技术讨论的一些补充
想起以前看 Linux 书的时候，里面说过为了缓存，Linux 使用了散列表。对于散列表的实现，主要有三个方面：散列函数、冲突解决方案、散列表大小策略。一般来说，整型的散列函数就是直接输出整型值。散列表的大小策略一般就是大小为一个质数（一般来说这样可以最大程序避免冲突）。而冲突解决方案主要有三种：第一种是再散列，即冲突发生时，将新加入的元素用某种方法再查找空位；第二种是链接表，即冲突发生时，将元素以链接表结点的形式记在已有元素之后；第三种是另外开一个表，专门存储冲突元素，这一般用于冲突很少的情况。
再散列是比较常用的做法，因为它对散列表的结构要求比较简单：只要是数组就行。.NET 类库中的散列表就采用这种做法。再散列的方法可以是依次查找再散列，即当冲突发生时，向下依次找，找到空白位置为止。可以是对称依次查找再散列。也可以是平方探测再散列。平方探测再散列有一种特殊情况：设散列表大小是 n，如果找到 n – 1 的平方还没有找到空位，那么应该采用其他方法，如依次查找，否则将会引起死循环。举个例子：当 n = 3 时，1 的平方模 3 余 1，2 的平方模 3 是 1，此时如果再找 3 的平方，是没有意义的，因为 3 的平方模 3 余 0，又回到冲突的位置上去了。如果找 4 的平方也是没有意义的，因为 4 模 3 余 1，4 的平方模 3 的结果等于 1 的平方模 3 的结果。同样，找比 4 更大的平方也没有意义。所以要改变策略。
散列表的好处是：当冲突较少时，查找的时间复杂度接近 O(1)。不过坏处是：当冲突较多时，查找的时间复杂度接近 O(n)。
比起我所设想的稀疏数组，以再散列为冲突解决办法的散列表的好处是实现简单，平均效率可能比较高。不过稀疏数组的效率比较稳定，是它的好处。
有关散列表、稀疏数组、AVL 树、B 树
前天晚上和昨天（2005 年 2 月 11 日）想了很长时间，发现稀疏数组的平均效率在特殊情况下（非常不均匀的情况下）可能会很低。相比散列表就低得多了！
看来还是有必要用 AVL 树（平衡二叉搜索树）或 B/B+ 树来代替的。不过现在发现一个更明显的问题：虽然散列表在特殊情况下的效率可能非常低，但是一般情况下比 AVL 树和 B 树的效率都要高。而且，AVL 树和 B 树还需要程序自己开一个内存池与内存分配/释放程序以提供高速的内存分配与释放。也就是说，多数情况下，散列表更好！看来是没有必要舍弃散列表了。呵呵。