我正在解决Quora 问题，对于我的特定解决方案，我需要一个哈希表（长键、整数值）来缓存值。我希望 Java HashMap 可以改进，因为我知道键和值的数据类型，它们是原语，也是我的问题空间。我决定天真地继续使用“链表数组”结构实现一个简单的哈希表（甚至我的链表也是我自己实现的 Node 类）。但我注意到我自己的幼稚实现比通用 Java HashMap 慢了大约 4 倍。我还尝试使用Trove 的 LongToIntMap库来看看他们做了什么。有没有人有任何好的建议来在 Java 中构建一个自定义的 Long to Int 哈希表，它的性能明显优于 Java HashMap？
问问题
1464 次
2 回答
1
我还尝试使用 Trove 的 LongToIntMap 库来看看他们做了什么。
您是否尝试查看代码以了解他们是如何做到的？
如果不查看代码，就无法确定您在实现中做错了什么。然而，一种可能的改进可能是将 替换为用于表示LinkedList<Integer>列表的自定义“整数列表”类型int[]。根据您的哈希表 API，您应该能够避免将值表示为对象（特别Integer是 s）的成本。（作为推论，您将通过不实现具有键和/或值类型的通用类型的 API 来获得更好的性能和空间利用率。）
值得一提的是，一个可能导致性能不佳的错误是忽略实现哈希表调整大小。在不调整大小的情况下，对表的复杂性get和put操作O(N)将比O(1)......因为哈希链长度将与哈希表条目的数量成比例地增长。
最后，您需要清楚自己是在优化性能还是空间利用率。最佳解决方案会有所不同......
于 2011-08-20T06:40:51.097 回答