Scala：构建没有链表的 HashMap 变体的正确方法是什么？
如何重用 Scala 标准库来创建根本不处理冲突的 HashMap 变体？
在 Scala 的 HashMap 实现中，我可以看到特征 HashEntry、DefaultEntry 和 LinkedEntry 是相关的，但我不确定我是否对它们有任何控制权。
How mouch Scala standard library can be reused to create variant of HashMap that does not handle collisions at all?
In HashMap implementation in Scala I can see that traits HashEntry, DefaultEntry and LinkedEntry are related, but I'm not sure whether I have any control over them.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以通过扩展
HashMap来做到这一点（阅读HashMap的源代码以了解需要修改什么）；基本上你会重写put和+=来不调用findEntry，并且你会重写addEntry（来自HashTable）来简单地计算哈希码并将条目放置到位。那么它根本无法处理碰撞。但这并不是明智之举，因为
HashEntry结构是专门为处理冲突而设计的——此时next指针就变得完全多余了。因此，如果您出于性能原因这样做，那么这是一个糟糕的选择；您有开销，因为您将所有内容都包装在Entry中。如果您不想进行冲突检查，那么最好将（键，值）元组存储在平面数组中，或者使用单独的键和值数组。请记住，您现在将遭受哈希值冲突，而不仅仅是密钥冲突。而且，通常情况下，
HashMap从小处开始，然后扩展，因此您最初会破坏性地碰撞那些如果不是从小处开始就可以幸存的东西。如果您知道要添加多少，则也可以覆盖initialSize，这样就无需调整大小。但是，基本上，如果您想编写一个特殊用途的高速不安全哈希图，您最好从头开始编写它或使用其他库。如果您修改通用库版本，您将获得所有不安全性，而没有所有速度。如果值得摆弄，那就值得完全重做。 （例如，您应该实现过滤器并映射
f: (Key,Value) => Boolean而不是映射(K,V)元组 - 即这样您就不必包装和展开元组。）You could do this by extending
HashMap(read the source code ofHashMapto see what needs to be modified); basically you'd overrideputand+=to not callfindEntry, and you'd overrideaddEntry(fromHashTable) to simply compute the hash code and drop the entry in place. Then it wouldn't handle collsions at all.But this isn't a wise thing to do since the
HashEntrystructure is specifically designed to handle collisions--thenextpointer becomes entirely superfluous at that point. So if you are doing this for performance reasons, it's a bad choice; you have overhead because you wrap everything in anEntry. If you want no collision checking, you're better off just storing the (key,value) tuples in a flat array, or using separate key and value arrays.Keep in mind that you will now suffer from collisions in hash value, not just in key. And, normally,
HashMapstarts small and then expands, so you will initially destructively collide things which would have survived had it not started small. You could overrideinitialSizealso if you knew how much you would add so that you'd never need to resize.But, basically, if you want to write a special-purpose high-speed unsafe hash map, you're better off writing it from scratch or using some other library. If you modify the generic library version, you'll get all the unsafety without all of the speed. If it's worth fiddling with, it's worth redoing entirely. (For example, you should implement filters and such that map
f: (Key,Value) => Booleaninstead of mapping the(K,V)tuple--that way you don't have to wrap and unwrap tuples.)我想这取决于你所说的“根本不处理碰撞”是什么意思。 MultiMap 上的薄层足以满足您的需求吗？
I guess it depends what you mean by "does not handle collisions at all". Would a thin layer over a MultiMap be sufficient for your needs?