envzn
0.8 · beta · not released

Library / Collections / Dictionaries / ShallowDictionary

CLASSIMPLEMENTS Dictionary<K, V, H>

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 count
int64 tombstones
int64 cap
int64 shiftAmt
uint64 mult
int64 mask
boolean primeMode
uint64 primeP

Constructors 2

INIT()
INIT(Hasher[K] h)

Methods 14

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 __op_index__(REFERENCE K key) RETURNS V
reads

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 boolean
reads

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 boolean
reads
MODIFY METHOD remove(REFERENCE K key) RETURNS | K
modifies

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

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.