I always preferred immutable sorted trees (such as found in Haskell or Scala) to concurrent hash tables when dealing with concurrent sets or maps.
You can add or remove a node from such trees without modifying the original trees, by only creating O(log(n)) nodes (tree branches that don't change don't have to be copied). So "modifying" a tree does not invalidate the previous versions of the tree, that can still be processed by concurrent threads if they still hold a reference to the root node. No longer referenced tree branches will then be discarded by the GC.
With a concurrent hash table, you have to hold a lock on the whole datastructure if you don't want it to be modified while processing it, and this makes the whole thing is harder to think about overall.
I also find it easier to implement a correct and fast comparison function (required by tree structures) than an equivalent hash function. Trees can also give you range search, and keep your items sorted, which are useful in some cases.
Trees are now my go to datastructures for map and sets unless maximum speed and minimal memory use are absolutely required. These might not be as efficient, but they make more reliable software.
Not if you don't want the hash table to change while doing some read only processing on it. Immutability ensures that the reference you get always point towards a object that is in a consistent state.
That is not the point. The point is that the hash table can be updated in a way (e.g., atomic) that is invisible to other readers and thefore they always see a consistent version of the hash table itself.
You can add or remove a node from such trees without modifying the original trees, by only creating O(log(n)) nodes (tree branches that don't change don't have to be copied). So "modifying" a tree does not invalidate the previous versions of the tree, that can still be processed by concurrent threads if they still hold a reference to the root node. No longer referenced tree branches will then be discarded by the GC.
With a concurrent hash table, you have to hold a lock on the whole datastructure if you don't want it to be modified while processing it, and this makes the whole thing is harder to think about overall.
I also find it easier to implement a correct and fast comparison function (required by tree structures) than an equivalent hash function. Trees can also give you range search, and keep your items sorted, which are useful in some cases.
Trees are now my go to datastructures for map and sets unless maximum speed and minimal memory use are absolutely required. These might not be as efficient, but they make more reliable software.