Module: collections.hashmap

Source: ./collections/hashmap.reef

Overview

collections/hashmap — HashMap[K, V], keys bounded by Hash.

Collections 0.9.2. Open addressing with linear probing. Grows and rehashes when an insert would push load past 70% (double capacity, min 1). Updates of an existing key never rehash, even at load >= 70%.

Usage: import collections.hashmap import core.option as option let ages = hashmap.create:string, int ages.set("ada", 36) match ages.get("ada") option.Option_Some(n) => println("ada=${n}") option.Option_None() => println("missing") end match

KEYS ARE COMPARED WITH ==, WHICH IS NOT VALUE EQUALITY FOR STRUCTS. For int, string and bool == compares values, which is what you want. For a struct or object it is REFERENCE IDENTITY (D3): two separately constructed structs with identical fields are different keys, so get(new User(...)) will not find an entry inserted under an equal- looking User. Key by an int or string field instead. This is pinned by examples/test_struct_eq_identity.reef.

There is no default_value any more. It existed so value_at() could return a V for an empty slot — a hole in the type, since that V was indistinguishable from a real stored value. Lookups return Option[V] and the slot walkers are gone (D7).

Factories: createK, V -> HashMap[K, V] 256 slots create_with_capacityK, V -> HashMap[K, V] cap < 1 clamps to 1

Methods: set(key, value) -> bool insert or update try_set(key, value) -> Result[bool, Error] Ok(true) = inserted, Ok(false) = updated, Err = hard failure add(key, value) -> bool insert only; false if key exists get(key) -> option.Option[V] has(key) -> bool remove(key) -> bool true if it existed len() / capacity() / is_empty() / clear() keys() -> [K] occupied keys, probe order values() -> [V] same order as keys()

Performance: O(1) average get/set/has/remove; O(n) keys()/values()/rehash.

Types

HashMap

Entry states: 0=empty, 1=occupied, 2=deleted (tombstone)

Fields:

Functions

fn create(): HashMap[K, V]

fn create_with_capacity(cap: int): HashMap[K, V]

cap < 1 clamps to 1 (BUG-062): a zero-capacity table would divide by zero in slot_of, and every operation would have to special-case it.

Generated by reefc doc