performance - ETS 运营运行时

Question

ets 包的delete_object 的运行时间是多少？鉴于有 n 个条目具有相同的键 k，delete_object 的运行时间是否为 O(n)或者O(1)？如果确实是 O(1)，lookup 操作如何返回所有按插入时间排序的元组？

谢谢!

Answer 1

erlang 邮件列表上的这篇帖子是 2011 年的，但我认为它可能仍然有效:

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

Sverker Eriksson 给出的答案暗示查找时间为 O(n) wrt 相等键的数量:

On average constant time for insert/lookup/removal of scattered keys. A bag with lots of identical keys may give bad performance as that will result in linear searches between objects with the same key (and others that happen to hash to the same bucket).