performance - ETS 操作运行时

Question

delete_objectets 包的运行时间是多少？鉴于存在n具有相同 key 的条目，k运行时delete_object是O(n)还是O(1)？如果确实是O(1)，该lookup操作如何返回按插入时间排序的所有元组？

谢谢！

标签： performancehashmaperlangets

Answer 1

erlang 邮件列表上的这篇文章来自 2011 年，但我认为它可能仍然存在：

http://erlang.org/pipermail/erlang-questions/2011-October/061705.html

Sverker Eriksson 给出的答案暗示查找时间将O(n)取决于相等键的数量：

插入/查找/删除分散键的平均恒定时间。具有许多相同键的包可能会导致性能不佳，因为这将导致具有相同键的对象之间的线性搜索（以及碰巧散列到同一个桶的其他对象）。