Data Structures in Computer Science

Performance metrics for arrays, stacks, and hash tables

Introduction
Data structures form the foundation of efficient computer programs, determining how information is
organized, stored, and accessed in memory. The choice of data structure directly governs the
performance characteristics of an algorithm operating on that data, often making the difference between
a program that scales gracefully to millions of records and one that becomes unusably slow.
Understanding the performance metrics associated with fundamental data structures — arrays, stacks,
and hash tables — is essential for any computer scientist or software engineer seeking to write efficient,
scalable code. This discussion examines each structure's underlying implementation, its time and space
complexity across common operations, and the practical trade-offs that determine when each is the
appropriate choice for a given problem.

Performance in computer science is typically expressed using asymptotic notation, most commonly Big
O notation, which describes how the time or space required by an operation grows as the size of the
input, denoted n, increases. This abstraction allows engineers to reason about scalability independent of
hardware specifics, focusing instead on the fundamental growth rate of an algorithm's resource
consumption. While Big O notation captures worst-case or average-case behavior in the abstract,
real-world performance is also shaped by factors such as memory locality, cache behavior, and
constant-factor overhead, all of which are discussed alongside the formal complexity metrics below.

Arrays
An array is among the simplest and most fundamental data structures in computer science: a contiguous
block of memory divided into equally sized slots, each holding one element, and each accessible via a
numeric index. Because array elements occupy contiguous memory addresses, the address of any
element can be computed directly from the base address of the array and the element's index, using
simple arithmetic. This property gives arrays their signature performance characteristic: accessing an
element at a known index is an O(1) constant-time operation, regardless of the array's size, because no
traversal or search is required — the memory location is calculated directly.

Searching for a value within an array, as opposed to accessing a known index, behaves very differently
depending on whether the array is sorted. In an unsorted array, determining whether a value exists, or
finding its index, requires examining elements one at a time until a match is found or the array is
exhausted, giving a worst-case time complexity of O(n), since in the worst case every element must be
checked. If the array is sorted, however, binary search can be applied: by repeatedly comparing the
target value to the middle element of the remaining search range and discarding the half that cannot
contain the target, binary search locates an element in O(log n) time, a dramatic improvement for large
datasets. This illustrates a recurring theme in data structure performance: maintaining additional
structure, such as sort order, can be traded for significantly faster operations later, at the cost of more
expensive insertions to preserve that order.

Insertion and deletion performance in arrays depends heavily on where in the array the operation occurs.
Appending an element to the end of a dynamic array, one that automatically resizes as needed, is
typically O(1) amortized time; although resizing the underlying memory block when capacity is exceeded
is itself an O(n) operation, this cost is spread, or amortized, across many prior insertions, since resizing
happens infrequently and doubles capacity each time it occurs, so the average cost per insertion
remains constant. Insertion or deletion at an arbitrary position within the array, however, is an O(n)
operation in the worst case, because every element after the insertion or deletion point must be shifted
one position to maintain contiguity, an expensive operation for large arrays or insertions near the
beginning of the structure.

The space complexity of an array is O(n), proportional to the number of elements stored, with minimal
per-element overhead compared to structures that require additional pointers or metadata. This
compactness, combined with contiguous memory layout, gives arrays excellent cache locality: because
modern processors load data into cache in contiguous blocks, sequentially accessing array elements is
significantly faster in practice than the equivalent operation on a data structure whose elements are
scattered throughout memory, such as a linked list. This practical performance advantage often makes
arrays preferable even when a theoretically more flexible structure exists, particularly for read-heavy
workloads or numerical computing applications where sequential or near-sequential access patterns
dominate.

Stacks
A stack is an abstract data structure that enforces a Last-In-First-Out, or LIFO, access pattern: elements
are added and removed only from one end, referred to as the top of the stack. This restricted access
pattern models a wide range of real-world and computational scenarios, from the call stack that tracks
function invocations during program execution, to undo functionality in software applications, to the
evaluation of arithmetic expressions and parsing of nested structures such as parentheses or code
blocks.

The two fundamental stack operations, push (adding an element to the top) and pop (removing the top
element), are both O(1) constant-time operations regardless of the stack's size, because both operations
act exclusively on the top element and require no traversal or shifting of other elements. This is true
whether the stack is implemented using an underlying array, where the top corresponds to the last
occupied index, or a linked list, where the top corresponds to the head node. A closely related operation,
peek or top, which returns the top element without removing it, is likewise O(1), since it requires only
reading the value at a known location.

Searching for an arbitrary element within a stack that is not at the top is an O(n) operation, since a
stack's interface does not support direct indexed access to interior elements; determining whether a
value exists anywhere in the stack, in principle, requires popping elements one at a time until the target
is found or the stack is emptied, which is both slow and destructive to the stack's original contents unless
the popped elements are subsequently pushed back. This limitation reflects the fundamental design
philosophy of the stack: it deliberately sacrifices general-purpose access flexibility in exchange for
extremely fast, predictable performance on the narrow set of operations, push, pop, and peek, that its
use cases actually require.

Implementation choice affects the practical, if not asymptotic, performance of a stack. An array-based
stack, where push and pop act on one end of an underlying array, benefits from the same contiguous
memory and cache-friendly access patterns as arrays generally, but may incur occasional O(n) resizing
costs as the underlying array grows, amortized to O(1) per operation in the same manner as dynamic
array append operations. A linked-list-based stack, where each push allocates a new node and each pop
deallocates the top node, avoids resizing costs entirely and can grow without any theoretical upper
bound imposed by pre-allocated capacity, but incurs the overhead of dynamic memory allocation for
every push and suffers from poorer cache locality, since linked nodes are not guaranteed to reside in
contiguous memory.

Hash Tables
A hash table, also called a hash map, is a data structure that provides fast key-based access to values
by using a hash function to compute an index, or bucket location, from a given key, allowing values to be
stored and retrieved without a linear search through the entire collection. This mechanism gives hash
tables their defining performance characteristic: under favorable conditions, insertion, deletion, and
lookup operations by key are all O(1) on average, a dramatic improvement over the O(n) linear search
required by an unsorted array or the O(log n) required by a sorted structure with binary search, since the
hash function directly computes where an element should be located rather than requiring the structure
to be searched.

This average-case O(1) performance depends critically on the quality of the hash function and on
keeping the load factor, defined as the ratio of stored elements to the number of available buckets,
sufficiently low. A well-designed hash function distributes keys uniformly across the available buckets,
minimizing the likelihood that multiple distinct keys will hash to the same bucket, an event known as a
collision. In the worst case, however, if a hash function performs poorly, or if an adversary deliberately
chooses keys designed to collide, all elements may be forced into a single bucket, degrading every
operation to O(n), since the hash table effectively behaves like a single unsorted list in that pathological
scenario.

Collisions are inevitable in practice even with good hash functions, simply due to the pigeonhole principle
once the number of stored keys approaches or exceeds the number of buckets, and hash tables employ
one of two primary strategies to resolve them. Separate chaining resolves collisions by storing a small
secondary structure, typically a linked list or a small dynamically sized array, at each bucket, so that all
keys hashing to the same location are appended to that bucket's chain; lookup then requires hashing to
the correct bucket in O(1) time followed by a short linear search within that bucket's chain, which remains
fast on average as long as chains stay short. Open addressing, by contrast, resolves collisions by
probing for the next available bucket according to a defined sequence, such as linear probing, quadratic
probing, or double hashing, when the initially computed bucket is already occupied; this approach avoids
the memory overhead of secondary chain structures but requires careful handling of deletions, since
simply clearing a slot can break the probing sequence for subsequent lookups of other keys.

To maintain consistently fast average-case performance as a hash table grows, implementations

typically monitor the load factor and trigger a resize, or rehash, operation once it exceeds a chosen
threshold, commonly around 0.7 to 0.75. Rehashing involves allocating a new, larger underlying array of
buckets, typically double the previous size, and reinserting every existing key-value pair into the new
structure according to its hash value modulo the new bucket count. This rehashing operation is itself
O(n), since every element must be reprocessed, but because it occurs infrequently and roughly doubles
capacity each time, its cost is amortized across the many O(1) insertions that occur between resizes,
yielding an amortized O(1) average insertion cost overall, closely paralleling the amortized analysis used
for dynamic array growth.

Comparative Summary
Comparing these three structures highlights the fundamental trade-offs that pervade data structure
design. Arrays offer unmatched performance for indexed access and excellent cache locality but are
inflexible for insertion and deletion at arbitrary positions. Stacks offer the fastest possible performance,
O(1), for their narrow set of supported operations by deliberately restricting access to one end of the
structure, making them ideal for problems with an inherently LIFO structure but unsuitable for
general-purpose storage and retrieval. Hash tables offer near-constant-time access by key across a
much broader range of use cases than either arrays or stacks, at the cost of losing any inherent ordering
among elements, consuming more memory overhead per element than a plain array, and remaining
vulnerable to worst-case degradation if hash function quality or load factor is not carefully managed.
Selecting the appropriate structure for a given problem requires weighing these performance
characteristics against the specific access patterns, ordering requirements, and memory constraints of
the application at hand.

Practical Considerations Beyond Big O

Asymptotic complexity analysis, while indispensable for reasoning about scalability, does not fully
capture real-world performance, and practicing engineers must account for several additional factors
when choosing among these structures. Constant factors hidden within Big O notation can matter
enormously at the scales typical of real applications; an O(n) operation with a very small constant factor,
such as scanning a small, cache-resident array, can outperform a theoretically faster O(log n) or even
O(1) operation that carries substantial constant overhead, such as pointer chasing through a poorly
cache-localized structure or computing an expensive hash function. This is why, for small collections, a
simple array-based linear search is frequently faster in practice than a hash table lookup, despite the
hash table's superior asymptotic complexity.

Memory locality and cache behavior represent one of the most consequential practical factors
distinguishing these structures. Modern CPUs read memory in fixed-size blocks called cache lines, and
when a program accesses memory sequentially, as with array traversal, the processor can prefetch
upcoming cache lines before they are explicitly requested, dramatically reducing effective memory
latency. Hash tables and linked-list-based stacks, by contrast, often involve accessing memory locations
scattered unpredictably throughout the address space, defeating hardware prefetching and incurring the
full latency penalty of a cache miss on many operations, even when the asymptotic complexity of those
operations is nominally as fast or faster than the array-based alternative.

Amortized analysis, used above to describe dynamic array append operations and hash table insertions,
is itself a nuanced tool that averages cost over a sequence of operations rather than guaranteeing
uniform per-operation performance; a single unlucky insertion that happens to trigger a resize will take
substantially longer than a typical insertion, which matters for latency-sensitive applications, such as
real-time systems, where worst-case single-operation latency may be more important than average-case
throughput. Engineers working in such domains sometimes choose data structure variants specifically
designed to avoid amortization spikes, accepting somewhat worse average-case performance in
exchange for more predictable, bounded worst-case behavior on every individual operation.

Finally, the choice among arrays, stacks, and hash tables in practice is rarely made purely on
performance grounds; it also reflects the semantics of the problem being solved. A stack is chosen not
because it is faster than an array at arbitrary operations, but because its LIFO ordering directly models
the underlying problem, such as tracking nested function calls or matching parentheses. A hash table is
chosen not merely for its average-case speed, but because key-based lookup is the natural interface the
application requires. Effective use of these fundamental structures therefore requires understanding both
their formal performance characteristics and the structural fit between a given data access pattern and
the guarantees each structure is specifically designed to provide.