[erlang-questions] Ets bag complexity

Gleb Peregud gleber.p@REDACTED
Mon Dec 10 13:20:03 CET 2012

Hello list

As far as I can understand from paper [1] by Scott Lystic Fritchie ETS
tables of 'bag' type are implemented as a hash table with linear
arrays of values attached to each key?

So, are the following statements correct for bag ETSes?
- lookup and delete operations for key which has K values is of
average complexity O(1+K)
- insert operations are amortized O(1) (sometimes resizing of arrays is needed)
- select operations are O(N+K) where N is a number of keys, K is
number of values

Gleb Peregud

1: www.erlang.se/workshop/2003/paper/p43-fritchie.pdf

More information about the erlang-questions mailing list