One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices.
This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.
I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.
Comments
My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices. This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.
I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.