API / Belt / Belt_HashMap

Belt_HashMap

A mutable Hash map which allows customized hash behavior.

All data are parameterized by not its only type but also a unique identity in the time of initialization, so that two HashMaps of ints initialized with different hash functions will have different type.

For example:


type t = int
module I0 = unpack(Belt.Id.hashableU(~hash=(. a: t) => "&"(a, 0xff_ff), ~eq=(. a, b) => a == b))
let s0: t<_, string, _> = make(~hintSize=40, ~id=module(I0))

module I1 = unpack(Belt.Id.hashableU(~hash=(. a: t) => "&"(a, 0xff), ~eq=(. a, b) => a == b))
let s1: t<_, string, _> = make(~hintSize=40, ~id=module(I1))

The invariant must be held: for two elements who are equal, their hashed value should be the same

Here the compiler would infer s0 and s1 having different type so that it would not mix.


let s0: t<int, I0.identity>
let s1: t<int, I1.identity>

We can add elements to the collection:


let () = {
  add(s1, 0, "3")
  add(s1, 1, "3")
}

Since this is an mutable data strucure, s1 will contain two pairs.

undefined

Specalized when key type is int, more efficient than the generic type

module Int = Belt_HashMapInt

undefined

Specalized when key type is string, more efficient than the generic type

module String = Belt_HashMapString

t

The type of hash tables from type 'key to type 'value.

type t<'key, 'value, 'id>

id

The identity needed for making an empty hash map.

type id<'a, 'id> = Belt_Id.hashable<'a, 'id>

make

make(~hintSize=10, ~id) creates a new map by taking in the comparator and hintSize.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let hMap = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))

Belt.HashMap.set(hMap, 0, "a")

let make: (~hintSize: int, ~id: id<'key, 'id>) => t<'key, 'value, 'id>

clear

Clears a hash table.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let hMap = Belt.HashMap.fromArray([(1, "1")], ~id=module(IntHash))
Belt.HashMap.clear(hMap)
Belt.HashMap.isEmpty(hMap) == true

let clear: t<'key, 'value, 'id> => unit

isEmpty

isEmpty(m) checks whether a hash map is empty.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

Belt.HashMap.isEmpty(Belt.HashMap.fromArray([(1, "1")], ~id=module(IntHash))) == false

let isEmpty: t<'a, 'b, 'c> => bool

set

set(hMap, k, v) if k does not exist, add the binding k,v, otherwise, update the old value with the new v.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.fromArray([(2, "2"), (1, "1"), (3, "3")], ~id=module(IntHash))

Belt.HashMap.set(s0, 2, "3")

Belt.HashMap.valuesToArray(s0) == ["1", "3", "3"]

let set: (t<'key, 'value, 'id>, 'key, 'value) => unit

copy

Creates copy of a hash map.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.fromArray([(2, "2"), (1, "1"), (3, "3")], ~id=module(IntHash))
let s1 = Belt.HashMap.copy(s0)

Belt.HashMap.set(s0, 2, "3")

Belt.HashMap.get(s0, 2) != Belt.HashMap.get(s1, 2)

let copy: t<'key, 'value, 'id> => t<'key, 'value, 'id>

get

Returns value bound under specific key. If values not exist returns None.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")

Belt.HashMap.get(s0, 1) == Some("value1")
Belt.HashMap.get(s0, 2) == None

let get: (t<'key, 'value, 'id>, 'key) => option<'value>

has

Checks if x is bound in tbl.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")

Belt.HashMap.has(s0, 1) == true
Belt.HashMap.has(s0, 2) == false

let has: (t<'key, 'value, 'id>, 'key) => bool

remove

If bound exists, removes it from the hash map.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.remove(s0, 1)
Belt.HashMap.has(s0, 1) == false

let remove: (t<'key, 'value, 'id>, 'key) => unit

forEachU

Same as forEach but takes uncurried function.

let forEachU: (t<'key, 'value, 'id>, (. 'key, 'value) => unit) => unit

forEach

forEach(tbl, f) applies f to all bindings in table tbl. f receives the key as first argument, and the associated value as second argument. Each binding is presented exactly once to f.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.forEach(s0, (key, value) => Js.log2(key, value))
// prints (1, "value1")

let forEach: (t<'key, 'value, 'id>, ('key, 'value) => unit) => unit

reduceU

let reduceU: (t<'key, 'value, 'id>, 'c, (. 'c, 'key, 'value) => 'c) => 'c

reduce

reduce(tbl, init, f) computes (f(kN, dN) ... (f(k1, d1, init))...), where k1 ... kN are the keys of all bindings in tbl, and d1 ... dN are the associated values. Each binding is presented exactly once to f.

The order in which the bindings are passed to f is unspecified. However, if the table contains several bindings for the same key, they are passed to f in reverse order of introduction, that is, the most recent binding is passed first.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.reduce(s0, "", (acc, key, value) => acc ++ (", " ++ value)) == "value1, value2"

let reduce: (t<'key, 'value, 'id>, 'c, ('c, 'key, 'value) => 'c) => 'c

keepMapInPlaceU

Same as keepMapInPlace but takes uncurried function.

let keepMapInPlaceU: (t<'key, 'value, 'id>, (. 'key, 'value) => option<'value>) => unit

keepMapInPlace

Filters out values for which function f returned None.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.keepMapInPlace(s0, (key, value) => key == 1 ? None : Some(value))

let keepMapInPlace: (t<'key, 'value, 'id>, ('key, 'value) => option<'value>) => unit

size

size(tbl) returns the number of bindings in tbl. It takes constant time.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.size(s0) == 2

let size: t<'a, 'b, 'c> => int

toArray

Returns array of key value pairs.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.toArray(s0) == [(1, "value1"), (2, "value2")]

let toArray: t<'key, 'value, 'id> => array<('key, 'value)>

keysToArray

Returns array of keys.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.keysToArray(s0) == [1, 2]

let keysToArray: t<'key, 'a, 'b> => array<'key>

valuesToArray

Returns array of values.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.set(s0, 1, "value1")
Belt.HashMap.set(s0, 2, "value2")

Belt.HashMap.valuesToArray(s0) == ["value1", "value2"]

let valuesToArray: t<'a, 'value, 'b> => array<'value>

fromArray

Creates new hash map from array of pairs.

Returns array of values.

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let s0 = Belt.HashMap.fromArray([(1, "value1"), (2, "value2")], ~id=module(IntHash))
Belt.HashMap.toArray(s0) == [(1, "value1"), (2, "value2")]

let fromArray: (array<('key, 'value)>, ~id: id<'key, 'id>) => t<'key, 'value, 'id>

mergeMany

RES
module IntHash = Belt.Id.MakeHashable({
  type t = int
  let hash = a => a
  let eq = (a, b) => a == b
})

let hMap = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
Belt.HashMap.mergeMany(hMap, [(1, "1"), (2, "2")])

let mergeMany: (t<'key, 'value, 'id>, array<('key, 'value)>) => unit

getBucketHistogram

RES
  module IntHash = Belt.Id.MakeHashable({
    type t = int
    let hash = a => a
    let eq = (a, b) => a == b
  })
  let hMap = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
  Belt.HashMap.set(hMap, 1, "1")

  Belt.HashMap.getBucketHistogram(hMap)

let getBucketHistogram: t<'a, 'b, 'c> => array<int>

logStats

RES
  module IntHash = Belt.Id.MakeHashable({
    type t = int
    let hash = a => a
    let eq = (a, b) => a == b
  })
  let hMap = Belt.HashMap.make(~hintSize=10, ~id=module(IntHash))
  Belt.HashMap.set(hMap, 1, "1")

  Belt.HashMap.logStats(hMap)

let logStats: t<'a, 'b, 'c> => unit