Make with the element element.
Destruct.
No copying.
Type of key stored.
Type of value stored.
Get element count.
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 room 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/tombstones 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.
Is true iff this is borrow-checked.
Get bin count (capacity).
Check if empty.
Get length.
Is true if key is valid.
Get key part of element.
Element type.
Get key part.
Get key part of element.
Get value part of element.
Element type.
Make with room for storing at least minimumCapacity number of elements.
Make with the elements elements. TODO: Replace with makeWithElements.
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.
https://engineering.fb.com/2019/04/25/developer-tools/f14/
https://github.com/abseil/abseil-cpp/blob/master/absl/container/flat_hash_map.h
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/
Test: dmd -version=show -preview=dip1000 -preview=in -vcolumns -preview=fieldwise -debug -g -unittest -checkaction=context -allinst -main -unittest -I../.. -i -run hybrid_hashmap.d
TODO: Pass nullValue and holeValue explicitly as members of Options instead of relying on traits isNullable. The search and remove usages of isNullable, nullValue and holeValue (enum) members.
TODO: Support set/map union via ~ and ~= operator. See https://issues.dlang.org/show_bug.cgi?id=15682.
TODO: Support non-nullable keys via extra bit-set _nullsPtr similar to _store.holesPtr TODO: Don’t allocate _store.holesPtr when we don’t need removal such as for compiler (dmd) symbol tables. Use GrowOnlyFlag. TODO: Factor out array store into container/store.d
TODO: Add support for assignment from AA that calls withElements
TODO: Add test for real class types as keys to test/container and test also with normal AA
TODO: Add class type erasure layer to void* for the relevant members of HashMap store and factor out that store to container/store.d
TODO: Make sure key classes and pointers are shifted down by alignement as is done in AlignedAddress.toHash before hashed
TODO: Replace withCapacity with void capacity(size_t) like D arrays.
TODO: Tests fails when linearSearchMaxSize is set to 0
TODO: A test fails with when -preview=fieldwise is not passed.
TODO: Add support for opApply by copying opApply members in ~/.dub/packages/emsi_containers-0.8.0/emsi_containers/src/containers/hashmap.d
TODO: Implement foreach (const k, const v; _) support. See https://forum.dlang.org/post/tj700o$1412$1@digitalmars.com
TODO: Disable pragma(inline, true) and rebenchmark
TODO: Robin-hood case introspect key type for storage of parts of hash alongside nullValue and holeValue. Typically for address-types that doesn't need scanning. Example is Address for implementation of GC. This is a D showcase for code that is difficult to write in C++.
TODO: group nxt.probing functions in Prober struct given as type template param to HybridHashMap
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: For copyable types replace auto ref with logic that only passes by ref when it's faster to do so. See_Also: https://github.com/dlang/dmd/pull/11000. When -preview=in has been made the default this complexity can be removed. Or replace ref with in.
TODO: Use mmap allocator when _store.elts.sizeof is larger than at least 8 pages
TODO: Use StoreK in store and cast between it and KeyType
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/common.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 opPostMove is implemented, in which case opPostMove() should assert false if this is borrowed. See: https://github.com/dlang/DIPs/pull/109
TODO: Save one word by making _store.elts.length be inferred by prime_modulo.primeConstants[_primeIndex] if this is not too costly.
TODO: Only add one extra element to capacity when assumeNonFullHaystack is true
TODO: Remove use of static if (__traits(isCopyable, ...)) and `static if (__traits(isPOD, ...))` in cases where compiler can handle more moves
Hash table/map with open-addressing and hybrid storage, storing keys of type K and values of type V. Setting V to void turns the map into a set.
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 sentinel bitmap _store.holesPtr or through assignment of reserved value of KeyType when KeyType has hole/tombstone-sentinel-support via trait isHoleable. The terms "tombstone" and "sentinel" are used at, for instance, https://engineering.fb.com/2019/04/25/developer-tools/f14/ and https://www.youtube.com/watch?v=ncHmEUmJZf4&t=2837s.
Element iteration via - either byKey, byValue or byKeyValue over HybridHashMap and - byElement over HybridHashSet 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.