Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 3 / c

With a 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 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 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.