Benchmark: array vs hashmap lookup

Script Preparation code:

function uuid() {
  return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c =>
    (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16)
  );
}
window.versionsArray = Array(100).fill({ type: 'module' }).map(a => ({ ...a, id: uuid(), archiveId: uuid() }))
window.versionsHash = versionsArray.reduce((hash, version) => { 
  if (!hash[version.type]) hash[version.type] = {}
  hash[version.type][version.id] = version.archiveId
  return hash; 
}, {})
window.locateId = versionsArray[70].id
window.locateArchiveId = versionsArray[70].archiveId

Tests:

array lookup
const foundVersionArchiveId = window.versionsArray.find(v => v.type === 'module' && v.id === window.locateId) console.assert(foundVersionArchiveId === window.locateArchiveId)
hash lookup
const foundVersionArchiveId = window.versionsHash.module?.[locateId] console.assert(foundVersionArchiveId === window.locateArchiveId)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
array lookup
hash lookup

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 days ago)

User agent: Mozilla/5.0 (X11; Linux x86_64; rv:151.0) Gecko/20100101 Firefox/151.0

Browser/OS: Firefox 151 on Linux

View result in a separate tab

Test name	Executions per second
array lookup	33408.6 Ops/sec
hash lookup	2306321.5 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark and explain what's being tested.

**Benchmark Overview**

The benchmark measures the performance difference between two approaches: array-based lookup and hash-based lookup. The test cases are designed to find a specific version of an archive ID in both data structures.

**Data Structures**

1. **Array-Based Lookup**: `window.versionsArray` is an array containing 100 objects, each with a unique `id` and `archiveId`. The `locateId` variable points to the 71st element of this array ( index 70).
2. **Hash-Based Lookup**: `window.versionsHash` is a nested hash map where the keys are types (`'module'`) and values are other hashes with IDs as keys and archive IDs as values. The `locateArchiveId` variable points to the value associated with the `locateId` key in this hash.

**Options Compared**

The two options being compared are:

1. **Array-Based Lookup**: Iterating through the array to find the desired element.
2. **Hash-Based Lookup**: Using a hash table to directly access the desired element by its key (archive ID).

**Pros and Cons of Each Approach:**

1. **Array-Based Lookup**:
	* Pros:
		+ Easy to implement in JavaScript.
		+ Can be used with any data structure.
	* Cons:
		+ Has a linear search time complexity (O(n)), making it slower for large datasets.
		+ May not be as efficient in terms of memory usage compared to hash-based lookup.
2. **Hash-Based Lookup**:
	* Pros:
		+ Fast lookups with an average time complexity of O(1), making it suitable for large datasets.
		+ Can reduce memory usage by avoiding unnecessary iterations.
	* Cons:
		+ Requires the data to be structured in a specific way (hash table).
		+ May not be as easy to implement or understand, especially for those without prior experience with hash tables.

**Library Used**

In this benchmark, the `crypto` library is used briefly to generate a random value for the UUID generation. The `crypto.getRandomValues()` method returns an array of cryptographically secure pseudo-random numbers.

**Special JS Feature/Syntax**

The `find()` method and template literals are being used in the benchmark. The `find()` method searches the array from left to right, stopping at the first element that satisfies the provided condition. Template literals allow for string interpolation using backticks (`).

**Alternatives**

Other alternatives to consider when searching or retrieving data in JavaScript include:

1. **Spread operators**: Used for creating new arrays by spreading existing arrays or objects.
2. **Set data structures**: Hash tables or sets can provide fast lookups and insertion/deletion operations.
3. **Object-based lookup**: Using object properties as keys to directly access values.

These alternatives may offer better performance, readability, or maintainability in specific scenarios, but the choice ultimately depends on the requirements of your application and personal preference.

Related benchmarks:

array vs hashmap lookup (version: 0)

Comparing performance of: array lookup vs hash lookup

Created: 2 years ago by: Guest

Jump to the latest result

array lookup

hash lookup

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):