ETS Operations Runtime

Question

What is the runtime of delete_object for the ets bag? Given that there are n entries with the same key k, would the runtime of delete_object be O(n) or O(1)? If it is indeed O(1), how does the lookup operation return all tuples sorted by insert time?

Thanks!

Answer 1

This post on the erlang mailing list is from 2011, but I would assume that it probably still holds:

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

The answer given by Sverker Eriksson implies that the lookup time would be O(n) wrt the number of equal keys:

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).