Array vs Hash Map: Which One for Fast Lookups?

If your keys are small, dense integers, use an array: indexing is a true O(1) address computation with the best cache behavior available. For anything else, strings, sparse numbers, or arbitrary objects, use a hash map, which gives average O(1) lookup by key at the cost of hashing, extra memory, and no built-in order.

What is the real difference?

An array is a contiguous block of memory. A lookup means computing an address, base plus index times element size, then doing one read. There is no comparison and no hashing, just arithmetic, and because the addresses are predictable the hardware prefetcher keeps the data in cache.

A hash map stores key-value pairs in buckets chosen by a hash of the key. A lookup means hashing the key, jumping to a bucket, and comparing keys to resolve collisions. It accepts any hashable key, but every one of those steps costs more than a bare array index, and the map deliberately keeps spare capacity so it can stay fast as it fills.

When does an array win?

An array wins whenever your keys are, or can be mapped to, a small contiguous range of integers. Counting lowercase letters? Index by ord(ch) - ord('a'). Marking which values in a bounded range you have seen? A boolean array beats a set. Filling a dynamic-programming table indexed by position? A list or 2D array is both faster and simpler than a dictionary keyed by tuples.

# Count lowercase letters with a fixed-size array
def char_counts(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - ord('a')] += 1
    return counts

This is O(1) per update with almost no constant factor, and it never rehashes. The tradeoff is that you pay for the whole range whether or not you use it: indices 0 through one million cost a million slots even if only ten are nonzero. When the range is small and dense, that is a bargain. When it is huge and sparse, it is waste.

When does a hash map win?

A hash map wins when the key space is large, sparse, or not an integer at all. Usernames, URLs, coordinate pairs, arbitrary integers with big gaps: the map stores only the keys you actually insert, so memory tracks the data rather than the range of possible keys.

# Two Sum: remember each value you have seen, keyed by value
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

Here the keys are unbounded integers, so an array indexed by value could need a slot for every number in range. The hash map holds only the values actually seen, which is why it is the standard answer to Two Sum and a hundred problems like it.

What about insertion and deletion?

Both structures handle these in amortized O(1) for the common cases, but the fine print differs. Appending to a dynamic array is amortized O(1) because it occasionally doubles capacity and copies, while inserting in the middle is O(n) because everything after it shifts. A hash map inserts and deletes by key in average O(1) anywhere, with no shifting, but it occasionally rehashes the whole table when it grows past a load threshold. If you insert in unpredictable key order and delete often, the hash map is usually the calmer choice.

What about ordering and worst cases?

Two things trip people up. First, a plain hash map has no meaningful order. If you need sorted keys, insertion order, or range queries, reach for a different structure: a sorted array, a balanced tree, or an ordered-map type. Some languages preserve insertion order in their default map, but sorted order is never free.

Second, hash-map O(1) is an average, not a promise. Adversarial keys or a weak hash can push lookups toward O(n) as buckets collide. Good hash functions make this rare in practice, but it is why systems that cannot tolerate a bad worst case sometimes prefer balanced trees with a guaranteed O(log n) bound.

The quick decision

Ask one question: can the key be a small dense index? If yes, an array is faster, lighter, and simpler, and you should use it. If no, reach for a hash map and treat the hashing and memory overhead as the fair price of looking things up by whatever key you actually have. When you also need ordering or a hard worst-case bound, step past both and use a sorted structure or a balanced tree.