scala - 在 Scala 中有效选择随机元素的适当集合类型

Question

对于我正在处理的项目，我需要跟踪多达数千个对象。我选择的集合需要支持随机元素的插入、选择和删除。我的算法会多次执行这些操作中的每一个，所以我想要一个可以在恒定时间内完成所有这些操作的集合。

有这样的合集吗？如果不是，与现有集合有哪些权衡？我正在使用 Scala 2.9.1。

编辑:通过“随机”，我的意思是数学上/概率上的随机，即，我想使用 Random 或其他一些适当的生成器从集合中随机选择元素。

Answer 1

定义“随机”。如果你的意思是索引，那么就没有这样的集合。如果您放弃“随机元素”要求，您可以在恒定时间内插入/删除 - 即，您对将被删除或将成为插入点的元素进行了非恒定查找。或者您可以在不经常插入/删除的情况下进行持续查找。

最接近该要求的集合是 Vector ，提供 O(log n)对于这些操作。

另一方面，如果您有要查找或删除的元素，则只需选择 HashMap .这不是完全恒定的时间，但它是一个公平的近似值。只要确保你有一个好的散列函数。