[erlang-questions] Ets bag complexity
Mon Dec 10 13:20:03 CET 2012
As far as I can understand from paper  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
More information about the erlang-questions