By efficient I mean they either have better or comparable time and/or
memory performance compared to their mutable versions.
Strictly speaking I don't believe this can exist, because you can always show me an immutable data structure and I can find ways to make something cheaper if it could be made mutable. For example, I might be able to eliminate the requirement for garbage collection or reference-counting if it was mutable.
There are data structures that are well-suited to become immutable though where the costs are relatively cheap. Most of the non-trivial ones are typically at least partially contiguous. That allows the costs of ref-counting or GC to be trivialized if the nodes are unrolled and store multiple elements each, not one element per node.
There's also often a balancing act between shallow copying more pointers vs. deep copying fewer non-unique elements because any data structure can be made immutable if you just copy the whole freaking thing every time you want to change anything, but that could be explosive in memory and processing requirements. On the flip side, if you shallow reference every single individual element, that could be explosive in memory and processing requirements with all the extra pointers, all the extra indirection and potential memory fragmentation, the cost of ref-counting or GC having to be paid for every single element, etc.
So often I think the most efficient immutable data structures for sets and dictionaries are going to be partially contiguous ones, like a hash table using open addressing but instead of using one giant array for the whole table, it uses unrolled blocks storing, say, 64 keys each. Another example would be an n-ary tree storing many keys in one node.
Of course a hash table using separate chaining is really straightforward to make immutable since making singly-linked LIFO lists immutable just requires storing a different head pointer per immutable list. However, it's straightforward but not very cheap since that implies, again, reference-counting or GC paid on a per-element level.
Also chances are that you'll need something like a "builder" or "transient" to express what you want to do with it, since you don't want to pay the cost of generating a new immutable instance every single time you just insert or remove one key.
A concrete example is Guava, where I have seen memory savings when
used with sets that don't need to be modified.
Here perhaps it's not so much about immutability but just a data structure being able to work off the assumption that elements will simply be inserted to it and known in advance and not having to deal with dynamic removal and insertion of elements after it's built.
In that case, for example, you can use a sequential memory allocator as one optimization because you don't have to handle freeing memory for individual elements since elements are never going to be individually removed from the data structure. All you have to be able to do is purge all the memory for all elements when the data structure is destroyed.
Also if the elements are all known in advance, you might be able to avoid having to do reallocations to expand the size of the structure. You can make it perfectly-sized upfront since you know all the elements you're going to be inserting to it upfront so you don't have to reserve any additional memory for future insertions.
Data structures which only need fulfill these types of "static" and not "dynamic" requirements also provide plenty of room for post-processing after they're built. A binary tree might be post-processed to reallocate its nodes in a cache-friendly access pattern, for example. You can afford that with a static kind of data structure that doesn't deal with dynamic insertions and removals since there's a clear build phase which leaves room for post-processing, after which you no longer have to deal with changes to the data structure.
Ex: Mutable "Clear" Method
Any data structure which has fewer functional requirements to deal with will generally have more room to optimize. But here it's not about immutable data structures so much as data structures which can just be built in advance and don't have to deal with dynamic insertions and removals. Such data structures could still be made mutable and stay just as cheap. For example, such a data structure might still provide a mutable
clear method to clear the entire contents of the set/dictionary, and providing such a mutable method would not require it to lose those potential optimizations described above. So there's no case as far as I see where immutability makes anything cheaper, since immutability imposes more functional requirements on a data structure, so to speak, not less.