Old but still relevant, and since innoq link-rots.
Jarkko Oranen a.k.a. Chousuke posted an excellent table summarizing the performance characteristics of functions operating on different Clojure data structures:
disj--near-constantlogarithmic----| hash-map | sorted-map | hash-set | sorted-set | vector | queue | list | lazy seq | |
|---|---|---|---|---|---|---|---|---|
| conj | near-constant | logarithmic | near-constant | logarithmic | constant (tail) | constant (tail) | constant (head) | constant (head) |
| assoc | near-constant | logarithmic | - | - | near-constant | - | - | - |
| dissoc | near-constant | logarithmic | - | - | - | - | - | - |