envzn
0.8 · beta · not released

Library / Collections / Dictionaries / ChainedHashDictionary

CLASSIMPLEMENTS Dictionary<K, V, H>

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 boolean
reads
METHOD size() RETURNS int64
reads

Number of key-value pairs currently stored. Read-only, O(1).

MODIFY METHOD clear() RETURNS void
modifies
MODIFY METHOD insert(K key, V value) RETURNS STATUS
modifies
MODIFY METHOD insertCopy(REFERENCE K key, REFERENCE V value) RETURNS STATUS
modifies
METHOD lookup(REFERENCE K key) RETURNS | MUTABLE REFERENCE V
reads
METHOD lookupFast(REFERENCE K key) RETURNS boolean
reads

Dictionary.lookupFast — same probe as lookup, without the STATUS that lookup must allocate on a miss.

MODIFY METHOD remove(REFERENCE K key) RETURNS | K
modifies
METHOD contains(REFERENCE K key) RETURNS boolean
reads
METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS boolean
reads

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.