Does Mathematica support an unordered set (e.g. hashset) data structure?

Question

Does Mathematica support any data structure representing an unordered set (without multiplicity) of Mathematica expressions? I would like this data structure to support $O(1)$ insertion, deletion, and membership testing.

Note that according to this answer, Associations only support $O(\log n)$ insertion and deletion.

Answer 1

DeleteDuplicates is another way to build sets, or, more precisely, ordered lists with no duplicates (a friend of mine calls such things "suits," I think a brilliant name). Note the last little minitest here fails:

{DeleteDuplicates[{}],
 DeleteDuplicates[{1}] == DeleteDuplicates[{1, 1}],
 DeleteDuplicates[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == 
  DeleteDuplicates[{1, 2, 3}]}

{{}, True, False}

Easy to fix by composing with Sort:

ClearAll[set];
set = Sort@*DeleteDuplicates;
{set[{}],
 set[{1}] == set[{1, 1}],
 set[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == set[{1, 2, 3}]}

{{}, True, True}

Here's a specific implementation of the ideas in Leonid's comment:

ClearAll[set];
set[l_List] := Sort@Keys@Association@MapThread[Rule, {l, l}];
{set[{}],
 set[{1}] == set[{1, 1}],
 set[{2, 1, 3, 1, 2, 3, 3, 2, 2, 1}] == set[{1, 2, 3}]}

{{}, True, True}

Keep or remove the Sort depending on whether you want a set or a suit. However, the Sort introduces more overhead, getting you away from (close to) O(1) perf, as you requested.

EDIT: The difference between set and suit can be important if you're trying to emulate a combinatorial function like Permutations. This function treats duplicate elements as identical, but it is also 'stable', meaning that it doesn't change the orders of inputs. If you try to emulate it using a set instead of a suit, you can get a scrambled answer. For instance, consider

Permutations[{1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{array}

Let's make our own permutations that can take a collector function as an input, and try it out with suit to check that we get the same answer, in the same order, as with the built-in Permutations:

ClearAll[permutations, set, suit];
set[l_List] := Sort@Keys@Association@MapThread[Rule, {l, l}];
suit[l_List] := Keys@Association@MapThread[Rule, {l, l}];
permutations[collector_, {}] := {{}};
permutations[collector_, xs_List] :=
  collector[
   Flatten[
    Table[
     With[{
       x = xs[[i]],
       plucked = Join[xs[[;; i - 1]], xs[[i + 1 ;;]]]},
      Prepend[x] /@ permutations[collector, plucked]],
     {i, Length[xs]}],
    1]];

permutations[suit, {1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{array}

Now try it with set as the collector:

permutations[set, {1, 1, 1, 0, 0}] // TeXForm

\begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array}