Library / Collections / Dictionaries / ProHashDictionary
ProHashDictionary
The DoS-RESISTANT dictionary, rebuilt on the byte-keyed substrate that made StringKeyedDictionary beat C. Pure Envzn, zero-dep beyond the SipHash key shim.
Constructors 1
INIT()Methods 27
MODIFY METHOD insertSlice(REFERENCE binary[] buf, int64 off, int64 len, V value) RETURNS STATUSmodifies
METHOD lookupFastSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS booleanreads
Comma-return lookup — no pipe-XOR (V | STATUS) tuple on the hot path.
METHOD containsSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS booleanreads
MODIFY METHOD removeSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS booleanmodifies
Remove. Unlinks the entry from the bucket's member chain, then RE-INDEXES the bucket: a treeified bucket that has fallen to the untreeify threshold drops its red-black index and reverts to a plain chain (hysteresis: treeify at >8, untreeify at <=6, so churn around the boundary cannot thrash); one still above it rebuilds the index. Rebuilding rather than running the CLRS red-black delete-fixup is a deliberate, bounded simplification (O(depth)) — labelled, not hidden. It keeps the single most bug-prone routine in a red-black tree out of the kernel, and remove is not the hot path; lookup and insert use the real tree.
MODIFY METHOD insert(REFERENCE binary[] key, V value) RETURNS STATUSmodifies
METHOD lookupFast(REFERENCE binary[] key) RETURNS booleanreads
METHOD __op_index__(REFERENCE binary[] key) RETURNS Vreads
Direct value read — d[key]. V default (0) on a miss. No pipe-XOR.
METHOD lookup(REFERENCE binary[] key) RETURNS | Vreads
Pipe-XOR lookup — the kernel idiom, kept OFF the hot path.
METHOD lookupRef(REFERENCE binary[] key) RETURNS | MUTABLE REFERENCE Vreads
METHOD contains(REFERENCE binary[] key) RETURNS booleanreads
MODIFY METHOD remove(REFERENCE binary[] key) RETURNS booleanmodifies
METHOD isEmpty() RETURNS booleanreads
METHOD size() RETURNS int64reads
MODIFY METHOD clear() RETURNS voidmodifies
METHOD bucketIndexOf(REFERENCE binary[] key) RETURNS int64reads
The bucket a key currently maps to.
Exposed for TESTABILITY of the adaptive tier. SipHash keying means an attacker cannot force colliding keys — which also means a TEST cannot, so the chain->tree escalation would otherwise be unreachable, untested kernel code. This lets a test group keys that share a bucket and drive the escalation deterministically.
It does NOT weaken the DoS guarantee: hash-flooding's threat model is "the attacker supplies KEYS (data) that the victim hashes", not "the attacker calls methods on the victim's dictionary". Anyone able to invoke this already has code execution in-process, at which point the hash is not the weak link. Do not, however, echo the result across a trust boundary — that WOULD hand out a collision oracle.
METHOD maxBucketDepth() RETURNS int64reads
Deepest bucket in the table — the clustering metric the adaptive tier bounds.
METHOD treeifiedBuckets() RETURNS int64reads
How many buckets have escalated to a red-black tree. Zero under normal load — non-zero means collisions got deep (the adaptive tier is doing its job). Exposed so the escalation is TESTABLE and observable, not a silent internal.
METHOD iterator() RETURNS ReferenceIterator[BinaryWord]reads
One BinaryWord per live entry, borrowed from this dictionary's key
pool. Valid only while the dictionary is unmodified: an insert may grow
the pool and a rehash may move it.
METHOD keys() RETURNS LinkedList[BinaryWord]reads
MODIFY METHOD insertCopy(REFERENCE BinaryWord key, REFERENCE V value) RETURNS STATUSmodifies
MODIFY METHOD insert(BinaryWord key, V value) RETURNS STATUSmodifies
METHOD lookupFast(REFERENCE BinaryWord key) RETURNS booleanreads
Dictionary.lookupFast — the interface-shaped (BinaryWord-keyed) peer of
the binary[] slice form above. K is BinaryWord for this class, so this
is the overload that satisfies the interface; the slice form stays for
the zero-copy call sites that already hold a buffer and a range.
METHOD lookup(REFERENCE BinaryWord key) RETURNS | MUTABLE REFERENCE Vreads
METHOD contains(REFERENCE BinaryWord key) RETURNS booleanreads
MODIFY METHOD remove(REFERENCE BinaryWord key) RETURNS | BinaryWordmodifies
The removed key is a word over this dictionary's own pool. A freed entry
is recycled through freeHead but its BYTES stay in the pool, so the
returned word reads correctly until the pool is next compacted.
METHOD equals(REFERENCE Dictionary[BinaryWord, V, H] other) RETURNS booleanreads
Equal when both hold the same keys mapped to the same values. Walks the smaller surface — this dictionary's entries — and asks the other by lookup, so the cost is one hash per key rather than a cross product. 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.
METHOD clone() RETURNS Dictionary[BinaryWord, V, H]reads
Deep copy. Returns the Dictionary INTERFACE, not the concrete class —
the class is HIDDEN, so its name may appear only as a CREATE target. The
copy goes in through the interface's own insert, since insertSlice
is this class's and not the interface's.