Indeed, my calculation is pretty slapdash. But I figure that a two-data-structure solution might have even worse locality. And, of course, I was comparing the linear search against a hypothetical hashed search that took zero time.
I think the rule of thumb about linear versus hash is that tables smaller than 10--15 entries are faster or the same with a linear search. So I should calculate some additional statistics about the fields per record.
On the other hand, I'm always up for timing hopeful optimizations, so I may go ahead and implement the MapVector approach.