Yes, but a properly-sized hash table will result in an average of 1 to 2 cache misses per lookup regardless of how many elements. This is far better than what you get with other structures, except perhaps in specialized cases that happen to follow tree traversal.
and can be about a million times slower if you have to page fault all the way into swap.
Disk based data requires specialized algorithms.
accessing every element once in a large naive hash table will give you O(n) page faults on average whereas accessing every element sequentially in a vector will give you O(n/d) page faults where d is your page size. While asymptotically similar, in real life that constant d can be gigantic.
Sure, a vector is better when you only ever access elements in a single sequential order and don't add or remove elements anywhere except the end.
That being said, I'm not sure how the C++ unordered_map handles this
C++ defines a method of iterating over all the elements of an unordered_map. I think a typical implementation will just treat the hash memory as a vector and return values from the occupied buckets.
Yes, but a properly-sized hash table will result in an average of 1 to 2 cache misses per lookup regardless of how many elements. This is far better than what you get with other structures, except perhaps in specialized cases that happen to follow tree traversal.
and can be about a million times slower if you have to page fault all the way into swap.
Disk based data requires specialized algorithms.
accessing every element once in a large naive hash table will give you O(n) page faults on average whereas accessing every element sequentially in a vector will give you O(n/d) page faults where d is your page size. While asymptotically similar, in real life that constant d can be gigantic.
Sure, a vector is better when you only ever access elements in a single sequential order and don't add or remove elements anywhere except the end.
That being said, I'm not sure how the C++ unordered_map handles this
C++ defines a method of iterating over all the elements of an unordered_map. I think a typical implementation will just treat the hash memory as a vector and return values from the occupied buckets.