堆栈和哈希联合

Question

我正在尝试编写一个数据结构，它是 Stack 和 HashSet 的组合，具有快速推送/弹出/成员资格（我正在寻找恒定时间操作）。想想 Python 的 OrderedDict。

我尝试了一些事情，并得出了以下代码：HashInt和SetInt。我需要向源代码添加一些文档，但基本上我使用带有线性探测的散列来存储键向量中的索引。由于线性探测总是将最后一个元素放在已填充单元的连续范围的末尾，因此无需复杂的删除操作即可轻松实现 pop()。

我有以下问题：

• 数据结构消耗大量内存（一些改进很明显：stackKeys比需要的大）。
• 有些操作比我使用 fastutil 时慢（例如：pop()，在某些情况下甚至是 push()）。我尝试使用 fastutil 和 trove4j 重写类，但我的应用程序的整体速度减半。

你对我的代码有什么性能改进建议？你知道我可以尝试哪些开源库/代码？

Answer 1

您已经有了一个非常好的实现。对我来说唯一明显的改进是，在弹出时进行搜索，您所做的工作比需要做的工作多。您应该在堆栈中存储的不是键本身，而是键数组的索引。当您想要查看最后一项时，这可以为您提供非常快速的弹出操作，但只需多一次指针间接寻址。

除此之外，只需将堆栈大小设置为 LOAD_FACTOR*（堆数组大小），您就应该拥有与预期一样快的实现速度，并根据您的速度要求使用尽可能少的内存。