OpenHashMap

Hash table/map with in-place open-addressing, storing keys of type K and values of type V.

Keys are immutable except for when they are classes in which case they are head-const (through bin reinterpretation to KeyValueType), This can be overridden by setting keyEqualPred to, for instance, a == b for class keys.

Uses quadratic probing (using triangular numbers) unless usePrimeCapacity in which case a simpler probing is used.

Deletion/Removal of elements is lazy via the bitmap _holesPtr or through assignment of of reserved value of KeyType when KeyType has hole-support via trait isHoleable.

Element iteration via - either byKey, byValue or byKeyValue over OpenHashMap and - byElement over OpenHashset respects taking the container argument either as an l-value or r-value using detected using auto ref-qualified parameter introspected using (__traits(isRef, y)). In the r-value case no reference counting is needed. In the l-value case setting borrowChecked to true adds run-time support for dynamic Rust-style ownership and borrowing between the range and the container.

@safe

struct OpenHashMap (

K

V = void

alias hasher = hashOf

string keyEqualPred = defaultKeyEqualPredOf!(K)

alias Allocator = Mallocator.instance

bool borrowChecked = false

bool useSmallLinearSearch = true

bool usePrimeCapacity = false

) if (

isNullable!K

) {

enum bool assumeNonFullHaystack;

enum isBorrowChecked;

enum hasAddressLikeKey;

enum hasHoleableKey;

enum holeKeyOffset;

@trusted

enum holeKeyAddress;

static K holeKeyConstant();

enum hasHoleableKey;

enum hasHoleableKey;

enum hasHoleableKey;

enum hasHoleableKey;

enum InsertionStatus;

static inout(K) keyOf(inout(SomeElement) element);

static inout(V) valueOf(inout(T) element);

alias KeyType = K;

alias ValueType = V;

enum nullKeyElement;

static inout(K) keyOf(inout(KeyValueType) element);

enum InsertionStatus;

static inout(SomeElement) keyOf(inout(SomeElement) element);

enum nullKeyElement;

template isScopedKeyType(SomeKey);

static typeof(this) withCapacity(size_t minimumCapacity);

this(T element);

static typeof(this) withElements(R elements);

typeof(this) dup();

bool opEquals(typeof(this) rhs);

auto borrowedErrorMessage;

void clear();

bool contains(SomeKey key);

bool containsUsingLinearSearch(SomeKey key);

bool containsWithHoleMoving(K key);

InsertionStatus insert(T element);

T insertAndReturnElement(SomeElement element);

void insertN(R elements);

enum bool growInPlaceFlag;

enum growScaleP;

enum growScaleQ;

void reserveExtra(size_t extraCapacity);

InsertionStatus insert(K key, V value);

const(Class) tryGetElementFromCtorParams(Params params);

inout(V) opIndex(SomeKey key);

inout(V) get(K key, inout(V) defaultValue);

const(K) getKeyRef(SomeKey key, const(K) defaultKey);

V opIndexAssign(V value, K key);

bool remove(SomeKey key);

import nxt.traits_ex : isRefIterable;;

bool empty();

size_t length();

size_t binCount();

size_t totalProbeCount();

double averageProbeCount();

inout(T)[] rawStore();

}

Constructors

this this(T element): Make with the element element.

Destructor

~this ~this(): Destruct.

Postblit

this(this) this(this): No copying.

Members

Aliases

KeyType alias KeyType = K: Type of key stored.
ValueType alias ValueType = V: Type of value stored.

Enums

InsertionStatus enum InsertionStatus: Map insertion status.
InsertionStatus enum InsertionStatus: Set insertion status.

Functions

averageProbeCount double averageProbeCount()
binCount size_t binCount(): Get bin count.
clear void clear(): Empty.
contains bool contains(SomeKey key): Check if element is stored.
containsUsingLinearSearch bool containsUsingLinearSearch(SomeKey key): Check if element is stored.
containsWithHoleMoving bool containsWithHoleMoving(K key): Check if element is stored. Move found element to a hole if possible.
dup typeof(this) dup()
empty bool empty(): Check if empty.
get inout(V) get(K key, inout(V) defaultValue): Get value of key or defaultValue if key not present (and therefore nothrow).
getKeyRef const(K) getKeyRef(SomeKey key, const(K) defaultKey): Get reference to key-part of stored element at key, if present, otherwise return defaultKey.
insert InsertionStatus insert(T element): Insert element, being either a key-value (map-case) or a just a key (set-case).
insert InsertionStatus insert(K key, V value): Insert or replace value at key.
insertAndReturnElement T insertAndReturnElement(SomeElement element): Insert element, being either a key-value (map-case) or a just a key (set-case).
insertN void insertN(R elements): Insert elements, all being either a key-value (map-case) or a just a key (set-case).
length size_t length(): Get length (read-only).
opEquals bool opEquals(typeof(this) rhs): Equality.
opIndex inout(V) opIndex(SomeKey key): Indexing.
opIndexAssign V opIndexAssign(V value, K key): Supports the syntax aa[key] = value;.
rawStore inout(T)[] rawStore(): Unsafe access to raw store.
remove bool remove(SomeKey key): Remove element.
reserveExtra void reserveExtra(size_t extraCapacity): Reserve rom for extraCapacity number of extra buckets.
totalProbeCount size_t totalProbeCount()
tryGetElementFromCtorParams const(Class) tryGetElementFromCtorParams(Params params): Try to retrieve class-element of type Class constructed with parameters params.

Manifest constants

growScaleP enum growScaleP;: Numerator for grow scale.
growScaleQ enum growScaleQ;: Denominator for grow scale.
hasAddressLikeKey enum hasAddressLikeKey;: Is true iff K is an address, in which case holes are represented by a specific value holeKeyConstant.
hasValue enum hasValue;: In the hash map case, V is non-void, and a value is stored alongside the key of type K.

Static functions

holeKeyConstant K holeKeyConstant()
keyOf inout(K) keyOf(inout(SomeElement) element): Get key part of element.
keyOf inout(K) keyOf(inout(KeyValueType) element): Get key part.
keyOf inout(SomeElement) keyOf(inout(SomeElement) element): Get key part of element.
valueOf inout(V) valueOf(inout(T) element): Get value part of element.
withCapacity typeof(this) withCapacity(size_t minimumCapacity): Make with room for storing at least minimumCapacity number of elements.
withElements typeof(this) withElements(R elements): Make with the elements elements.

Structs

T struct T: Mutable element reference with mutable constant key and value.

Templates

isScopedKeyType template isScopedKeyType(SomeKey): Is true if an instance of SomeKey that can be implictly cast to K.

Variables

assumeNonFullHaystack enum bool assumeNonFullHaystack;: Setting this true doesn't give measurable speedups so set it to false for now.
growInPlaceFlag enum bool growInPlaceFlag;: Is true iff in-place rehashing during growth should be performed.

See Also

https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

https://arxiv.org/abs/1605.04031

https://github.com/Tessil/robin-map

https://github.com/martinus/robin-hood-hashing

https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

https://en.wikipedia.org/wiki/Lazy_deletion

https://forum.dlang.org/post/ejqhcsvdyyqtntkgzgae@forum.dlang.org https://gankro.github.io/blah/hashbrown-insert/

TODO tests fails when useSmallLinearSearch is set to false

TODO Use set of Flags (defined here) as template params

TODO group nxt.probing functions in Prober struct given as type template param to OpenHashMap

TODO Make load factor dependent on current capacity or length and perhaps also type and hash-function to get memory efficiency when it matters. Similar to what is recommended in https://ticki.github.io/blog/horrible/.

TODO remove use of static if (__traits(isCopyable, ...)) in cases where compiler can handle more moves

TODO use mmap allocator when _store.sizeof is larger than at least 8 pages

TODO use StoreK in store and cast between it and KeyType

TODO allocate _holesPtr array together with _store to reduce size of OpenHashMap to 3 words when element type doesn't support it

TODO fix bug in growInPlaceWithCapacity and benchmark

TODO modify existing unittest for struct Rel { const string name; }

TODO use allocator.dispose() instead of allocator.deallocate() as in https://github.com/dlang-community/containers

TODO if hash-function is cast(size_t)(classInstance) always use prime length and shift pointer before hash based on alignof (might not be needed when module prime) to maximize memory locality when adding successively allocated pointers

TODO add extractElement that moves it out similar to http://en.cppreference.com/w/cpp/container/unordered_set/extract

TODO add merge or union algorithm here or into container_algorithm.d. See also: http://en.cppreference.com/w/cpp/container/unordered_set/merge. this algorithm moves elements from source if they are not already in this

TODO Robin-Hood-hashing

TODO enable borrowChecked unconditionally in version(debug) if and when opMove is implemented, in which case opMove() should assert false if this is borrowed. See: https://github.com/dlang/DIPs/pull/109

TODO keep only predicates with ref arguments (const scope auto ref) when LDC can optimize those as fast as value passing. add LDC issue for this

TODO save one word by making _store.length be inferred by primeConstants[_primeIndex] if this is not too costly

TODO only add one extra element to capacity when assumeNonFullHaystack is true

Meta

Source

See Implementation

nxt open_hashmap aliases

OpenHashSet

enums

isHoleable

functions

structs

templates

defaultKeyEqualPredOf

variables

isAddress