Make with the element element.
Destruct.
No copying.
Type of key stored.
Type of value stored.
Map insertion status.
Set insertion status.
Empty.
Check if element is stored.
Check if element is stored.
Check if element is stored. Move found element to a hole if possible.
Get value of key or defaultValue if key not present (and therefore nothrow).
Get reference to key-part of stored element at key, if present, otherwise return defaultKey.
Insert element, being either a key-value (map-case) or a just a key (set-case).
Insert or replace value at key.
Insert element, being either a key-value (map-case) or a just a key (set-case).
Insert elements, all being either a key-value (map-case) or a just a key (set-case).
Equality.
Indexing.
Supports the syntax aa[key] = value;.
Unsafe access to raw store.
Remove all elements matching keys followed by a rehash.
Remove element.
Reserve rom for extraCapacity number of extra buckets.
Try to retrieve class-element of type Class constructed with parameters params.
Numerator for grow scale.
Denominator for grow scale.
Is true iff K is an address, in which case holes are represented by a specific value holeKeyConstant.
In the hash map case, V is non-void, and a value is stored alongside the key of type K.
Get bin count.
Check if empty.
Get length (read-only).
Get key part of element.
Get key part.
Get key part of element.
Get value part of element.
Make with room for storing at least minimumCapacity number of elements.
Make with the elements elements.
Mutable element reference with mutable constant key and value.
Is true if an instance of SomeKey that can be implictly cast to K.
Setting this true doesn't give measurable speedups so set it to false for now.
Is true iff in-place rehashing during growth should be performed.
key type
value type
hash function or std.digest Hash
memory allocator for bin array
only activate when it's certain that this won't be moved via std.algorithm.mutation.move()
Use linear search instead probing when _store is smaller than linearSearchMaxSize
Use prime numbers as capacity of hash table enabling better performance of simpler hash-functions
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
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.