在哪里可以获得关于Dictionary ADT和Skip List for Java的更多信息？

Question

我试图深入到字典ADT和跳过列表为Java。我的教材没有涉及这方面的内容，它涵盖的内容非常复杂。哪一个是最好的在线网站，可以获得关于Dictionary ADT和Skip List for Java的更多信息。我正在寻找可视化谈话并给出了很多例子。

Answer 1

因为听起来像你在算法类中，所以我会从Java API提供的内容中分离字典和跳过列表的实现。在这一点上，更重要的是你了解这些抽象数据类型的概念，因为它们可以用任何语言实现（C＃，PHP，Scheme，Brainfuck等）。

你的导师可能会希望你为：首先，为字典（或跳过列表）定义接口或合约，然后找出其实现。如果您使用Java进行编程，请使用JUnit来验证算法的正确性。如果您使用其他语言进行编程，请查找任何xUnit API。

查看NIST's Dictionary of Algorithms and Data Structures作为您教科书的辅助资源，以了解这些内容的含义。 Java中最好的算法书可能是Sedgewick's，它的主要特点是它在教学中使用applet。由于示例代码不是用惯用Java编写的，因此我不会在这里看到这些算法的工业强度实现。毕竟，你应该自己完成这项工作，而不是使用其他人的集合API。

哦，顺便说一句，Java 6有两个跳过列表的实现：ConcurrentSkipListSet和ConcurrentSkipListMap。而Java中的字典数据结构的接口是Map。

Answer 2

您可以下载William Pugh原创论文的PDF文件，描述跳过列表及其背后的理论here。

此外，this是一个很好的小程序，可视化跳过列表的操作。当我的数据结构类中出现跳过列表时，它帮助了我很多。

另外，Wikipedia条目在其他实现和Java源代码的底部有一些很好的链接。