Random data structure using bless of dimensionality

randomDataStructure.ts

interface BinaryTrieNode<T> {
    value?: T
    lc?: BinaryTrieNode<T>
    rc?: BinaryTrieNode<T>
}

class BinaryTrie<T> {
    root: BinaryTrieNode<T> = {}

    constructor(public readonly depth: number) {}

    public get(key: boolean[]) {
        let node: BinaryTrieNode<T> | undefined = this.root
        let i = 0
        while (node && i < this.depth) {
            if (key[i]) {
                node = node.lc
            } else {
                node = node.rc
            }
            ++i
        }
        return node?.value
    }

    public add(value: T) {
        const key = this.createKey()

        let node: BinaryTrieNode<T> | undefined = this.root
        for (const b of key) {
            if (b) {
                node = (node!.lc ??= {})
            } else {
                node = (node!.rc ??= {})
            }
        }
        node.value = value
        return key
    }

    public remove(key: boolean[]) {
        let node: BinaryTrieNode<T> | undefined = this.root
        let i = 0
        const stack = [] as BinaryTrieNode<T>[]
        while (node && i < key.length) {
            stack.push(node)
            if (key[i]) {
                node = node.lc
            } else {
                node = node.rc
            }
            ++i
        }

        if (!node) return

        while (stack.length) {
            const top = stack.pop()
            const nextTop = stack[stack.length - 1]
            
            if (!nextTop) break

            if (top === nextTop.lc) {
                delete nextTop.lc
                if (nextTop.rc) {
                    break
                }
            } else {
                delete nextTop.rc
                if (nextTop.lc) {
                    break
                }
            }
        }
    }

    public has(key: boolean[]) {
        let node: BinaryTrieNode<T> | undefined = this.root
        let i = 0
        while (node && i < this.depth) {
            if (key[i]) {
                node = node.lc
            } else {
                node = node.rc
            }
            ++i
        }
        return !!node
    }

    private createKey() {
        let key: boolean[]
        do {
            key = Array.from(new Array(this.depth), () => (Math.random() > 0.5 ? true : false))
        } while (this.has(key))
        return key
    }
}

It's just stupidly simple binary trie with random key generation. But if depth is significantly big (imo more than 64), there is almost no chance of collision between created key(s) and existing key(s). Note that the time complexity never affected by number of entries, so it can achieve O(1) time complexity of reading, writing and deletion. If there is a case of having insanely many entries, just increase depth a little bit(>80) would resolve collision issues.

This stupid data structure is inspired by Vector Symbolic Architecture (or Hyper Dimensional Coputing). This uses blessing of dimensionality. This implementation is just proof of concept, and I hope more better performance-friendly improvement would be found. Here are some suggestions.

• Use more compact trie
• Use arrays of numbers of which are bit coded, instead of boolean array
• Implement using other native languages

But actually this doesn't seem to be helpful in most real cases, since the constant is fairly big and tree has bad local cache efficiency. They can't be sorted neither. There are better ways to handle hash collision in reasonable cost with more tiny, compact hash data sturctures.