Nuclear Planning Manual

    @ronomon/hash-table
    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/ronomon__hash-table package

    2.0.8 • Public • Published

    hash-table

    Fast, reliable cuckoo hash table for Node.js.

    Installation

    npm install @ronomon/hash-table
    

    Motivation

    Why not use a vanilla Javascript object (or Set or Map) as a hash table?

    • A vanilla object has no interface to pre-allocate table capacity in advance, and a Set or Map constructor only accepts an iterable. If the Javascript engine's underlying implementation of a vanilla object is a hash table, then a vanilla object must resize multiple times (copying every key and value multiple times) while you insert millions of elements.

    • A vanilla object has no concept of binary keys. Encoding binary keys as hexadecimal or Base64 strings is slow, and Javascript strings have additional storage overhead.

    • Extreme GC pause times. Millions of pointers in a vanilla object can block the Node.js event loop every few seconds for tens to hundreds of milliseconds at a time, whenever the GC needs to mark every pointer in the object.

    A simple comparison, which you can run yourself:

    node vanilla.js
    

    Ignoring any GC implications or per-key memory overhead considerations, which are more serious:

    
                           keySize=16 bytes, valueSize=0 bytes
    
      @ronomon/hash-table: Inserting 4000000 elements...
      @ronomon/hash-table: 783ms
    
                new Set(): Inserting 4000000 elements...
                new Set(): 3695ms
    
           vanilla object: Inserting 4000000 elements...
           vanilla object: 5557ms
    
    

    Fast

    @ronomon/hash-table features several design decisions and optimizations:

    • Each element, a key and corresponding value, can reside in at most 1 of 2 possible buckets, guaranteeing constant lookup time in the worst-case.

    • Each bucket contains up to 8 elements to support a hash table load factor of 80% or higher, unlike linear or chained hash tables which support a load factor (elements / capacity) of at most 50% and which waste the other 50% of memory. A more efficient load factor means that table resizes are less frequent.

    • Each element in a bucket has a tag, which is an 8-bit hash of the key. When searching for an element in a bucket, these 8-bit tags are compared first, eliminating comparisons against most keys in the bucket.

    • Cache misses across buckets are reduced by an order of magnitude. In the case of a naive cuckoo hash table, if an element is not in its first bucket then its second bucket must be fetched from memory, causing a cache miss, which is slow and why cuckoo hashing is sometimes overlooked in favor of linear probing or double hashing. However, in our design, the first bucket has an 8-byte coarse-grained bloom filter (k=1). If the element is not in this bloom filter, the element is guaranteed not to be in either of its first or second buckets, and a cache miss can be avoided nearly 90% of the time.

    • The 8-bit tag further contributes to reduced cache misses within buckets when keys or values are large.

    • Each element is included in its first bucket's bloom filter, regardless of whether the element is in its first or second bucket, so that a negative lookup can be performed in a single branch by testing against a single bit in the bloom filter instead of testing against all 8 tags.

    • Each bucket has a 1-byte bitmap indicating which of the 8 slots in the bucket contain elements, so that the first empty slot in a bucket can be found with a single branch on a 256-byte precomputed lookup table instead of iterating across all 8 slots.

    • Each element's key is hashed with 2 independent hash functions to locate its first and second buckets. These hashes are computed by interleaving both hash function lookup tables into a single interleaved hash function lookup table for optimal locality of reference.

    • The hash function requires keys to be a multiple of 4 bytes and uses an unrolled loop, so that keys are hashed 4 bytes at a time.

    • The number of buckets in a table is a power of 2 for a fast bitwise mod. While Daniel Lemire's excellent fast alternative to the modulo reduction yields better entropy mixing of all available bits, it is not used since Javascript's 64-bit integer operations are not fast.

    • Each bucket is padded to a multiple of 64 bytes for optimal cache line alignment.

    • An unrolled copy method is selected at instantiation to copy the key and value without branching if the key or value is 4, 8, 16, 32, 64, 128, 256 bytes etc. A native copy method is used for larger values.

    • Methods accept a buffer and a buffer offset to avoid a buffer slice. While a buffer slice may not copy the underlying memory, it adds overhead through allocating an object which must eventually be reclaimed by the GC. This overhead is considerable when inserting millions of elements.

    • The CLOCK LRU eviction algorithm is supported at an overhead of 2 bits per element, so that the hash table can be used as a fast user-space cache.

    • Surprisingly, the implementation is written in Javascript to avoid the 100-200ns bridging cost of calling into C from Javascript. Even a C implementation making use of SIMD instructions may struggle to regain the cost of being called from Javascript.

    Reliable

    @ronomon/hash-table was designed for billions of elements:

    • Each hash table instance is partitioned across multiple buffers and scales linearly up to a maximum of 4,294,967,296 elements or 16 TB of memory, whichever comes first.

    • Exactly 2.5 bytes of overhead per element at 100% load.

    • The implementation is purely in terms of huge flat buffer instances. Apart from jumping to a huge flat buffer instance, there is no pointer chasing. Most importantly, this sidesteps memory fragmentation issues and is GC friendly. If the GC cannot look into the buffers, the GC has nothing further to do. This places almost zero load on the GC.

    • Tabulation hashing is used as a fast high-quality hash function instead of more popular hash functions such as MurmurHash etc. Tabulation hashing has excellent proven theoretical properties, guarantees 3-independence, consists solely of table lookups and XOR, is one of the fastest hash functions when evaluating hash functions implemented in Javascript, and is resistant to hash flooding attacks. When compared with hash functions which use magic numbers and attempt avalanche through empirical methods, tabulation hashing is easier to understand and implement, and harder to get wrong.

    • Each 8-byte bloom filter has a separate 1-byte count of the number of elements in second position, so that bloom filters can be reset without a runaway increase in false positives.

    • Each 8-byte bloom filter is partitioned into 8 subsidiary filters, so that bloom filters can be reset with minimal latency. Further, this solves the edge case where a key in second position is never removed while other keys are churned repeatedly. Without bloom filter partitioning, the bucket's false positive rate would approach 100%. With bloom filter partitioning, only 1/8th of the bucket's filter would be adversely affected.

    • A maximum of 16 cuckoo displacements per insert are allowed in order to limit recursion and to keep the algorithm intuitive. If both buckets are full and no element can be displaced into another bucket, the buffer is resized by a factor of 2 to make space for the insert.

    • Each buffer is resized independently of other buffers so that the resize latency for a massive hash table is bounded per insert. This guarantee does NOT extend to a batch of inserts. For example, subsequent inserts may cause other buffers to resize in close succession. But then again, you can reserve or pre-allocate a massive hash table upfront to eliminate resize latency.

    • The number of resize attempts per insert is bounded as a precaution against resource exhaustion in the unlikely event that several resizes do not produce an empty slot.

    Usage

    var hashTable = new HashTable(keySize, valueSize, [elementsMin], [elementsMax])

    • keySize An integer, must be a multiple of 4 bytes, up to a maximum of 64 bytes (HashTable.KEY_MAX).
    • valueSize An integer, from 0 bytes up to a maximum of 1 MB (HashTable.VALUE_MAX).
    • elementsMin An integer, a hint as to the minimum number of elements expected to be inserted, to avoid unnecessary resizing over the short term.
    • elementsMax An integer, a hint as to the maximum number of elements expected to be inserted, to ensure sufficient capacity over the long term.

    hashTable.set(key, keyOffset, value, valueOffset)

    Inserts or updates an element in the hash table.

    • key A buffer, contains the key to be inserted or updated.
    • keyOffset An integer, the offset into key at which the key begins.
    • value A buffer, contains the value to be inserted or updated.
    • valueOffset An integer, the offset into value at which the value begins.
    • Returns an integer, 0 if the element was inserted, 1 if the element was updated.

    hashTable.get(key, keyOffset, value, valueOffset)

    Retrieves an element's value from the hash table.

    • key A buffer, contains the key to be retrieved.
    • keyOffset An integer, the offset into key at which the key begins.
    • value A buffer, the element's value will be copied into this buffer if the element exists.
    • valueOffset An integer, the offset into value at which to begin copying.
    • Returns an integer, 0 if the element was not found, 1 if the element was found.

    hashTable.exist(key, keyOffset)

    Tests whether an element exists in the hash table.

    • key A buffer, contains the key to be tested.
    • keyOffset An integer, the offset into key at which the key begins.
    • Returns an integer, 0 if the element was not found, 1 if the element was found.

    hashTable.unset(key, keyOffset)

    Removes an element from the hash table.

    • key A buffer, contains the key to be removed.
    • keyOffset An integer, the offset into key at which the key begins.
    • Returns an integer, 0 if the element was not found, 1 if the element was removed.

    hashTable.cache(key, keyOffset, value, valueOffset)

    Similar to set() but inserts by evicting a least recently used element, rather than resizing the hash table.

    • key A buffer, contains the key to be inserted or updated.
    • keyOffset An integer, the offset into key at which the key begins.
    • value A buffer, contains the value to be inserted or updated.
    • valueOffset An integer, the offset into value at which the value begins.
    • Returns an integer, 0 if the element was inserted, 1 if the element was updated, 2 if the element was inserted by evicting another element.

    cache() will never resize the hash table. Use the same elementsMin and elementsMax arguments to size the hash table appropriately.

    cache() and set() are mutually exclusive and cannot be used on the same hash table instance. This restriction is in place to prevent the user from accidentally evicting elements which were inserted by set(), and to enable several caching optimizations. When using cache(), you can still use get(), exist() and unset() to retrieve, test and remove cached elements.

    hashTable.capacity

    An integer, read-only, the current total capacity of the hash table, i.e. the number of elements which the hash table can accommodate at 100% load, which will increase through automatic resizing of the hash table buffers.

    hashTable.length

    An integer, read-only, the number of elements actually present in the hash table.

    hashTable.load

    A fraction between 0 and 1, read-only, the length of the hash table divided by the capacity of the hash table.

    hashTable.size

    An integer, read-only, the total size of all hash table buffers in bytes.

    Example

    var HashTable = require('@ronomon/hash-table');
    
    var keySize = 16;
    var valueSize = 4;
    var elementsMin = 1024; // Optional. Reserve space for at least 1,024 elements.
    var elementsMax = 65536; // Optional. Expect at most 65,536 elements.
    
    var hashTable = new HashTable(keySize, valueSize, elementsMin, elementsMax);
    
    // set():
    var key = Buffer.alloc(keySize);
    var keyOffset = 0;
    var value = Buffer.alloc(valueSize);
    var valueOffset = 0;
    var result = hashTable.set(key, keyOffset, value, valueOffset);
    if (result === 0) console.log('set(): element was inserted');
    if (result === 1) console.log('set(): element was updated');
    
    // get():
    var result = hashTable.get(key, keyOffset, value, valueOffset);
    if (result === 0) console.log('get(): element does not exist, nothing copied');
    if (result === 1) console.log('get(): element exists, copied value to buffer');
    
    // exist():
    var result = hashTable.exist(key, keyOffset);
    if (result === 0) console.log('exist(): element does not exist');
    if (result === 1) console.log('exist(): element exists');
    
    // unset():
    var result = hashTable.unset(key, keyOffset);
    if (result === 0) console.log('unset(): element does not exist, not removed');
    if (result === 1) console.log('unset(): element was removed');
    
    // cache():
    // cache() cannot be used on the same instance as set(), reinstantiate:
    var hashTable = new HashTable(keySize, valueSize, elementsMin, elementsMax);
    var result = hashTable.cache(key, keyOffset, value, valueOffset);
    if (result === 0) console.log('cache(): element was inserted');
    if (result === 1) console.log('cache(): element was updated');
    if (result === 2) console.log('cache(): element evicted another element');

    Exceptions

    Apart from validation exceptions thrown for programming errors, the following exceptions may be thrown for operating errors:

    HashTable.ERROR_MAXIMUM_CAPACITY_EXCEEDED

    A hash table buffer could not be further resized due to reaching HashTable.BUFFER_MAX or HashTable.BUCKETS_MAX. Increase elementsMax when instantiating the hash table to ensure sufficient capacity.

    HashTable.ERROR_SET

    An insert failed despite several resize attempts. This should never happen and may indicate weak system entropy.

    Performance

    
                CPU=Intel(R) Xeon(R) CPU E3-1230 V2 @ 3.30GHz
    
    ===============================================================================
                KEY=8 VALUE=0              |            KEY=8 VALUE=4              
    ---------------------------------------|---------------------------------------
          set() Insert              228ns  |      set() Insert              269ns  
          set() Reserve             134ns  |      set() Reserve             139ns  
          set() Update              149ns  |      set() Update              164ns  
          get() Miss                 99ns  |      get() Miss                100ns  
          get() Hit                 147ns  |      get() Hit                 164ns  
        exist() Miss                 98ns  |    exist() Miss                 99ns  
        exist() Hit                 143ns  |    exist() Hit                 148ns  
        unset() Miss                 98ns  |    unset() Miss                 98ns  
        unset() Hit                 196ns  |    unset() Hit                 200ns  
        cache() Insert              122ns  |    cache() Insert              139ns  
        cache() Evict               153ns  |    cache() Evict               174ns  
        cache() Miss                120ns  |    cache() Miss                133ns  
        cache() Hit                 133ns  |    cache() Hit                 136ns  
    ===============================================================================
                KEY=8 VALUE=8              |            KEY=8 VALUE=16             
    ---------------------------------------|---------------------------------------
          set() Insert              299ns  |      set() Insert              346ns  
          set() Reserve             158ns  |      set() Reserve             172ns  
          set() Update              175ns  |      set() Update              195ns  
          get() Miss                 96ns  |      get() Miss                103ns  
          get() Hit                 174ns  |      get() Hit                 191ns  
        exist() Miss                 94ns  |    exist() Miss                102ns  
        exist() Hit                 148ns  |    exist() Hit                 160ns  
        unset() Miss                 93ns  |    unset() Miss                101ns  
        unset() Hit                 204ns  |    unset() Hit                 224ns  
        cache() Insert              151ns  |    cache() Insert              165ns  
        cache() Evict               189ns  |    cache() Evict               207ns  
        cache() Miss                150ns  |    cache() Miss                158ns  
        cache() Hit                 146ns  |    cache() Hit                 166ns  
    ===============================================================================
                KEY=8 VALUE=32             |            KEY=8 VALUE=64             
    ---------------------------------------|---------------------------------------
          set() Insert              418ns  |      set() Insert              631ns  
          set() Reserve             190ns  |      set() Reserve             275ns  
          set() Update              225ns  |      set() Update              280ns  
          get() Miss                104ns  |      get() Miss                111ns  
          get() Hit                 223ns  |      get() Hit                 277ns  
        exist() Miss                103ns  |    exist() Miss                109ns  
        exist() Hit                 172ns  |    exist() Hit                 183ns  
        unset() Miss                103ns  |    unset() Miss                110ns  
        unset() Hit                 251ns  |    unset() Hit                 295ns  
        cache() Insert              192ns  |    cache() Insert              244ns  
        cache() Evict               229ns  |    cache() Evict               286ns  
        cache() Miss                167ns  |    cache() Miss                179ns  
        cache() Hit                 181ns  |    cache() Hit                 191ns  
    ===============================================================================
                KEY=8 VALUE=4096           |            KEY=8 VALUE=65536          
    ---------------------------------------|---------------------------------------
          set() Insert             6436ns  |      set() Insert            79601ns  
          set() Reserve            2178ns  |      set() Reserve           24260ns  
          set() Update             1518ns  |      set() Update            20550ns  
          get() Miss                135ns  |      get() Miss                181ns  
          get() Hit                 828ns  |      get() Hit                7904ns  
        exist() Miss                127ns  |    exist() Miss                171ns  
        exist() Hit                 232ns  |    exist() Hit                 269ns  
        unset() Miss                104ns  |    unset() Miss                 63ns  
        unset() Hit                1088ns  |    unset() Hit               13284ns  
        cache() Insert             1746ns  |    cache() Insert            20381ns  
        cache() Evict              1471ns  |    cache() Evict             20526ns  
        cache() Miss                180ns  |    cache() Miss                224ns  
        cache() Hit                 231ns  |    cache() Hit                 283ns  
    ===============================================================================
                KEY=16 VALUE=0             |            KEY=16 VALUE=4             
    ---------------------------------------|---------------------------------------
          set() Insert              339ns  |      set() Insert              389ns  
          set() Reserve             161ns  |      set() Reserve             182ns  
          set() Update              197ns  |      set() Update              211ns  
          get() Miss                114ns  |      get() Miss                115ns  
          get() Hit                 194ns  |      get() Hit                 208ns  
        exist() Miss                113ns  |    exist() Miss                112ns  
        exist() Hit                 197ns  |    exist() Hit                 189ns  
        unset() Miss                112ns  |    unset() Miss                111ns  
        unset() Hit                 250ns  |    unset() Hit                 423ns  
        cache() Insert              164ns  |    cache() Insert              184ns  
        cache() Evict               206ns  |    cache() Evict               225ns  
        cache() Miss                163ns  |    cache() Miss                166ns  
        cache() Hit                 183ns  |    cache() Hit                 189ns  
    ===============================================================================
                KEY=16 VALUE=8             |            KEY=16 VALUE=16            
    ---------------------------------------|---------------------------------------
          set() Insert              416ns  |      set() Insert              444ns  
          set() Reserve             189ns  |      set() Reserve             192ns  
          set() Update              225ns  |      set() Update              240ns  
          get() Miss                124ns  |      get() Miss                120ns  
          get() Hit                 221ns  |      get() Hit                 238ns  
        exist() Miss                122ns  |    exist() Miss                119ns  
        exist() Hit                 199ns  |    exist() Hit                 205ns  
        unset() Miss                122ns  |    unset() Miss                119ns  
        unset() Hit                 458ns  |    unset() Hit                 509ns  
        cache() Insert              185ns  |    cache() Insert              197ns  
        cache() Evict               232ns  |    cache() Evict               243ns  
        cache() Miss                176ns  |    cache() Miss                179ns  
        cache() Hit                 195ns  |    cache() Hit                 202ns  
    ===============================================================================
                KEY=16 VALUE=32            |            KEY=16 VALUE=64            
    ---------------------------------------|---------------------------------------
          set() Insert              527ns  |      set() Insert              521ns  
          set() Reserve             242ns  |      set() Reserve             324ns  
          set() Update              268ns  |      set() Update              331ns  
          get() Miss                125ns  |      get() Miss                122ns  
          get() Hit                 265ns  |      get() Hit                 328ns  
        exist() Miss                125ns  |    exist() Miss                120ns  
        exist() Hit                 217ns  |    exist() Hit                 234ns  
        unset() Miss                128ns  |    unset() Miss                121ns  
        unset() Hit                 619ns  |    unset() Hit                 484ns  
        cache() Insert              226ns  |    cache() Insert              279ns  
        cache() Evict               263ns  |    cache() Evict               316ns  
        cache() Miss                185ns  |    cache() Miss                206ns  
        cache() Hit                 212ns  |    cache() Hit                 224ns  
    ===============================================================================
                KEY=16 VALUE=4096          |            KEY=16 VALUE=65536         
    ---------------------------------------|---------------------------------------
          set() Insert             6264ns  |      set() Insert            80181ns  
          set() Reserve            2172ns  |      set() Reserve           23874ns  
          set() Update             1535ns  |      set() Update            20602ns  
          get() Miss                155ns  |      get() Miss                204ns  
          get() Hit                 863ns  |      get() Hit                7758ns  
        exist() Miss                148ns  |    exist() Miss                186ns  
        exist() Hit                 272ns  |    exist() Hit                 343ns  
        unset() Miss                130ns  |    unset() Miss                150ns  
        unset() Hit                1228ns  |    unset() Hit               13332ns  
        cache() Insert             1767ns  |    cache() Insert            20791ns  
        cache() Evict              1486ns  |    cache() Evict             20552ns  
        cache() Miss                201ns  |    cache() Miss                243ns  
        cache() Hit                 266ns  |    cache() Hit                 318ns  
    ===============================================================================
                KEY=32 VALUE=0             |            KEY=32 VALUE=4             
    ---------------------------------------|---------------------------------------
          set() Insert              526ns  |      set() Insert              549ns  
          set() Reserve             239ns  |      set() Reserve             251ns  
          set() Update              295ns  |      set() Update              302ns  
          get() Miss                160ns  |      get() Miss                161ns  
          get() Hit                 293ns  |      get() Hit                 302ns  
        exist() Miss                158ns  |    exist() Miss                158ns  
        exist() Hit                 281ns  |    exist() Hit                 282ns  
        unset() Miss                159ns  |    unset() Miss                158ns  
        unset() Hit                 590ns  |    unset() Hit                 616ns  
        cache() Insert              239ns  |    cache() Insert              249ns  
        cache() Evict               272ns  |    cache() Evict               282ns  
        cache() Miss                217ns  |    cache() Miss                224ns  
        cache() Hit                 271ns  |    cache() Hit                 277ns  
    ===============================================================================
                KEY=32 VALUE=8             |            KEY=32 VALUE=16            
    ---------------------------------------|---------------------------------------
          set() Insert              562ns  |      set() Insert              625ns  
          set() Reserve             244ns  |      set() Reserve             277ns  
          set() Update              316ns  |      set() Update              325ns  
          get() Miss                164ns  |      get() Miss                162ns  
          get() Hit                 314ns  |      get() Hit                 325ns  
        exist() Miss                161ns  |    exist() Miss                159ns  
        exist() Hit                 290ns  |    exist() Hit                 291ns  
        unset() Miss                162ns  |    unset() Miss                159ns  
        unset() Hit                 646ns  |    unset() Hit                 693ns  
        cache() Insert              243ns  |    cache() Insert              261ns  
        cache() Evict               290ns  |    cache() Evict               301ns  
        cache() Miss                227ns  |    cache() Miss                226ns  
        cache() Hit                 277ns  |    cache() Hit                 283ns  
    ===============================================================================
                KEY=32 VALUE=32            |            KEY=32 VALUE=64            
    ---------------------------------------|---------------------------------------
          set() Insert              685ns  |      set() Insert              739ns  
          set() Reserve             308ns  |      set() Reserve             356ns  
          set() Update              348ns  |      set() Update              399ns  
          get() Miss                161ns  |      get() Miss                154ns  
          get() Hit                 347ns  |      get() Hit                 398ns  
        exist() Miss                163ns  |    exist() Miss                154ns  
        exist() Hit                 296ns  |    exist() Hit                 304ns  
        unset() Miss                162ns  |    unset() Miss                155ns  
        unset() Hit                 799ns  |    unset() Hit                 662ns  
        cache() Insert              276ns  |    cache() Insert              360ns  
        cache() Evict               322ns  |    cache() Evict               376ns  
        cache() Miss                231ns  |    cache() Miss                272ns  
        cache() Hit                 289ns  |    cache() Hit                 299ns  
    ===============================================================================
                KEY=32 VALUE=4096          |            KEY=32 VALUE=65536         
    ---------------------------------------|---------------------------------------
          set() Insert             6761ns  |      set() Insert            78095ns  
          set() Reserve            2309ns  |      set() Reserve           23743ns  
          set() Update             1611ns  |      set() Update            20693ns  
          get() Miss                202ns  |      get() Miss                250ns  
          get() Hit                 952ns  |      get() Hit                7802ns  
        exist() Miss                190ns  |    exist() Miss                227ns  
        exist() Hit                 354ns  |    exist() Hit                 444ns  
        unset() Miss                174ns  |    unset() Miss                199ns  
        unset() Hit                1383ns  |    unset() Hit               13594ns  
        cache() Insert             1868ns  |    cache() Insert            20883ns  
        cache() Evict              1530ns  |    cache() Evict             20565ns  
        cache() Miss                246ns  |    cache() Miss                295ns  
        cache() Hit                 339ns  |    cache() Hit                 401ns  
    ===============================================================================
                KEY=64 VALUE=0             |            KEY=64 VALUE=4             
    ---------------------------------------|---------------------------------------
          set() Insert              947ns  |      set() Insert              961ns  
          set() Reserve             378ns  |      set() Reserve             370ns  
          set() Update              463ns  |      set() Update              471ns  
          get() Miss                240ns  |      get() Miss                236ns  
          get() Hit                 465ns  |      get() Hit                 471ns  
        exist() Miss                239ns  |    exist() Miss                236ns  
        exist() Hit                 452ns  |    exist() Hit                 452ns  
        unset() Miss                240ns  |    unset() Miss                237ns  
        unset() Hit                 628ns  |    unset() Hit                 650ns  
        cache() Insert              386ns  |    cache() Insert              383ns  
        cache() Evict               407ns  |    cache() Evict               412ns  
        cache() Miss                315ns  |    cache() Miss                323ns  
        cache() Hit                 432ns  |    cache() Hit                 437ns  
    ===============================================================================
                KEY=64 VALUE=8             |            KEY=64 VALUE=16            
    ---------------------------------------|---------------------------------------
          set() Insert             1008ns  |      set() Insert              837ns  
          set() Reserve             378ns  |      set() Reserve             439ns  
          set() Update              478ns  |      set() Update              501ns  
          get() Miss                235ns  |      get() Miss                231ns  
          get() Hit                 475ns  |      get() Hit                 498ns  
        exist() Miss                235ns  |    exist() Miss                230ns  
        exist() Hit                 451ns  |    exist() Hit                 466ns  
        unset() Miss                236ns  |    unset() Miss                230ns  
        unset() Hit                 674ns  |    unset() Hit                 720ns  
        cache() Insert              376ns  |    cache() Insert              390ns  
        cache() Evict               421ns  |    cache() Evict               434ns  
        cache() Miss                338ns  |    cache() Miss                353ns  
        cache() Hit                 444ns  |    cache() Hit                 448ns  
    ===============================================================================
                KEY=64 VALUE=32            |            KEY=64 VALUE=64            
    ---------------------------------------|---------------------------------------
          set() Insert              929ns  |      set() Insert             1293ns  
          set() Reserve             438ns  |      set() Reserve             516ns  
          set() Update              511ns  |      set() Update              555ns  
          get() Miss                227ns  |      get() Miss                231ns  
          get() Hit                 507ns  |      get() Hit                 553ns  
        exist() Miss                227ns  |    exist() Miss                227ns  
        exist() Hit                 459ns  |    exist() Hit                 457ns  
        unset() Miss                227ns  |    unset() Miss                229ns  
        unset() Hit                 821ns  |    unset() Hit                 688ns  
        cache() Insert              440ns  |    cache() Insert              479ns  
        cache() Evict               460ns  |    cache() Evict               485ns  
        cache() Miss                386ns  |    cache() Miss                302ns  
        cache() Hit                 454ns  |    cache() Hit                 435ns  
    ===============================================================================
                KEY=64 VALUE=4096          |            KEY=64 VALUE=65536         
    ---------------------------------------|---------------------------------------
          set() Insert             7004ns  |      set() Insert            81742ns  
          set() Reserve            2502ns  |      set() Reserve           24197ns  
          set() Update             1776ns  |      set() Update            20955ns  
          get() Miss                268ns  |      get() Miss                326ns  
          get() Hit                1166ns  |      get() Hit                8035ns  
        exist() Miss                259ns  |    exist() Miss                297ns  
        exist() Hit                 515ns  |    exist() Hit                 592ns  
        unset() Miss                249ns  |    unset() Miss                266ns  
        unset() Hit                1490ns  |    unset() Hit               13617ns  
        cache() Insert             2004ns  |    cache() Insert            21043ns  
        cache() Evict              1671ns  |    cache() Evict             20711ns  
        cache() Miss                336ns  |    cache() Miss                383ns  
        cache() Hit                 492ns  |    cache() Hit                 551ns  
    

    Tests

    @ronomon/hash-table ships with extensive tests, including a fuzz test:

    node test.js
    

    Benchmark

    node benchmark.js
    

    Install

    npm i @ronomon/hash-table

    DownloadsWeekly Downloads

    20

    Version

    2.0.8

    License

    MIT

    Unpacked Size

    95.3 kB

    Total Files

    8

    Last publish

    Collaborators

    • ronomon