HP Integrity NonStop J-Series - Manual (Page 307)

Container overhead Re-balance may occur at each insert
or remove. However it will happen
less often than for a balanced binary
tree. This depends on how fully
the nodes are packed. Each
node costs
ORDER(2p+t+1)+i and
there will be no more than
2N/ORDER, and no fewer
than min(N/ORDER,1)
nodes. Inserting presorted
items will tend to maximize
the size.
Sedgewick says the size is
close to 1.44 N/ORDER for
random data
Comments Insertion based on sort order.
The logarithm is approximately base
ORDER which is the splay of the
b-tree. (In fact the base is between
ORDER and 2ORDER depending on
the actual loading of the b-tree)
Replace for b-tree requires remove
then insert. For btreedictionary the
value is copied in place
Hash-based Collections [33]
operation time cost; space cost
Insert C p+t
Find (average item) C 0
Change/replace item C or 2C 0
Remove C p+t (recovered)
Container overhead ((M+2)p+i) + N(p+t) (1)
(Mp+(2p+i)b_used) + N(p+t) (2)
1: standard compliant version 2: b_used is
"number of used slots" for the "V6.1"
hashed collections