HashTable

Hash-based key-value storage parameterized by key and value schemas.

Construct with key and value schemas before the type name: Key Value HashTable, for example Int32 Int32 HashTable.

`HashTable`

(keySchema valueSchema -- table) Constructs an empty owning table from key and value schemas.

Use schema objects such as Int32 or mutable prototype views such as @keyPrototype @valuePrototype; immutable prototype views can make find or at fail to compile when lookup instantiates the matching-node branch («set», Second argument (target) is of different schema). Use schema objects or mutable prototype views.
Stored key and value variables must support construction. Text is not a constructible stored item here; use String for owned text.

Fields

SCHEMA_NAME: static Text schema-name field built from the key and value schema names.
HASH_TABLE: static empty-Tuple marker.
Key: static NIL reference descriptor for the key schema.
Value: static NIL reference descriptor for the value schema.
Node: Block with effect (-- node) that constructs an object containing one key field of the key schema and one value field of the value schema.
data: array of bucket arrays containing Node values.
dataSize: Int32 count of stored nodes.

A new HashTable is empty. An immutable table source is copied using contained assignment operations; a mutable table can be moved, leaving the source empty. Destroying the table destroys its owned arrays, nodes, keys, and values, not objects merely referenced by contained reference fields.

Buckets have independent array storage. An insertion can move a bucket and invalidate its references even without changing the bucket count. Erasing can replace another slot in the same bucket. Reacquire references and iterators after any insertion or erasure, and after clear, release, assignment, or destruction.

`iter`

(-- iter) Returns an iterator of stored {key value} pairs.

next has effect (-- item valid). It yields an immutable key view and a value view whose mutability follows the table view.

`keys`

(-- iter) Returns an iterator of stored keys.

next has effect (-- item valid); it always yields immutable key views.

`values`

(-- iter) Returns an iterator of stored values.

next has effect (-- item valid); it yields value views whose mutability follows the table view.

`size`

(-- count) Returns the number of stored key-value pairs.

`at`

(key -- ref) Returns a view of the stored value, mutable through a mutable table and immutable through an immutable table.

A missing key reports Key is not in the collection with DEBUG enabled and exits with status 2; with DEBUG disabled it yields a NIL value reference that must not be dereferenced.

`find`

(key -- result) Returns a result record describing the key lookup.

result.success is TRUE when the key exists. result.value is a value reference whose mutability follows the table view; ordinary reads of a result field are immutable, while @r.@value retains the stored reference's view. The value reference is NIL when success is FALSE.

`erase`

(key --) Removes the stored pair with key.

On a nonempty table, a missing key fails with Erasing unexisting element! and terminates with status 2. On an empty table, erase is a no-op.

`insert`

(key value --) Constructs a stored pair from key and value.

With DEBUG enabled, inserting an existing key fails with Inserting existing element!; with DEBUG disabled, duplicate pairs are accepted.
Each input is copied or moved according to its view and construction support; mutable managed inputs can be moved from, immutable inputs are copied, and contained references retain aliasing.

`insertUnsafe`

(key value --) Inserts a pair without checking for an existing key.

Construction, growth, and invalidation follow insert; check for an existing key when unique keys are required.

`rebuild`

(bucketCount --) Redistributes the stored nodes over bucketCount buckets; the size counter is not changed.

bucketCount must be a positive Int32.
Normal growth uses powers of two (16, 32, ...). The bucket index is hash and (bucketCount - 1), so a count that is not a power of two leaves some buckets unused.
rebuild invalidates stored references and iterators.

Known issue: shrinking the bucket count destroys truncated buckets before rehashing, loses their pairs without correcting size, and leaves the table inconsistent; do not shrink the bucket count.

`clear`

(--) Removes stored pairs and sets the item count to zero.

Remarks

The outer bucket array retains its reserved allocation; stored pairs and their owned values are destroyed.

`release`

(--) Releases bucket storage and sets the item count to zero.

Implementation helper

`makeIter`

(buckets projection -- iter) Used by iter, keys, and values; builds an iterator over bucket-node storage, applying projection to each node.

The iterator retains the supplied storage view and has method, data, bucket, item, and next fields.
projection must consume a node and return one item; it is stored as a static field.
next has effect (-- item valid). On exhaustion it calls projection with a node containing NIL key/value references and returns its result followed by FALSE. Do not dereference those NIL references.

Key requirements and iteration order

Hash selection uses direct-cast overloads for fixed-width signed and unsigned integer keys.
Any other constructible key schema must provide a hash field or method that returns one Nat32 result; a table does not convert a custom hash. A key without a hash method, such as a Tuple, fails with All 11 predicates named «hash» did not match.
Equal keys must have equal hashes. Do not change a stored key's hash or equality while it remains in the table.
Keys are compared with =: an integer key uses the builtin; a Dict key with an equal method uses control's =; an iterable key uses algorithm's =.
A non-iterable Dict without equal fails with Built-in text, tuple, Iter, or Iterable expected.
Initially no buckets are allocated. The first insertion creates 16 buckets; before an insertion whose item count equals the bucket count, the bucket count doubles.
Iteration visits buckets in ascending bucket index and items in their current bucket-storage order. It is neither sorted-key nor insertion order.

`hash`

(object -- hashValue) Casts an integer input to Nat32, or returns the result of the input's hash field or method without converting it.

Signed and unsigned Int8, Int16, Int32, Int64, Intx, Nat8, Nat16, Nat32, Nat64, and Natx values use the integer casts. Other schemas use their .hash field or method.

`toHashTable`

(source -- hashTable) Builds an owning HashTable from an iteration source of key-value pairs.

Each item is a Struct of two fields (or a view of one): field 0 is the key and field 1 is the value. Field names are ignored; a Dict must declare those fields in that order. A Tuple such as (1 10) and the pairs yielded by another table's iter are accepted.
The first item returned by next supplies both schemas, even if its validity flag is FALSE; valid items are inserted in source order.
An empty source works when its end item supplies both field schemas. Duplicate handling is the same as insert.

Examples

Lookup and erasure

"HashTable" use
"String"    use
"control"   use

{} Int32 {} [
  h: Int32 Int32 HashTable;
  1 10 @h.insert
  2 20 @h.insert
  3 30 @h.insert
  r: 3 @h.find;
  ("size=" h.size LF
    "at2=" 2 @h.at new LF
    "found3=" r.success LF
    "value3=" @r.value new LF) printList
  2 @h.erase
  ("size2=" h.size LF) printList
  0
] "main" exportFunction

Expected Output

size=3
at2=20
found3=TRUE
value3=30
size2=2

Lookup of a missing key

"HashTable" use
"String"    use
"control"   use

{} Int32 {} [
  h: Int32 Int32 HashTable;
  1 10 @h.insert
  r0: 1 @h.find;
  r1: 5 @h.find;
  ("found0=" r0.success LF
    "value0=" @r0.value new LF
    "found1=" r1.success LF
    "size=" h.size LF) printList
  0
] "main" exportFunction

Expected Output

found0=TRUE
value0=10
found1=FALSE
size=1

Building from pairs

"HashTable" use
"String"    use
"control"   use

{} Int32 {} [
  t: ((1 10) (2 20)) toHashTable;
  ("size=" t.size LF
    "at2=" 2 @t.at new LF) printList
  0
] "main" exportFunction

Expected Output

size=2
at2=20

Runtime example: iter, keys, and values

"HashTable" use
"String"    use
"control"   use

{} Int32 {} [
  h: Int32 Int32 HashTable;
  1 10 @h.insert
  2 20 @h.insert
  pairs: @h.iter;
  pair0: ok0: @pairs.next;;
  pair1: ok1: @pairs.next;;
  pair2: ok2: @pairs.next;;
  keys: @h.keys;
  key0: hasKey0: @keys.next;;
  key1: hasKey1: @keys.next;;
  values: @h.values;
  value0: hasValue0: @values.next;;
  value1: hasValue1: @values.next;;
  ("pair0Key=" pair0.key LF
    "pair0Value=" @pair0.value new LF
    "pair1Key=" pair1.key LF
    "pair1Value=" @pair1.value new LF
    "iterDone=" ok2 LF
    "key0=" key0 LF
    "key1=" key1 LF
    "value0=" value0 new LF
    "value1=" value1 new LF) printList
  0
] "main" exportFunction

Expected Output

pair0Key=1
pair0Value=10
pair1Key=2
pair1Value=20
iterDone=FALSE
key0=1
key1=2
value0=10
value1=20

HashTable

Fields

Remarks

Implementation helper

Key requirements and iteration order

Examples

Lookup and erasure

Expected Output

Lookup of a missing key

Expected Output

Building from pairs

Expected Output

Runtime example: iter, keys, and values

Expected Output

See also