Another wrinkle is that the constant factors can be data-dependent: which data structure to choose can heavily depend on the distribution of data you typically see.