Is Vec<Option<Box<T>>> generally better than HashMap<usize, T> (assuming enough memory)

Assuming enough memory so we are not dealing with swap space, for read/write, is

Vec<Option<Box<T>>> pretty much guaranteed to be better than HashMap<usize, T> ?

What sorts of operations are you planning to do on the Vec<Option<Box<T>>>?

Yes, I'd generally expect this to be faster at many typical operations (insert, remove, random access read, random access write), at the expense of using more space. In many cases, Vec<Option<T>> would be faster still, but would potentially waste more space.

If the usize keys are very widely spaced, and there are not many of them, the HashMap is going to use much less memory, which is likely to mean much better performance ( fewer cache misses ). I think it all depends on the key distribution.


This is essentially VecMap.

The Box indirection is a separate consideration, which you may or may not want in either case.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.