1

我正在解决Quora 问题,对于我的特定解决方案,我需要一个哈希表(长键、整数值)来缓存值。我希望 Java HashMap 可以改进,因为我知道键和值的数据类型,它们是原语,也是我的问题空间。我决定天真地继续使用“链表数组”结构实现一个简单的哈希表(甚至我的链表也是我自己实现的 Node 类)。但我注意到我自己的幼稚实现比通用 Java HashMap 慢了大约 4 倍。我还尝试使用Trove 的 LongToIntMap库来看看他们做了什么。有没有人有任何好的建议来在 Java 中构建一个自定义的 Long to Int 哈希表,它的性能明显优于 Java HashMap?

4

2 回答 2

1

看看 Javolution 的FastMap。源代码可在此处获得。

于 2011-08-20T06:37:01.840 回答
1

我还尝试使用 Trove 的 LongToIntMap 库来看看他们做了什么。

您是否尝试查看代码以了解他们是如何做到的?


如果不查看代码,就无法确定您在实现中做错了什么。然而,一种可能的改进可能是将 替换为用于表示LinkedList<Integer>列表的自定义“整数列表”类型int[]。根据您的哈希表 API,您应该能够避免将值表示为对象(特别Integer是 s)的成本。(作为推论,您将通过不实现具有键和/或值类型的通用类型的 API 来获得更好的性能和空间利用率。)

值得一提的是,一个可能导致性能不佳的错误是忽略实现哈希表调整大小。在不调整大小的情况下,对表的复杂性getput操作O(N)将比O(1)......因为哈希链长度将与哈希表条目的数量成比例地增长。

最后,您需要清楚自己是在优化性能还是空间利用率。最佳解决方案会有所不同......

于 2011-08-20T06:40:51.097 回答