Playing with QUID string keys

I call those QUID string keys for "Quasi-Unique IDentifiers" : these randomized string keymaps are not ~100% guaranteed (cryptographocally speaking) to be unique during runtime, but the program can use them easily and safely to identify a bunch of data items, acommodating with possible collisions between consecutive computed values of the keys.

Context

Let's have a very big collections of blocks stored data inside a JS/TS Map:

type Block = { /* user data */ }

const blocks: Map <string, Block> = new Map ()

blocks.set ('abcd', { x: 1 })
blocks.set ('ef12', { y: 2 })
blocks.set ('3456', { z: 3 })        
blocks.set ('7890', { w: 4 })        

// oops we erased some useful data !
blocks.set ('abcd', { bad: '#ERROR!' })

We want enough keys to avoid collision and data loss; both we also want to keep human-readability for keys.

UUIDs ? No, just QUIDs !

Of course you probably think to a node library UUID-like to produce keys in the form: XXXX-XXXX-4YXX-XXXX-XXXXXXXXXXX ?If so you can watch

(see tutos #random #generator #etc...)

But do you really need for your todolists, a lightweb game a such level of uniqness and unpredictility in yout keys ?

If not, just try the QUID approach !

Let's figure out N-digits hexadecimal strings, such as "900dcafe": "bada55e5" or "c0cac01a".

LENGTH  available values

2       256

4       65536 (= 256 * 256)

8       ~ 4.2 * Math.pow (10, 9)

16      ... isn't it enough ??

Computing

Since access to Map is algorithmically time-constant O(1) complexity, let's compute new keys against user map keys.

// "phantom" property...

export type QUID = string & { __quid: void }

export  const nextQUID = (exists: (qtest: QUID) => boolean): QUID => {

    let counter: number = 0

    let qtest: QUID

do {
    const str = [0, 1, 2, 3].map ((_) =&gt; {
        return Math.floor (256 * Math.random ())
            .toString (16)
            .padStart (2, '0')

    }).reduce ((acc, str) =&gt; acc += str, '')

    qtest = fromString (str)    

    if (counter &gt; 1000) {
        throw new Error ('#QUID_LOOP!')
    }

    counter++
} while (exists (qtest))

return qtest



    

    




}

Storage impacts

Performance considerations

Since Map.has is O(1) time complexity and 8-kzngth hexa-string could address 4.2 * Math.pow (10, 9), collision risks are limited, same for loops in nextQUID function.

So can be efficient.

Happy coding !

François-Emmanuel CORTES @hefeust