3 ms·
I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a
by KerrAvon 4y ago
I think the cases where lookup is faster for a linearly scanned vector is where the hash computation overhead is greater than a linear scan. Assuming you have a good hash implementation, that should be true only for a small number of entries, where you need to determine "small" by measuring.
- asveikau 4y agoI think it's about locality and quickness of compare. So if you have a small data structure and/or large cache, and the key is not complicated.
- bluGill 4y agoEven if the key is cheap, that it isn't in cache means that vector will be faster just because we avoid the cache miss of loading the value into memory.