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 ((_) => { return Math.floor (256 * Math.random ()) .toString (16) .padStart (2, '0') }).reduce ((acc, str) => acc += str, '') qtest = fromString (str) if (counter > 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 !