Killing time, just for fun. How do you write a set where insertion, lookup, and deletion all have a time complexity of O(1)?

Of course, I know everyone would immediately think: just use Dictionary! Well... sure, that works. Using HashSet is also a good option.

But let's set some constraints for ourselves to increase the difficulty. If we code it from scratch, without using any libraries, how do we build an O(1) set?

Just hash the input, use the hash to index into a binary search structure, and done? That's an easy problem. I spent 10 minutes writing one, just so future readers can roast me for it.

public sealed class BinaryHashTrie
{
    private BinaryHashTrie? _left;
    private BinaryHashTrie? _right;
    private bool _isTerminal;

    private bool ExistsBin(int hash)
    {
        if (hash == 0)
        {
            return _isTerminal;
        }

        var goLeft = (hash & 1) == 0;
        var next = hash >> 1;
        return goLeft 
            ? (_left?.ExistsBin(next) ?? false)
            : (_right?.ExistsBin(next) ?? false);
    }

    private BinaryHashTrie AddBin(int hash)
    {
        if (hash == 0)
        {
            _isTerminal = true;
            return this;
        }

        var goLeft = (hash & 1) == 0;
        var next = hash >> 1;
        if (goLeft)
        {
            _left = _left == null ? new BinaryHashTrie() : _left.AddBin(next);
        }
        else
        {
            _right = _right == null ? new BinaryHashTrie() : _right.AddBin(next);
        }
        return this;
    }
    
    public void Add(string input)
    {
        var hash = Math.Abs(input.GetHashCode());
        AddBin(hash);
    }

    public bool Exists(string input)
    {
        var hash = Math.Abs(input.GetHashCode());
        return ExistsBin(hash);
    }
}

Usage:

        var myDic = new BinaryHashTrie();
        myDic.Add("Java");
        myDic.Add("Python");
        myDic.Add("C++");
        myDic.Add("C");
        for (var i = 0; i < 10000000; i++)
        {
            // Add a random string
            myDic.Add("RandomString" + i);
        }
        myDic.Add("CSharp");

        Console.WriteLine("Exists: CSharp " + myDic.Exists("CSharp"));
        Console.WriteLine("Exists: Java " + myDic.Exists("Java"));
        Console.WriteLine("Exists: C++ " + myDic.Exists("C++"));
        Console.WriteLine("Exists: Ruby " + myDic.Exists("Ruby"));
        Console.WriteLine("Exists: Rust " + myDic.Exists("Rust"));

I actually ran a test, and it's clearly much faster than a linked list. The time complexity is kept at O(1). Of course, the issue is that hash collisions can occur. This means there's a probability of incorrect results (false positives, where a non-existent string is judged to exist). It's suitable for acceleration in low-precision scenarios, such as checking whether a user is already registered.

file