在 Hashtable 中实现排序

• 下载源文件 - 3.11 Kb

目录

• 引言
• 为什么需要排序
• 算法
• 需要注意的一些问题！
• 实现
• 性能
• 最终注释

引言

哈希表在搜索方面是一个方便的选择，特别是因为在集合中，元素是根据元素本身的信息存储的。这些信息通过（几乎）独占的方式通过哈希函数提取。虽然哈希表是一个有用的数据结构，但它们确实缺少一点——元素在哈希表中存储的顺序不会被保留。这意味着，给定一个 Hashtable，我可以获取 Hashtable 键集上的 Iterator（通过 keySet() 方法），或者我可以获取一个 Enumeration（通过 keys() 方法）。但两者都不能保证以插入的顺序检索元素。这是可以理解的，因为 Hashtable 通常更多地用于其哈希功能，而不是其他任何东西。

为什么需要排序

在我们的项目中，我们将 SQL 查询返回的结果存储在 Hashtable 中（以便以后可以轻松搜索）。但同时，我们需要保留 SQL 返回的顺序，因为数据库端的排序比在程序中进行排序快得多。此外，数据库可以很好地处理多个复杂排序（使用 order by 子句）。在这种情况，我们需要为 Hashtable 实现排序功能。

算法

显而易见的地方是查看 Java 编程语言的源代码，其中有 Hashtable.java。解决方案就是编写另一个类——OrderedHashtable.java，它使用了一些技术，如内部类。

算法很简单：取一个 Hashtable 和一个 Vector。每当您将对象放入 Hashtable 时，将相应的键放入 Vector。由于 Vector 是有序的，因此可以保证对它的 Enumeration 或 Iterator 以插入的顺序遍历键。所以，如果您稍后需要遍历 Hashtable 中的所有对象（按插入顺序），只需获取 Vector 的 Iterator，然后从 Hashtable 中获取相应的对象。这样就得到了一个 OrderedHashtable！当然，它仍然具有 Hashtable 的哈希功能，并且如果您有键，当然可以像在 Hashtable 中一样直接检索对象。唯一的新功能是，可以保证 Iterator（或 Enumeration）是有序的。

需要注意的一些问题！

当然，还有一些重要的事情需要注意，比如同步。由于可以从 OrderedHashtable 中添加和删除项，因此我们需要确保类的内部 Vector 和 Hashtable 是线程安全的。如果两个线程同时访问它，一个线程添加而另一个线程删除同一个对象，这可能会导致 Hashtable 处于任意、不确定的状态，其中 Vector、Hashtable 或内部元素计数（或所有这三者）可能不正确。这要求对某些代码段进行同步。

同样，还有一个重要的溢出问题。Hashtable 和 Vector 都是可调整大小的，但它们的大小增加方式不同。在 Hashtable 中，有一个 loadfactor，它指定在大小增加（通过调用 rehash() 方法）之前 Hashtable 可以变得多满。每当 Hashtable 中的条目数超过 loadfactor 和 current capacity 的乘积时，容量就会增加一倍。Hashtable 的默认 initial capacity 和 loadfactor 分别为 10 和 0.75。所以在默认情况下，当插入第 9 个对象时，Hashtable 会翻倍到 20。

然而，Vector 的操作方式不同。在 Vector 中，您可以指定一个 capacityIncrement 值。每当 Vector 变满时，其容量就会增加 capacityIncrement（如果 capacityIncrement 为 0，则加倍）。Vector 的默认 initialcapacity 和 capacityIncrement 分别为 10 和 0。在默认情况下，只有当插入第 11 个对象时，大小才会增长到 20。再次，当第 21 个对象进来时，大小会翻倍到 40，依此类推。在 put() 和 get() 方法中需要小心处理这种情况。像删除等其他问题也可以通过稍加注意轻松处理。

实现

现在轮到 inner classes 的魔力了。Iterator 和 Enumeration 被实现为内部类。（显然，还能怎么实现？）当调用 Enumeration（enumerateKeys() 方法）或 Iterator（iterateKeys() 方法）时，就是这个内部类在私有 Vector 上进行迭代，并从 Hashtable 中返回相应的对象，并确保将其保持在错误限制内。

性能

紧接着想到的是一个最终的思考——“实现这种排序的性能开销是多少？”由于我们使用的是 Vector，它在所有 Java 类中都属于性能较慢的类之一，因此我们确实预计我们的 OrderedHashtable 会比 Hashtable 慢。除了 OrderedHashtable 的源代码之外，我在下载包中还包含了两个小测试文件。代码注释良好，希望易于理解。其中一个（Test.java）证实了排序已正确实现（毕竟这是本文的主题！），而另一个文件（Performance.java）进行了一些基本的性能测试。它使用一百万个对象填充 Hashtable 和 OrderedHashtable，并比较访问它们所花费的时间。虽然 Test.java 将检索到的项目打印到标准输出流以显示它们确实与插入时的顺序相同，但 Performance.java 不打印对象本身。有两个原因：一是，我不想让屏幕充斥着两百万行，二是（更重要的是）System.out.println() 本身需要一些时间，而我们只想比较访问 Hashtable 元素所花费的时间。

在我的系统上，多次试运行表明，对于非常大的值（如 100 万），两者所需的时间几乎相同（31 毫秒）。这令人惊讶，因为我曾预计 Vector 会使 OrderedHashtable 慢很多。是的，偶尔，OrderedHashtable 的花费的时间是 Hashtable 的两倍，但这种情况很少见。您可以在您的系统上进行测试运行。您的体验可能会因系统、系统设置和当前负载而异。如果您有任何问题、评论、建议或新发现，您随时欢迎在 CP 上告知我和其他程序员。

最终注释

这里提供的源代码实现了 java.util.Hashtable 的大部分方法。但是，有几个方法被省略了，有些是因为它们不符合排序的概念（例如，那些返回 Set 的方法），有些是因为它们在底层 Hashtable 类中被声明为 protected 或 private（例如 rehash()）。但是，已经实现了足够多的方法，可以在几乎所有情况下提供 Hashable 的全部功能，同时保持排序。但如果您觉得它应该包含其他一些方法来提高 OrderedHashtable 的功能/可用性，那么您非常欢迎提供任何反馈并与 CP 社区讨论。:-)

感谢阅读本文。祝您有美好的一天！