Lesson 12 · Working with data

Collections

A collection keeps many values under one name. Follow a 13-line program: a List<int> stores its values in a hidden array, fills it, and when it is full makes a new array twice as big and copies across; a Dictionary<int, string> uses each key's hash code to pick a bucket, so TryGetValue goes straight to the right one. The program prints 85 Sara.

14 min11 steps5 questionsIntermediate

Fig 12 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A List<int> has Count 4 and Capacity 4. What happens when you call Add(95)?

An array cannot change size. When Count reaches Capacity, List<T> allocates a bigger array (in .NET 8, twice as big), copies the old values across and then adds the new one. The old array becomes garbage.

02scores holds 5 values and has Capacity 8. What does scores[6] do?

Capacity is spare room inside the list, not part of it. Valid indexes go from 0 to Count - 1; anything else throws ArgumentOutOfRangeException.

03In a new Dictionary<int, string>, which bucket does the key 205 go into?

An int's hash code is the int itself, and the first table has 3 buckets, so the bucket is 205 % 3 = 1. (This is how .NET 8 does it; string keys hash differently on every run.)

04Why is looking up a value by key in a Dictionary fast, close to O(1)?

A dictionary is a hash table. Hashing the key picks one bucket straight away, so the time does not grow with the number of entries (as long as keys spread out well).

05names already holds the key 205. What do names[205] = "Zed" and names.Add(205, "Zed") do?

A key appears only once. Setting through the indexer adds the key or replaces its value; Add insists on a new key and throws ArgumentException for a duplicate.

Key terms

Glossary

Collection: An object that holds many values under one name, such as List<T> or Dictionary<TKey, TValue> from System.Collections.Generic.
Generic type: A type with a type parameter in angle brackets, such as List<T>. List<int> fills T with int, so the list holds only ints and the compiler checks every use.
List<T>: An ordered collection you read by index (0, 1, 2 ...). It stores its values in an array and grows by itself.
Count and Capacity: Count is how many values a list holds; Capacity is how many fit in its current array before it must grow.
Dictionary<TKey, TValue>: A collection of key and value pairs. Each key is unique and maps to one value; lookups by key are close to O(1).
Hash code: A number computed from a value. A dictionary uses the key's hash code to pick the bucket where the pair is stored.
Bucket: One slot in a hash table. Keys whose hash codes give the same remainder share a bucket.
O(1) and O(n): Ways to describe cost: O(1) takes the same time whatever the size; O(n) grows with the number of items n.

Fine print

Notes and sources

The numbers 4 and "twice as big" come from the .NET 8 source of List<T> (an empty list starts with no array, the first Add makes 4 slots, then each growth doubles). The documentation only promises that the list reallocates and copies when Count reaches Capacity, so treat the exact sizes as an implementation detail. If you know the size up front, new List<int>(1000) allocates once.
O(1) "on average" (amortized): one Add that copies n values is paid for by the n cheap Adds before it, because the array doubles each time.
The dictionary picture is simplified. In .NET 8 the table really starts with 3 buckets (a prime) and picks bucket = hash code % 3, but the pairs live in a separate entries array that the buckets point into, and keys that land in the same bucket are chained together. A 4th key here would grow the table to the next prime size (7).
Only int keys hash to themselves. A string's hash code is randomised for each run of the program, so string keys land in different buckets each time; the lookup still works because the same run always hashes the same way.
The old array is not freed at once: it becomes unreachable, and the garbage collector reclaims it when it next runs.
The program is real C#. Put the 13 lines in Program.cs and dotnet run prints 85 Sara.

Quiz Unlocks after the last step.