Resizable Associative Store

Problem

An associative store maps each key to one value. Design ResizableAssociativeStore for signed 64-bit integer keys and string values, with collision handling, deterministic capacity growth, removal, and sorted detached snapshots. The index itself must not use a built-in associative container.

Requirements

Key identity. Keys are equal only when their signed numeric values are equal, and distinct colliding keys remain independent entries.
Insert or replace. put inserts a missing key and returns INSERTED, or replaces an existing value and returns REPLACED without changing size or capacity.
Missing behavior. get and remove return found=false, value="" for a missing key, which is distinct from a present key whose value is empty.
Correct removal. Removing a present key returns its prior value, decreases size once, and leaves every other entry reachable. Removing a missing key changes nothing.
Deterministic growth. Before a missing-key insertion, capacity doubles repeatedly while the projected size would make 4 × size > 3 × capacity. Equality does not grow, and removal never shrinks capacity.
Resize preservation. Growth preserves every key-value pair and assigns each key to its bucket for the new capacity using floor modulus.
Stable snapshot. snapshot returns detached entries in ascending signed-key order.
Custom storage. Store indexing must not use a built-in associative container. Arrays, lists, sequences, sorting utilities, and scalar helper objects are allowed.

API

Signature	Returns	Behavior
`ResizableAssociativeStore(initialCapacity: integer)`	Not applicable	Creates an empty store. The capacity must be from 1 through 65,536; otherwise construction raises the runtime's invalid-argument exception.
`put(key: int64, value: string)`	`string`	Inserts or replaces the key and returns `INSERTED` or `REPLACED`.
`get(key: int64)`	`LookupResult`	Returns a detached result containing `found` and `value` without changing state.
`remove(key: int64)`	`LookupResult`	Removes and returns a present value, or returns the missing result without changing state.
`size()`	`integer`	Returns the number of live keys.
`capacity()`	`integer`	Returns the current bucket capacity.
`snapshot()`	`StoreEntry[]`	Returns detached `key` and `value` entries sorted by ascending key.

LookupResult has fields found: boolean and value: string. StoreEntry has fields key: int64 and value: string. For key k and capacity c, the bucket index is the mathematical floor modulus:

[ ((k \bmod c) + c) \bmod c ]

Examples

Starting with ResizableAssociativeStore(4):

Step	Operation	Result
1	`put(1, "a")`	`INSERTED`; size 1, capacity 4
2	`put(5, "b")`	`INSERTED`; size 2, capacity 4
3	`put(9, "")`	`INSERTED`; size 3, capacity 4
4	`put(5, "B")`	`REPLACED`; size 3, capacity 4
5	`put(13, "d")`	`INSERTED`; capacity becomes 8
6	`snapshot()`	`[(1, "a"), (5, "B"), (9, ""), (13, "d")]`
7	`remove(9)`	`found=true, value=""`
8	`get(9)`	`found=false, value=""`; size 3, capacity 8

At capacity 4, keys 1, 5, and 9 collide and remain distinct.

Constraints

Initial capacity is from 1 through 65,536.
Keys are from -1,000,000,000,000 through 1,000,000,000,000.
Values contain from 0 through 200 Unicode scalar values and are non-null.
A testcase has at most 50,000 actions and 25,000 live keys.
Threshold and growth arithmetic must not overflow the runtime integer type.
Expected average cost is $O(1)$ for put, get, and remove; resizing is $O(n)$ ; snapshot is $O(n \log n)$ .
Memory allocation failure is outside scope.

Notes

Calls on one instance are sequential. Each testcase uses one thread and preserves its action order. Different instances share no state. Concurrent calls, null values, automatic shrinking, live iterators, custom equality or hashing, persistence, serialization, and manual capacity control are outside scope. Python dict and set, Java Map and Set implementations, C++ ordered or unordered map and set containers, and equivalent associative wrappers are forbidden as store indexes.