[erlang-questions] ETS bag performance characteristics
Tue Oct 18 11:03:19 CEST 2011
Kris Rasmussen wrote:
> I am currently using the ETS bag table type to store a list of PIDs
> associated with a given key. I'm concerned that the bag implementation may
> require a linear traversal to remove (and possibly also add) elements to the
> bag. Does anyone know how ETS bags are implemented? Ideally, I'd like to
> have constant lookups by key as well as constant adds/contains/removals. If
> I were to implement this outside of erlang I would use a Map<String, Set>
> type data structure.
All ETS tables, except ordered_set, are hash tables with separate
chaining to resolve collisions.
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).
ordered_set is implented as a binary AVL tree.
/Sverker, Erlang/OTP Ericsson
More information about the erlang-questions