Class HashIndex<T, K>

A data structure that maps elements to different memory locations so that they can be very efficiently stored and retrieved.

Choosing the key and determining how to detect duplicates

In the next example, we index the states of a [finite-state machine][1]. Each state has a unique id that we'd like to use as key. There is only one instance of each unique FSMState, so we can instruct HashIndex to use the much simpler strict equality check instead of the more advanced isEqual. Likewise, keys are just numbers, so we can save come CPU cycles by directly comparing them.

import { HashIndex } from "scl";

interface FSMState {
  id: string;
  isFinal: boolean;
  edgeCount: number;
  nextStates: Array<[string, FSMState]>;
}

const s0: FSMState = {
  id: 0,
  isFinal: false,
  edgeCount: 1,
  nextStates: [
    ['a', s1],
  ]
}

const s1: FSMState = {
  id: 1,
  isFinal: true,
  edgeCount 0,
  nextStates: [],
}

const allStates = new HashIndex<({
  getKey: state => state.id,
  compareKeys: (a, b) => a < b,
  isEqual: (a, b) => a === b,
  elements: [s0, s1],
});

assert(allStates.getKey(1) === s1);

See

  • AVLTreeIndex for when the elements have to be sorted and there are frequent lookups
  • RBTreeIndex for when the elements have to be sorted and there are frequent mutations

Type Parameters

  • T
  • K = T

Hierarchy (View Summary)

Implements

Accessors

size

Methods

[iterator] add clear clone delete deleteAll deleteAt deleteKey equalKeys findKey has hasKey toRange

Accessors

size

  • get size(): number

  • Count the amount of elements in the collection.

    ⚠️ In most cases, this should be an O(1) operation. However, there are cases where this can be an O(n) operation. Therefore, it is recommended to always cache the result in a local variable.

    Returns number

Methods

[iterator]

  • "[iterator]"(): Generator<T, void, unknown>

  • Returns an object which is able to sift through the values in this collection.

    The order by which the elements are traversed depends on the kind of collection. For unordered collections, the iteration order is unspecified and may even differ between two iterations on the same collection.

    Returns Generator<T, void, unknown>

add

  • add(element: T): AddResult<T>

  • Add an element to the collection. If the element already exists, update its value.

    The location where the element is placed depends on the collection type, and in the generic case there is no guarantee on the location where it is inserted.

    This method returns a pair with the first element indicating whether the element was added, while the second element refers to the actual location of the element.

    Parameters

    • element: T

    Returns AddResult<T>

clear

  • clear(): void

  • Remove all elements from this collection, effectively setting the collection to the empty collection.

    Returns void

clone

delete

  • delete(el: T): boolean

  • Remove an element from the collection. If multiple elements are matched, the collection picks one of them.

    Parameters

    • el: T

    Returns boolean

    true if the element was found, false otherwise.

deleteAll

  • deleteAll(element: T): number

  • Remove an element from the collection. If multiple elements are matched, the collection removes all of them.

    Parameters

    • element: T

    Returns number

    The amount of elements that was removed.

deleteAt

deleteKey

  • deleteKey(key: K): number

  • Delete a pair from the underlying collection that has the given key as key.

    Returns the amount of items that have been deleted.

    Parameters

    • key: K

    Returns number

equalKeys

findKey

has

  • has(element: T): boolean

  • Checks if the collection holds the given element.

    Parameters

    • element: T

      The element to check membership of.

    Returns boolean

    True if the collections holds the given element, false otherwise.

hasKey

  • hasKey(key: K): boolean

  • Checks whether there a pair in this collection that has the given key.

    Parameters

    • key: K

    Returns boolean

toRange

Settings

Member Visibility

On This Page

Accessors
Methods