= Solution
With a \b[directly indexed <array>], use two parallel count <arrays>, or one <array> of count records, at each user identity. Both queries and increments take $O(1)$ <running time>, with no <hash collision>. However, reserving $10^8$ positions for each of two four-byte counters uses about $800$ million bytes, roughly $763$ MiB before object overhead, even when only a few users have payments. Index zero is unused and all valid positions initially contain zero.
With a \b[<linked list>], store one node `(user, countIn, countOut, next)` for each active user. A scan locates a record, returning zero counts if absent; an increment creates a missing record or updates its counter. Storage is $O(K)$ for $K$ stored users, but a query or update can require $O(K)$ <running time>. Nodes also carry pointer and allocation overhead and lack direct indexed access.
With a \b[<hash table> using <separate chaining>], compute a <hash bucket> from the user identity and store its record in that bucket's <linked list>. The same zero-default convention applies to a missing record. With $B$ buckets and a well-distributing <hash function>, the expected operation cost is $O(1+K/B)$ in terms of the <load factor of a hash table>; worst-case cost remains $O(K)$ under severe collisions. Storage is $O(B+K)$, but a permanently fixed $B=100$ cannot maintain constant expected cost as $K$ grows without bound. A good distribution and, where permitted, <hash table resizing> address that trade-off.
Back to article page
