Library / Collections / Dictionaries / ShallowDictionary
ShallowDictionary
A Dictionary[K,V,H] with a WHOLE-KEY-SET-AWARE multiply-shift index and a prime-modulus fallback tier: linear-probe open-addressing over a STRUCT-OF-ARRAYS. Pure Envzn, zero-dep.
Fields 8
int64 countint64 tombstonesint64 capint64 shiftAmtuint64 multint64 maskboolean primeModeuint64 primePConstructors 2
INIT()INIT(Hasher[K] h)
Methods 14
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 __op_index__(REFERENCE K key) RETURNS Vreads
Direct value read — d[key]. Returns the stored value on a hit, or the V
default (0) on a miss. No pipe-XOR (V | STATUS) tuple on the hot path.
METHOD lookupFast(REFERENCE K key) RETURNS booleanreads
Comma-return lookup — boolean f, V v := d->lookupFast(key). No pipe-XOR;
found distinguishes a miss from a stored default.
METHOD contains(REFERENCE K key) RETURNS booleanreads
MODIFY METHOD remove(REFERENCE K key) RETURNS | Kmodifies
Remove — hands back the stored key and value. Like IntKeyedDictionary and unlike ChainedHashDictionary, an SoA open-addressed table has no move-out-at-index primitive, so a subscript read clones rather than moves (stmt_assign.py:149). Census pins this at one DUPLICATE per half.
METHOD isEmpty() RETURNS booleanreads
METHOD size() RETURNS int64reads
MODIFY METHOD clear() RETURNS voidmodifies
METHOD iterator() RETURNS ReferenceIterator[K]reads
METHOD keys() RETURNS LinkedList[K]reads
METHOD clone() RETURNS Dictionary[K, V, H]reads
METHOD equals(REFERENCE Dictionary[K, V, H] other) RETURNS booleanreads
for Equatable Interface Dictionary is equal if all keys between the two dictionaries are equal 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.