An array is a fixed sequence of elements of the same type, laid out back to back in one contiguous block of memory. Because every element takes the same number of bytes, the array only needs to remember its starting address and its length.

That layout is why arrays feel so simple. The values sit next to each other in order, with no gaps and no pointers linking them. A five-element integer array is just five integers packed tightly, one after another.

The packing has real consequences. Reading nearby elements is fast, since the CPU pulls in whole cache lines at once. The cost is rigidity: the block is one piece, so you cannot cheaply grow it in place when neighboring memory is already taken.

A static array has a fixed size chosen when it is created, and that size never changes. A dynamic array can grow and shrink at runtime, resizing itself as you add or remove elements.

Under the hood, a dynamic array still uses a contiguous block. When that block fills up, it allocates a larger one and copies the elements across. You get flexibility, but occasional resize work happens behind the scenes.

Use a static array when you know the count ahead of time and want zero overhead. Reach for a dynamic array, like a Python list or a Java ArrayList, when the size is unknown or keeps changing. Access stays O(1) for both; only the growth behavior differs between them.

Doubling storage on overflow is how a dynamic array stays fast. When the underlying block fills up, the array allocates a new block, usually twice as large, copies every element over, and releases the old one.

That copy costs O(n), so a single resize is not cheap. The saving grace is that resizes get rarer as the array grows. Going from 8 to 16 to 32 slots means the gaps between resizes keep doubling.

Spread the total copy work across every append, and each one averages out to constant time. That is what amortized O(1) means: individual appends occasionally spike, but the long-run cost per append stays flat. Appending a million items in a row stays fast overall.

Indexing is a single arithmetic step, not a search. Because an array is a contiguous block of equal-size elements, the computer locates any element with one formula.

address = base_address + index * element_size

Give it the index and it computes the exact memory location directly. No scanning, no walking through earlier elements first. Element 0 and element 999 take exactly the same amount of work to reach.

This constant-time access is the array's headline feature. It holds no matter how large the array grows, which is why arrays back so many other structures. The one requirement is that every element be the same size, so the multiplication always lands on the right spot.

Inserting in the middle forces every later element to move. An array keeps its values packed with no gaps, so making room at position k means shifting everything from k onward one slot to the right.

If you insert near the front of a million-element array, you shift almost a million elements. That shifting is the O(n) cost, and it grows with how much sits after the insertion point.

Appending at the end avoids this, because nothing follows the last element. The same logic applies to deleting from the middle: the gap must be closed by shifting later elements left. When you need frequent middle inserts, an array is often the wrong tool.

A hash table maps keys directly to values, so you can find things without scanning. It solves the problem of slow lookups in a plain array, where finding a value by content means checking elements one by one.

The idea is to compute a key's storage slot from the key itself. A hash function turns the key into a bucket number, and the value lives in that bucket. Later you recompute the same number and jump straight there.

This turns lookup, insert, and delete into roughly constant-time operations instead of O(n) scans. Phone books, caches, database indexes, and language dictionaries all lean on it. When you need fast membership tests or key-to-value access, a hash table is usually the answer.

On average, a good hash function scatters keys evenly across all the buckets. That even spread means most buckets hold very few entries, so finding the right one takes a small, roughly constant number of steps.

Look up a key and the table computes its bucket in one shot, then checks the handful of entries there. With a low load factor, that handful is close to one. There is no dependence on the total number of stored items.

The word average matters. If many keys collide into the same bucket, that bucket becomes a long chain and lookup slows down. Good hash functions and controlled load factors keep collisions rare, which is what keeps the everyday cost at O(1).

A hash set stores only keys, while a hash map stores keys paired with values. Both use the same hashing machinery to place and find entries fast; the difference is what each slot actually holds.

A set answers one question: is this item present? You add values and later ask whether something is in the collection. A map answers a richer question: what value is associated with this key?

seen.add("alice");       // set: membership only
ages.set("alice", 30);   // map: key -> value

Reach for a set when you only care about presence or uniqueness, like tracking which items you have already processed. Reach for a map when each key needs an attached value. Under the hood, a set is often just a map with dummy values.

Two different keys landing in the same bucket is a hash collision. It happens because a hash function squeezes a huge space of possible keys into a small, finite number of buckets.

There are far more possible keys than slots, so by pigeonhole some keys must share a slot. Even a great hash function cannot avoid this; it can only make collisions rare and evenly spread. Poor functions make it worse by clustering keys together.

Collisions are normal, not a bug, so every hash table has a plan for them. Common approaches store the clashing entries in a small list per bucket, or probe for the next open slot. Handling them well is what keeps lookups near O(1) instead of degrading.

A string is an ordered sequence of characters, usually stored as bytes that encode text. In many languages it behaves like a read-only array of characters that you can index and iterate over.

Immutability means that once a string is created, its contents never change. Operations that look like edits, such as replacing a character, actually build a brand new string and leave the original untouched.

Languages make this choice for safety and speed. Immutable strings can be shared freely between threads with no locking, and their hash code can be computed once and reused. The tradeoff is that heavy in-place editing wastes work creating copies. That is why building text in a loop should use a dedicated builder instead.

The load factor is the ratio between the number of stored entries and the number of buckets. A table with 6 entries across 8 buckets sits at 0.75. It is a single number describing how crowded the table is.

Why care? As the load factor rises, more keys share buckets, so collisions and chain lengths grow. Lookups that were near constant start scanning longer chains. Implementations watch this number and resize once it crosses a set threshold.

A low load factor wastes memory on empty buckets. A high one wastes time on collisions. The whole point is to keep it in a healthy middle band so average operations stay near O(1).