How do hash tables and arrays work?

In this article

1. Before you start
2. Why interviewers ask this
3. Hashing and arrays from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one rung of the coding interview questions path.

Why interviewers ask this

A wrong data-structure choice shows up as a program that works on ten inputs and stalls on ten million, so interviewers use array and hash questions to check that you know what each operation really costs. Candidates report prompts such as finding the number closest to the mean of a set, finding the one number that occurs once in an array of pairs, designing a structure with insert, delete and a random pick in constant time, and sorting a bitonic array.

A weak answer names a structure and says "O(1)". A strong answer says what the cost assumes, and what happens when the assumption fails. A Staff-level answer also names the cheaper structure when the data has extra shape, such as sorted order or paired values, and says what it would measure before deciding.

Hashing and arrays from first principles

Hash function

A hash function is a rule that turns a key into a whole number, the same number every time for the same key; a hash table then reduces that number to a bucket position (for example with a remainder).

Chaining

Chaining is a collision strategy that keeps a short list of key-value pairs in each bucket and walks that list, comparing keys, on every lookup.

Open addressing

Open addressing is a collision strategy that stores every pair in the table's own array and, on a clash, probes other slots in a fixed order until it finds the key or a free slot.

In plain words

Picture a row of numbered mailboxes. If you know the box number, you walk straight to it. That is an array. Now suppose you want to find a letter by the recipient's name, not by a box number. You apply a fixed rule that turns the name into a box number, and you always use that box for that name. That is a hash table. The analogy breaks at one point: two names can map to the same box, and then the box holds a small pile you must search by name.

In one precise sentence, an array finds an element by position in constant time, and a hash table finds a value by key in constant time on average by turning the key into a position.

Step 1: An array reads any position in one move

An array is a block of equal-sized slots in memory, numbered from zero, so the address of slot i is the start address plus i times the slot size. The computer does one multiplication and one addition, whatever the length. That is why getting or setting an item by index costs O(1), which the Python documentation lists for lists, and a CPython list is internally an array.

The cost moves elsewhere. The same page says the largest costs come from growing beyond the current allocation or from inserting or deleting near the beginning, because everything after that point must move. Amortized cost is the average cost per operation over a long run, with rare expensive steps spread across many cheap ones. In an illustrative run that doubles capacity when full, 16 appends copy 15 elements in total, about 1.94 moves per append.¹ CPython lists grow by a smaller constant factor, and any constant growth factor keeps the amortized cost constant. Input: a position. Output: the element. You now know why position is cheap and shifting is not.

Step 2: A hash function turns a key into a position

A key such as a name or a user id has no position, so the table makes one. The hash function turns the key into a whole number, and the table takes that number modulo the number of buckets. A bucket is one slot of the table's underlying array that holds the pairs sent there. With 7 buckets (illustrative), key 15 goes to bucket 1, because 15 divided by 7 leaves remainder 1, and key 10 goes to bucket 3.¹

Input: a key. Output: a bucket number. The rule must give the same number for equal keys, or a stored value could never be found again. In Python, a key must be hashable for this reason: a key is hashable when its hash never changes during its life and equal keys always have equal hashes, so a list cannot be a dict key. The defaultdict page shows the everyday dictionary built on hashing. The cost of a lookup is one hash plus one bucket visit, which the Python documentation describes as O(1) on average for a dict.

Step 3: Collisions turn one lookup into a chain walk

Two different keys can reach the same bucket, and then the bucket keeps a chain of pairs. Keys in one bucket form a chain that a lookup walks, comparing keys one by one. With keys 15, 22, 8, 29, 36 and 10 in 7 buckets (illustrative), bucket 1 receives five of the six keys, so finding key 36 takes five comparisons.¹

That is the condition behind "O(1)". The Python documentation says the dict times are average-case times that assume the hash function is good enough to make collisions uncommon and the keys well distributed. In the worst case, when every key hashes to the same value, each of those operations takes O(n) time instead. If all six keys shared one bucket, the last would take six comparisons.¹ Resizing (Step 4) fixes crowding; it cannot fix keys that share one hash value, because those collide at every table size. Only a better hash function fixes that.

Step 4: Resizing keeps chains short

The load factor is the number of stored keys divided by the number of buckets, and it measures how crowded the table is. In the example, six keys in 7 buckets is a load factor of 0.8571.¹ When the load factor passes a chosen limit, the table allocates more buckets and re-places every key, moving each pair to its position in the larger table. This is the same grow-and-copy cost as in the array step, and it is also paid rarely and spread out.

Re-spreading the same six keys over 17 buckets (illustrative) gives a load factor of 0.3529, a longest chain of one, and one comparison to find key 36.¹ Input: a crowded table. Output: a larger table with short chains. This is why a hash table is fast on average: it pays occasional resizes to keep chains short.

1 · Array2 · Hash function3 · Collision4 · ResizeReplay

Step-by-step description

1. An array reads a position in one move.
2. A key becomes a bucket number.
3. Keys in one bucket form a chain.
4. More buckets keep chains short.

• An array reads any position in one move.
• A hash function turns a key into a bucket number.
• Two different keys can reach the same bucket.
• Resizing spreads keys across more buckets.

Worked example

Five common prompts use the same two ladders. All inputs below are illustrative small arrays, and every result is computed in the saved script.¹

Closest to the mean: for the values 2, 9, 4, 10 and 15, the sum is 40 and the mean is 8.0 (illustrative input). The absolute distances from 8.0 are 6, 1, 4, 2 and 7, so the answer is 9.¹ One pass sums, one pass compares: linear time and constant extra memory.

The number that occurs once: exclusive or (XOR) is a bit operation that returns zero when applied to two equal numbers and leaves a number unchanged when applied with zero. XOR-ing 4, 7, 4, 9, 7 gives running values 4, 3, 7, 14 and 9, so the single number is 9, because every pair cancels. XOR is commutative and associative, so the order of the numbers does not matter and each pair cancels wherever it sits. A hash set also works in linear time but uses extra memory.

Two Sum: find two numbers that add to a target. For each number, check whether target minus number is already in the hash map, then insert the number. With 4, 9, 1, 6, 2 and a target of 8 (illustrative), the check succeeds at the fifth number, 2, because 6 is in the map at index 3; the answer is indices 3 and 4.¹

Text description of the diagram

• Finding key 36 takes five comparisons with 7 buckets.
• Finding key 36 takes one comparison with 17 buckets.

The constant-time delete in the table works because an array loses an element cheaply at its end. Swap the element to delete with the last one, update the index map, then pop the end; after deleting 20, the map says 10 is at 0, 40 at 1 and 30 at 2.¹

Trade-offs and edge cases

The structure you pick follows the question you ask, not habit. An array answers "what is at position i?" and a hash table answers "is this key here, and what is its value?" Neither is good at the other's job.

Text description of the diagram

• An array reads a position in one move.
• A hash table finds a key in constant time on average.
• Inserting at the front of an array shifts every element.

Edge cases to name aloud:

• Unsorted data and "O(log n)". Finding the one unpaired number in an unsorted array in logarithmic time is not possible, because every element must be read at least once. Logarithmic time works only if the array is sorted and paired: at the middle, check whether the pair lines up with its partner, then keep the half where the pairing breaks. In the sorted example, two probes find the 3 among nine elements.¹
• Bitonic arrays. A bitonic array is one that rises to a peak and then falls. Reverse the falling part and merge two sorted runs: linear time, with no general sort needed. In the example the peak is at index 3, and the reversed tail 3, 6, 10 merges with 1, 4, 9, 12.¹
• Constant-time random pick. Keep the elements in an array and a map from value to index. A random index gives the pick, and swap-with-last gives the delete. The reported wording "getRandomFrequent" does not say what "frequent" means, so ask before designing. For the obvious reading, a pick weighted by frequency, store every insertion in the array, duplicates included, and keep a map from value to the set of its indices. A uniform random index then returns each value with probability proportional to its count. Delete removes one index from that value's set, swaps the last array element into the gap, updates the moved element's index set, and pops. These are O(1) on average, because they rest on hash-map operations.
• Chaining versus open addressing. Chaining is the scheme in Steps 3 and 4; open addressing is the other collision strategy. Chaining degrades gradually as the load factor grows; open addressing needs the table kept less full, because probe sequences lengthen as slots fill, and deleting needs care so probe sequences stay intact. CPython's dict uses open addressing, not chains, as the dictionary implementation note describes. Either way the average cost depends on a good spread of keys.
• Hash quality in practice. Python Enhancement Proposal (PEP) 456, adopted in Python 3.4, gave string and bytes hashing a secure algorithm called SipHash. Hash randomization, described in the Python documentation for undefined and the undefined option, makes string hashes vary between runs, so an attacker cannot easily craft many colliding keys.
• Implementation differences. The Python tables describe CPython specifically, and the documentation notes that other implementations may differ. Say which language you assume.

A related pattern uses a hash map of running sums; see subarray sum equals k. A window version appears in longest substring without repeating characters.

How to answer it in an interview

The spoken structure: say the mechanism, name the collision, give the average cost with its condition, then state the worst case: resizing fixes crowding, but only a better hash function fixes keys that share one hash value.

Common mistakes

• "Hash lookup is O(1)." (wrong) It is O(1) on average under a good hash function; the Python documentation names O(n) for the case where every key hashes to the same value. (right) "Average constant time, worst case linear."
• "Append to a list is O(1) every time." (wrong) Growing beyond the allocation moves everything. (right) "Append is amortized constant time with an occasional resize."
• "Resizing the table fixes any slow lookup." (wrong) Keys with the same hash value collide at every size. (right) "Resizing fixes crowding; a better hash function fixes identical hashes."
• "Inserting at the front of an array is cheap." (wrong) Everything after it must move. (right) "Front insert shifts the whole array, so it is linear; I would use another structure if I need it often."
• "I can find the unique number in logarithmic time." (wrong) Not on unsorted data, since every element must be read. (right) "Linear with XOR or a set, or logarithmic only if it is sorted in pairs."

Follow-up questions

How do you find the number in a set that is closest to the mean of the whole set?

Sum the values, divide by the count, then scan once for the smallest absolute distance to that mean. It takes linear time and constant extra memory. Ask how ties are broken, since two values can be equally close.

Given an array of numbers where every number occurs twice except one, how would you find the unique number in O(log n) time?

On unsorted data you cannot, because every element must be read, so the honest answer is linear time with XOR or a hash set. On a sorted array with exact pairs, a binary search on pair alignment takes logarithmic time.

How do you design a data structure that supports insert, delete and getRandomFrequent in O(1) time?

Combine an array and a hash map from value to array index. Insert appends, delete swaps with the last element and pops, and a random pick uses a random index. Ask what "frequent" means; for a frequency-weighted pick, keep duplicates in the array and a set of indices per value. The times are O(1) on average, since they rest on hash-map operations.

How would you sort a bitonic array efficiently?

Find the peak, reverse the falling half and merge the two sorted halves in linear time.

Is hash lookup always O(1)?

No. The Python documentation gives O(1) as the average case and O(n) when every key hashes to the same value, which resizing cannot repair. See also Python interview questions and answers for related prompts.

Sources

1. Time complexity of operations on built-in types (Python documentation, dict section) — Python Software Foundation, 26 Oct 2026
2. How are dictionaries implemented in CPython? (Python design and history FAQ) — Python Software Foundation, 26 Oct 2026
3. PEP 456: Secure and interchangeable hash algorithm — Python Software Foundation, 27 Sep 2013
4. Command line and environment: PYTHONHASHSEED and the -R option — Python Software Foundation, 26 Oct 2026