In Defense of Linked Lists

Re:In Defense of Linked Lists by KerrAvon on Friday November 04, 2022 @08:34PM (#33476250)

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.

[ Parent | on HN ]

Re:In Defense of Linked Lists by asveikau on Friday November 04, 2022 @08:53PM (#33476418)

I 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.

[ Parent | on HN ]

Re:In Defense of Linked Lists by bluGill on Friday November 04, 2022 @09:02PM (#33476506)

Even 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.

[ Parent | on HN ]