在Java中自定义实现HashTable？
我正在解决Quora problem和我的特殊解决方案，我需要一个散列表（long-keys，int-values）来缓存值。我希望Java HashMap可以得到改进，因为我知道我的数据类型的键和值，它们是原语，也是我的问题空间。我决定天真地继续使用“链表阵列”结构实现一个简单的哈希表（甚至我的linkedList是我自己实现的Node类）。但我注意到，我自己的朴素实现比普通的Java HashMap慢大约4倍。我也尝试使用Trove's LongToIntMap库来查看它们的功能。有没有人有任何好的建议来构建一个自定义的Long to Int哈希表，它明显优于Java HashMap？在Java中自定义实现HashTable？
我也尝试使用Trove的LongToIntMap库来查看它们的功能。
你试过看代码，看看它们是如何做到的吗？
无法确定地说出你在执行过程中做了什么错误而没有看代码。然而，一种可能的改进可能是将LinkedList<Integer>替换为使用int[]来表示列表的自定义“整数列表”类型。取决于你的散列表API，你应该能够避免将你的值表示为对象（特别是Integer s）的代价。 （并且作为推论，通过不执行具有用于键和/或值类型的通用类型的API，您将获得更好的性能和空间利用率。）
对于什么是值得的，可能导致穷人的一个错误性能忽略实施散列表大小调整。没有调整大小，表上的get和put操作的复杂性将为O(N)而不是O(1) ...，因为哈希链长度将与哈希表条目的数量成比例地增长。
最后，您需要清楚自己是否在优化性能或空间利用率。最佳的解决方案将有所不同....
“...将是O（N）而不是O（N）...”，它仍然渐近地比O（N）快，我猜...： - ） – Dirk
@Dirk - 固定。 （你知道我的意思是......） –
你是否分析了你的代码，看看它花费了多少时间？在散列函数？附加链接列表？添加？查询？ –
还记得Knuth的口头禅：“过早优化是万恶之源”。除非你有 - 或有理由怀疑 - 标准库实现的问题，否则你可能不应该担心。至少不是“过早地”;-) – paulsm4