My hunch is that b is often mitigated by the fact that you were having to touch many items? Such that you don't necessarily even care that it is O(1) in lookup, you are iterating over the items. (And if you aren't having to touch many of the items on the regular, than you probably won't see a benefit to this approach?)
