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.
Check if empty.
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.
Is true iff this is borrow-checked.
TODO remove when https://github.com/dlang/dmd/pull/11000 has been merged
Get bin count.
Get length (read-only).
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.
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://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/
TODO: Add support for opApply by copying opApply members in ~/.dub/packages/emsi_containers-0.8.0/emsi_containers/src/containers/hashmap.d
TODO: Add bool isSorted that adds a set of indexes to the insertion and removal order of the indexes. Insertion is fast. Removal is slow. These indexes are jointly allocated with the buckets
TODO: Replace withCapacity with void capacity(size_t) like D arrays.
TODO: Replace remove branching on passElementByValue when https://github.com/dlang/dmd/pull/11000 has been merged and use in instead
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: tests fails when useSmallLinearSearch is set to false
TODO: Use set of Flags (defined here) as template params
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 FlatHashMap
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: 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 FlatHashMap 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/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.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
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 FlatHashMap and - byElement over FlatHashset 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.