如何重用 Scala 标准库来创建根本不处理冲突的 HashMap 变体？
在 Scala 的 HashMap 实现中，我可以看到特征 HashEntry、DefaultEntry 和 LinkedEntry 是相关的，但我不确定我是否可以控制它们。
问问题
637 次
2 回答
1
您可以通过扩展来做到这一点HashMap（阅读源代码HashMap以查看需要修改的内容）；基本上你会覆盖put并且+=不调用findEntry，并且你会覆盖addEntry(from HashTable) 来简单地计算哈希码并将条目放在适当的位置。然后它根本不会处理碰撞。
但这不是明智的做法，因为该HashEntry结构是专门为处理冲突而设计的——此时next指针变得完全多余。因此，如果您出于性能原因这样做，这是一个糟糕的选择；您有开销，因为您将所有内容都包装在Entry. 如果您不想进行冲突检查，最好将 (key,value) 元组存储在平面数组中，或者使用单独的键和值数组。
请记住，您现在将遭受hash value冲突，而不仅仅是 key。而且，通常，HashMap从小开始，然后扩展，所以你最初会破坏性地碰撞如果不是从小开始就可以幸存的东西。initialSize如果您知道要添加多少，您也可以覆盖，这样您就永远不需要调整大小。
但是，基本上，如果你想编写一个专用的高速不安全哈希映射，你最好从头开始编写它或使用其他库。如果您修改通用库版本，您将获得所有的不安全性而没有所有的速度。如果值得摆弄，那就值得完全重做。（例如，您应该实现过滤器和这样的映射f: (Key,Value) => Boolean而不是映射(K,V)元组——这样您就不必包装和解开元组。）
于 2010-05-10T20:57:40.280 回答
0
我想这取决于您所说的“根本不处理碰撞”是什么意思。MultiMap 上的薄层是否足以满足您的需求？
于 2010-05-14T12:25:34.663 回答