java - 堆栈和哈希联合

Question

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

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

我有以下问题:

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

您会为我的代码提出哪些性能改进建议？您知道我可以尝试哪些开源库/代码？

Answer 1

您已经有了一个非常好的实现。对我来说唯一明显的改进是你在弹出时通过搜索做的工作比你需要做的更多。您应该在堆栈中存储的不是键本身，而是键数组的索引。当您想查看最后一项时，这可以让您以仅多一个指针间接为代价快速弹出。

除此之外，只需将您的堆栈大小调整为 LOAD_FACTOR*(堆数组大小)，您的实现速度应该与您预期的一样快，同时根据您的速度要求，您可以管理尽可能少的内存。