Library / Collections / Dictionaries / ChainedHashDictionary
ChainedHashDictionary
ChainedHashDictionary
STORAGE:
- buckets : HashBucket[K,V][] — a RAW value-array of lean value-class buckets,
one per slot. Each HashBucket stores its entries INLINE (2 CollisionNode slots
+ a lazy spill), so there is NO per-bucket heap object and NO per-entry heap
node — the LinkedList-per-bucket + ChainedHashEntry + per-lookup heap iterator
of the old design are gone (that iterator alloc was the measured 174 ns/lookup
S4 bug). An empty bucket is a zero-count HashBucket (no nullable-slot problem).
- In-place bucket mutation binds a MUTABLE REFERENCE into .buckets[idx] (reads
bind a plain REFERENCE); the bucket's own MODIFY methods do the work.
- count : int64; hasher : Hasher OF K (interface-typed, decision 5);
bucketLevel : int64 (power-of-two growth level); growth : GrowthHint
(advisory, stored-unused for V1).
Constructors 4
INIT()No hasher, default sizing — CREATE a DefaultHasher[K].
INIT(Hasher[K] h)
Caller-supplied hasher, default sizing.
INIT(GrowthHint hint, int64 initialCapacity)
Default hasher + sizing hints (initialCapacity ignored for V1 — the pow2 ladder governs bucket count; GrowthHint stored, unused).
INIT(Hasher[K] h, GrowthHint hint, int64 initialCapacity)
Caller hasher + sizing hints.
Methods 13
METHOD clone() RETURNS Dictionary[K, V, H]reads
METHOD iterator() RETURNS ReferenceIterator[K]reads
METHOD keys() RETURNS LinkedList[K]reads
METHOD isEmpty() RETURNS booleanreads
METHOD size() RETURNS int64reads
Number of key-value pairs currently stored. Read-only, O(1).
MODIFY METHOD clear() RETURNS voidmodifies
MODIFY METHOD insert(K key, V value) RETURNS STATUSmodifies
MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUSmodifies
METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE Vreads
METHOD lookupFast(REFERENCE K key) RETURNS booleanreads
Dictionary.lookupFast — same probe as lookup, without the STATUS that
lookup must allocate on a miss.
MODIFY METHOD remove(REFERENCE K key) RETURNS | Kmodifies
METHOD contains(REFERENCE K key) RETURNS booleanreads
METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS booleanreads
Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.
Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so
two "equal" dictionaries would answer lookup(a) differently and neither
could stand in for the other — which is the whole point of an equivalence.
Keys-AND-values is what C++ (map and unordered_map), Rust, Swift,
Julia, Python and Java all specify. Keyset equality is a perfectly good
relation, but it is equality of the DOMAIN rather than of the dictionary,
and it deserves its own name (hasSameKeys) rather than this one.
Equal sizes plus a one-way walk is sufficient: with the counts already
equal, other cannot carry a key this one lacks unless this one also
carries a key other lacks — and the walk would have found that.