Dondish's HashMap
Hashmap and hashing implementation in JavaScript.
Installation
NPM:
npm i donhash
Yarn:
yarn add donhash
HashMap Implementation
Open-Addressing with linear probing and Robin Hood Bucket Stealing.
Memory Usage
The hashmap capacity is the smallest power of two larger than the amount of elements.
The hashmap does not shrink if element count goes down.
Benchmarks
Benchmarking: Insertion
Amount of insertions: 1000000
Min Insertion time: 0.0007999999943422154ms
Max Insertion time: 281.561099999999ms
Average Insertion time: 0.033581183399999555ms
Average Insertion time of the first 5000: 0.005359440000000012ms
Average Insertion time of the last 5000: 0.02661639999997569ms
Benchmarking: Insertion with no reallocation
Amount of insertions: 1000000
Min Insertion time: 0.0007999999943422154ms
Max Insertion time: 30.169999999998254ms
Average Insertion time: 0.002772173899998139ms
Average Insertion time of the first 5000: 0.000953620000022056ms
Average Insertion time of the last 5000: 0.03078976000006951ms
Benchmarking: Successful Lookup
Amount of lookups: 50000
Amount of elements: 1000000
Min Retrieval time: 0.000999999996565748ms
Max Retrieval time: 0.5910000000003492ms
Average Retrieval time: 0.002046426000012434ms
Average Retrieval time of the first 5000: 0.0029222600000459354ms
Average Retrieval time of the last 5000: 0.001903740000007383ms
Benchmarking: Failed Lookup
Amount of lookups: 50000
Amount of elements: 1000000
Min Retrieval time: 0.0007999999943422154ms
Max Retrieval time: 7.737300000000687ms
Average Retrieval time: 0.001981702000022051ms
Average Retrieval time of the first 5000: 0.0019545200000226034ms
Average Retrieval time of the last 5000: 0.0033657400000025517ms
Benchmarking: Removal
Amount of removes: 50000
Amount of elements: 1000000
Min Removal time: 0.000999999996565748ms
Max Removal time: 0.7252999999982421ms
Average Removal time: 0.005207931999969587ms
Average Removal time of the first 5000: 0.010110580000017945ms
Average Removal time of the last 5000: 0.0034685599999240368ms