3 ms·
> How do you preserve insertion order in a hash map? You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely criti
by layer8 2y ago
> How do you preserve insertion order in a hash map?
You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely critical in practice. It can be made more efficient if the hash map doesn’t need to support deletion.
- thinkharderdev 2y agoAh yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)
- Sesse__ 2y ago> The overhead is rarely critical in practice. Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.
- layer8 2y agoI repeat: This is rarely critical in practice. Of course there are cases where it becomes critical, but it’s a perfectly good default.