Library / Collections / Dictionaries / IntKeyedDictionary
IntKeyedDictionary
HIDDEN concrete Dictionary impl specialised for INTEGER keys: linear-probe open-addressing over a STRUCT-OF-ARRAYS (K[] keys + V[] vals), with a hash & mask home index. The TRUSTED-KEY FAST TIER. Pure Envzn, zero-dep.
Fields 4
int64 countint64 tombstonesint64 capuint64 maskConstructors 1
INIT(H 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: the
s04 experiments (IntDict) showed the pipe-XOR construction is a real per-lookup
cost, and operator[] returns V by value like ByteBuffer/String subscript.
Use contains/lookup when a miss must be distinguished from a stored 0.
METHOD lookupFast(REFERENCE K key) RETURNS booleanreads
Comma-return lookup — boolean f, V v := d->lookupFast(key). No pipe-XOR
(V | STATUS) tuple; the trivial (found, value) return the s04 prototypes
(IntDict/OADict) used to stay C-class. 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.
NOTE: unlike ChainedHashDictionary, this cannot move the halves out. The
storage is a struct-of-arrays open-addressed table, and reading a slot
(.vals[s]) is a subscript READ, which by rule clones rather than moves
(cxx_emit stmt_assign.py:149 — "the subscript is a read accessor, never
a move-out"). HashBucket escapes this because it can evict a whole
CollisionNode and take its fields; an SoA table has no move-out-at-index
primitive to call. So this pays one DUPLICATE per half, and the census
pins it at that rather than at 0. K is an integer here, so the key half
is a bit copy; only a class-typed V costs a real clone.
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.