Library / Collections / Dictionaries / HashBucket
HashBucket
PARAMETERISED OVER HASH: uint64 for ChainedHashDictionary (FNV), uint128 for
ProHashDictionary (SipHash-2-4-128). Every scan rejects on the cached HASH before the
key compare (CollisionNode.matches). Equal cached hashes form a contiguous run the
scans walk for the key match.
Constructors 1
INIT()Methods 13
METHOD size() RETURNS int64reads
Number of entries in this bucket.
MODIFY METHOD insert(K key, V value, HASH hash) RETURNS booleanmodifies
Insert key→value (with cached hash). TRUE if a new entry was added,
FALSE if an existing key's value was replaced in place.
METHOD lookup(HASH hash, REFERENCE K key) RETURNS booleanreads
Look up key (with cached hash) — TRIVIAL (found, value) multi-return, so
the hot path never builds an _EvStatus. value is the type default on a miss.
HYBRID (measured crossover at depth ~24): the common shallow bucket
(≤ LINEAR_SCAN_MAX entries) is a plain linear scan from 0 — no lowerBound
binary search, and one matches() per node (no redundant outer hash pre-check).
Only a deep/flooded bucket (> LINEAR_SCAN_MAX) pays the O(log n) sorted path.
The sorted invariant is kept by insert, so the deep path stays valid.
METHOD lookupRef(HASH hash, REFERENCE K key) RETURNS | MUTABLE REFERENCE Vreads
Look up key — a non-owning reference into the stored value, or FAILURE.
A borrow-propagating ("mirror") accessor: the returned reference mirrors
the receiver's mutability (a mutable bucket yields a MUTABLE REFERENCE, a
const bucket a read-only REFERENCE). Binds directly to the matched node's
INTERNAL value field.
METHOD containsKey(HASH hash, REFERENCE K key) RETURNS booleanreads
TRUE if key is present.
METHOD keyCloneAt(int64 i) RETURNS Kreads
A clone of the i-th node's key.
METHOD valueCloneAt(int64 i) RETURNS Vreads
A clone of the i-th node's value.
METHOD hashAt(int64 i) RETURNS HASHreads
The cached hash of the i-th node — backs growAndRehash re-bucketing.
MODIFY METHOD removeEntry(HASH hash, REFERENCE K key) RETURNS | Kmodifies
Remove key — returns the cloned-out key, or FAILURE. Shift-removes from the
sorted live region (the tail slides left, count--; the physical array is not
shrunk — the freed tail slot is reused by the next insert).
Evict the entry for key and hand BOTH halves back, moved — never
cloned. Replaces the former removeKey, which was written as
read-then-delete (keyCloneAt(pos) followed by the shift) and so
deep-copied the very key it was about to destroy — the Array.popLast
defect shape fixed in 3003ed5f, in its dictionary form.
The survivors still shift down and data's physical length is left
alone: it is a non-shrinking high-water mark and the vacated tail slot
is reused by the next insert (see the header note).
MODIFY METHOD placeNew(K key, V value, HASH hash) RETURNS voidmodifies
Build a node from (key, value, hash) and sorted shift-insert it. No update scan; the caller guarantees the key is new (rehash re-place / known-fresh).
METHOD clone() RETURNS HashBucket[K, V, HASH]reads
Deep copy — every live node cloned, in sorted order (so the clone stays sorted).
METHOD equals(REFERENCE HashBucket[K, V, HASH] other) RETURNS booleanreads
METHOD isLessThan(REFERENCE HashBucket[K, V, HASH] other) RETURNS booleanreads