← Back to list
Computing & Embedded
#해시함수#충돌해결#적재율#개방주소법#HashDoS
Last updated · 2026-11-15

Hash Table

1. Overview

A. Definition

A hash table is a data structure that converts a key into an array index via a hash function, performing insertion, lookup, and deletion in constant time O(1) on average; it resolves collisions—in which different keys map to the same index—through chaining or open addressing, and guarantees constant-time performance by keeping the load factor below a fixed threshold.

The idea behind the hash table is "don't search by comparing keys one by one; compute the storage location directly from the key itself." When looking up a name in a phone book, a person does not flip through pages from the front but guesses the position by the letters—"it starts with G, so it's near the front." The hash table pushes this intuition to the extreme, using a function that turns a key into a number to point at the exact array slot immediately. Unlike a search tree, which depends on the order (comparison) among keys and reaches O(log n), a hash table depends on the content (computation) of the key, driving the number of comparisons down to a constant independent of input size. This very shift from "comparison to computation" is the fundamental reason the hash table became the default associative container (hash map, dictionary, set) in nearly every language.

Yet this constant time is not free but conditional. If the hash function fails to distribute keys evenly or the load factor grows too high, collisions explode and worst-case performance collapses to O(n); add malicious input, and this escalates into a security problem known as a hash-collision attack (HashDoS). Therefore the core competence of a professional engineer dealing with hash tables lies in the engineering judgment to "design a good hash function and appropriate collision-resolution and rehashing policies so that average O(1) is actually achieved, while defending against the worst case and security threats."

B. Background and Necessity

The dictionary operation of finding data by key is one of the most frequent tasks in computing. Storing in an unsorted array or linked list makes lookup a slow O(n), while binary search on a sorted array is O(log n) but insertion and deletion cost O(n) due to element shifting. A balanced binary search tree ([[btree-bplus-index]], red-black tree, etc.) guarantees insertion, lookup, and deletion all in O(log n), but it slows down in proportion to log n as n grows and has poor cache efficiency from pointer chasing. The demand to "make key-based lookup fast regardless of input size" gave birth to the hash table, which converts keys directly into addresses.

The crucial point here is that the hash table is a classic trade-off that exchanges space for time. A direct-address table, which keeps one slot for every possible key value, achieves perfect collision-free O(1), but reserving four billion slots in advance for a single 32-bit integer key is impractical. The hash table solves this waste of space by keeping only "a small array (of size m) proportional to the number of elements actually stored (n)" and compressively mapping a vast key space into a small index space. The price is that collisions—different keys pointing to the same slot—become inevitable, and how well collisions are handled becomes the essence of hash table design.

Moreover, the fact that a large share of modern systems' performance bottlenecks are concentrated in key-value lookup further heightens the need for hash tables. A database's hash index and hash join ([[join-algorithm]]), an OS's page table and file descriptor management, a compiler's symbol table, a network router's flow table, in-memory caches like Redis and Memcached ([[caching-strategy]]), and the deduplication ([[data-deduplication]]) and aggregation of nearly every application all run on hash tables. In such environments, which must handle millions of lookups per second, the difference between O(log n) and O(1) becomes decisive when accumulated—which is precisely why the hash table holds the status of "the most widely used data structure."

2. Components and Operating Principle of the Hash Table

A hash table operates via the flow key space → hash function → index (bucket) → storage space. The structural diagram below shows the overall structure in which keys of arbitrary size are mapped through a hash function into a fixed-size bucket array and bound together by chaining on collision.

flowchart LR
    K1["key 'apple'"] --> HF["hash function h(key)"]
    K2["key 'grape'"] --> HF
    K3["key 'melon'"] --> HF
    HF --> IDX["index = h(key) mod m"]
    IDX --> B0["bucket0"]
    IDX --> B1["bucket1 → (apple) → (melon)"]
    IDX --> B2["bucket2 → (grape)"]
    IDX --> B3["bucket3"]
    B1 -. "same bucket = collision" .-> B1

The first core element of a hash table is the hash function. A good hash function must satisfy three things. First, determinism—the same key must always yield the same value for lookup to be possible. Second, uniformity—keys must be scattered across buckets as evenly as possible to minimize collisions. Third, efficiency—the function computation itself must be fast for O(1) to be meaningful. The hardest of these is uniformity: the property of scattering results without bias toward input key patterns (consecutive integers, strings sharing a common prefix, etc.)—that is, a distribution close to the avalanche effect—is required.

As representative hashing techniques, the division method h(k) = k mod m is simple to implement but sensitive to the choice of m. If m is a power of two, only the low bits are reflected and the distribution worsens, so a prime far from a power of two is usually chosen as m. The multiplication method h(k) = ⌊m·(k·A mod 1)⌋ (A is an irrational between 0 and 1, often golden-ratio based) is less sensitive to the choice of m. For string keys, a polynomial rolling hash accumulating each character as a polynomial (e.g., h = h·31 + c; Java's String.hashCode famously uses 31) or non-cryptographic hashes like FNV, MurmurHash, and xxHash are widely used. By contrast, to mathematically guarantee the distribution, universal hashing—choosing one function at random from a family—is used so that even for any specific input the collision probability is on average at most 1/m; this is also the theoretical foundation of the HashDoS defense discussed later.

Why the distribution quality of a hash function is decisive becomes clear through numbers. For example, if all integer keys are multiples of 10 and the division method is used with m=10, every key piles into bucket 0 and lookup immediately collapses to O(n). Conversely, changing m to a prime like 97 breaks the regularity of "multiples of 10," scattering keys evenly across 97 buckets. Since "whether the hash absorbs the input's hidden regularity" governs average performance, the designer must verify by measurement rather than assume the actual key distribution. In special cases where the key space and element set are fully known in advance, perfect hashing can even reduce collisions to zero: a two-level hash (dividing buckets with a top-level hash and processing each bucket with a collision-free secondary hash) guarantees O(1) lookup even in the worst case. Perfect hashing is actually used in "fixed-key" situations such as a compiler's reserved-word table or an unchanging key set (a static dictionary).

The second core element is index compression. The large integer produced by the hash function is reduced to the actual bucket number via the remainder of division by array size m (or bit masking). The third element is the bucket and storage strategy: how each bucket holds elements and handles collisions is the subject of Section 3. Ideally, if n elements are evenly placed into m buckets, the average number of elements per bucket becomes the load factor α = n/m, and lookup is "hash computation + an average of α comparisons within one bucket," so average O(1) holds as long as α is kept constant. Ultimately, hash table performance is jointly determined by the two axes of "the distribution quality of the hash function" and "load-factor management."

What must be distinguished here is average complexity versus worst-case complexity. A hash table's O(1) is strictly an expected value under the probabilistic assumption that "keys are evenly distributed," and in the worst case where all keys pile into one bucket, lookup becomes O(n). In this respect it fundamentally differs from a balanced tree, which always guarantees O(log n) for every operation. Thus when evaluating a hash table, one must consider not only average performance but also "how bad the worst case is, and whether that worst case can be maliciously induced"—a question that becomes the design motivation for the treeification, perfect hashing, and HashDoS defense discussed later.

3. Collision-Resolution Techniques and Load-Factor Management

No matter how good the hash function, if the key space is larger than the number of buckets, collisions are inevitable in principle. As the birthday paradox shows, inserting merely around √m elements into m buckets causes a collision with 50% probability, so collisions must be designed as an "ever-present task to handle" rather than an "exception." Collision resolution is broadly divided into separate chaining and open addressing.

flowchart TB
    COL["collision: h(k1)=h(k2)"] --> M{"resolution method"}
    M -->|"store outside bucket"| CH["separate chaining(Chaining)"]
    M -->|"store inside bucket array"| OA["open addressing(Open Addressing)"]
    CH --> CHD["bind with linked list / tree"]
    OA --> LP["linear probing"]
    OA --> QP["quadratic probing"]
    OA --> DH["double hashing"]
    CHD --> LF{"load factor α exceeded?"}
    LP --> LF
    QP --> LF
    DH --> LF
    LF -->|"yes"| RH["rehash: double array then relocate"]
    LF -->|"no"| OK["keep constant time"]

A. Separate Chaining

Separate chaining uses each bucket as the head of a linked list (or dynamic array/tree), hanging all elements mapped to the same bucket on that list. Insertion adds to the front of the list in O(1), while lookup and deletion linearly search that bucket's list and are therefore O(α) on average. If load factor α is kept constant, average O(1) is guaranteed, and the robustness that operation does not break but merely slows gently even when α exceeds 1 (more elements than buckets) is a major advantage of chaining.

The strengths of chaining are that deletion is simple (removing a node from the list), load factors above 1 are tolerable, and it does not suffer from "clustering" as open addressing does. On the other hand, each element carries a pointer, so memory overhead is large, and list nodes scattered around memory give poor cache locality, so real performance may fall short of the theoretical figure. A representative practical case is Java's HashMap: since Java 8, when collisions in one bucket exceed 8, the linked list is converted to a red-black tree (treeify), lowering the worst case from O(n) to O(log n). This is a measure to defend against HashDoS attacks that pile collisions into a specific bucket via malicious input—a good example of the hybrid strategy "chaining on average, tree in the worst case."

In actual numbers, placing n=750 elements into m=1,000 buckets by chaining gives α=0.75, an average of 0.75 elements per bucket—that is, lookup ends in fewer than one comparison on average. But if the hash function is poor and all keys pile into one bucket, that bucket's list length becomes 750 and lookup collapses to O(n); treeification rescues exactly this case. Thus chaining is a safe default that is "fast on average and does not collapse even in the worst case," which is why many standard libraries adopt it.

B. Open Addressing

Open addressing stores elements inside the bucket array by finding an empty slot, without a separate list. On collision, it examines the next slots in turn according to a fixed rule (the probe sequence) and places the element in an empty one. Linear probing moves one slot at a time as h(k), h(k)+1, h(k)+2, …; it is simple to implement and has outstanding cache locality, but consecutive slots clump together into primary clustering, producing long probe chains. Quadratic probing widens the interval as h(k)+1², h(k)+2², … to mitigate primary clustering, but secondary clustering—keys with the same initial position following the same path—remains. Double hashing determines the probe interval itself by a second hash function h₂(k), moving as h(k)+i·h₂(k), reducing clustering most effectively so the distribution approaches universal hashing.

To trace the concrete behavior with linear probing, suppose m=8 and h("cat")=3, h("dog")=3, h("ant")=4. "cat" goes into empty slot 3; "dog" finds 3 occupied, looks at 4, which is empty, and is stored at 4. Then "ant" finds h=4 already filled by "dog" and is pushed to 5. The way keys with different initial hash values (3 and 4) clump into one cluster (3-4-5) is primary clustering, and the longer this cluster grows, the longer the probe chains of subsequent insertions and lookups become together. This is exactly why quadratic probing or double hashing widens the probe interval to scatter this clumping.

Open addressing has no pointers, so memory is dense and cache efficiency high, often making it faster than chaining on modern CPUs. Instead, deletion is tricky—simply erasing an element breaks the probe chain passing through that slot so later elements cannot be found, so one must leave a "deleted (tombstone)" marker in the deleted spot or pull back a later element. Also, the load factor cannot exceed 1, and once α exceeds 0.7–0.8, probe chains lengthen abruptly and performance collapses steeply. Python's dict uses a probe sequence that adds perturbation to open addressing, and Rust's and Google's SwissTable (Abseil) is famous for its modern design that examines the metadata of several slots at once with SIMD atop open addressing to lower probing cost.

C. Load Factor and Rehashing

The common mechanism underpinning the performance of both methods is load-factor management and rehashing. When load factor α = n/m exceeds a threshold (often 0.75 for chaining, 0.5–0.7 for open addressing), a larger array (usually double) is newly created and all elements are rehashed and relocated. A single rehash looks expensive at O(n), but growing the array by doubling keeps the total rehashing cost over n insertions at O(n), so amortized it maintains O(1) per insertion. This amortized analysis follows the same principle as the expansion of a dynamic array (ArrayList, vector) and is the secret to a hash table keeping "average O(1)" to the end.

However, rehashing makes one particular insertion spike to O(n), worsening tail latency in real-time, low-latency systems. To avoid this, Redis uses incremental rehashing, moving buckets to the new table a little at a time on each lookup or update rather than all at once, flattening the latency. Also, whether to size the table as a prime or a power of two at rehash time, and whether to allow shrinking, are design variables that govern the balance of memory and latency. Thus the load-factor threshold and rehashing strategy are key tuning points that simultaneously determine a hash table's average performance, worst-case latency, and memory usage.

Often overlooked in practice is the effect of pre-sizing. If the number of elements to hold can be roughly known, the table can be made large enough from the start to avoid rehashing altogether. For example, if it is clear that one million items will be inserted but one starts with the default size (16 or so), about 20 rehashes occur during growth and unnecessary copying accumulates; specifying the capacity at creation (Java new HashMap<>(expectedSize), Go make(map[K]V, n)) eliminates this cost at once. But making it excessively large wastes memory and lowers cache efficiency, so the balance of taking "expected element count ÷ target load factor" as the initial capacity is recommended.

4. Comparison: Collision-Resolution Methods and Alternative Data Structures

The choice between the two collision-resolution methods inside a hash table, and between a hash table and a search tree, diverges according to "what is being optimized." The table below organizes those differences, but the fundamental reason the differences arise lies in where and how the data is placed.

Category Separate Chaining Open Addressing
Storage location List/tree outside bucket Inside bucket array
Load-factor limit α>1 allowed (gentle degradation) α<1 required, 0.7 recommended
Cache locality Low (pointers scattered) High (contiguous memory)
Deletion Simple (node removal) Complex (tombstone needed)
Memory overhead Extra pointers Empty-slot slack
Clustering None Occurs in linear/quadratic probing

The performance reversal between chaining and open addressing stems from the memory hierarchy. In theory both are average O(1), but on modern CPUs a single cache miss costs hundreds of clocks, so open addressing—which linearly probes a contiguous array—is often faster in measurement than chaining, which chases a list scattered along pointers. Conversely, if elements are large or deletions are frequent and a high load factor is desired, chaining is advantageous. Therefore the two must not be equated just because "their theoretical complexity is the same"; one must choose by weighing cache behavior, element size, deletion frequency, and target load factor together.

How the choice between the two methods diverges in practice is vividly revealed in language standard libraries. Java's HashMap and C++'s std::unordered_map default to chaining, designed to be robust to deletion and high load factors, whereas Python's dict, Rust's HashMap, and Google's Abseil flat_hash_map choose open addressing to maximize cache efficiency and lookup speed. The reason internal strategies differ even under the same name "hash map" is that each language assumes different typical workloads (deletion frequency, element size, degree of exposure to external input) and hardware. Therefore performance must not be prejudged on the assumption that "all hash maps are the same"; confirming the internal strategy and load-factor policy of the implementation in use is the starting point of performance tuning.

The comparison between a hash table and a balanced search tree ([[btree-bplus-index]], red-black tree) is more fundamental. A hash table is faster at average O(1) than a tree's O(log n), but has the decisive constraint of not preserving order. If range queries ("all keys between 100 and 200"), sorted traversal, min/max lookup, or nearest-key search are needed, a hash table becomes an O(n) full scan in every case and the tree is overwhelmingly advantageous. So a database index chooses a hash index for equality lookups only and a B+tree index when range queries are mixed in. Also, because a hash table has worst-case O(n) and rehashing latency, in real-time systems where worst-case latency matters, a tree that always guarantees O(log n) is more predictable. In short, "hash if equality lookup and average speed are the priority; tree if order, range, and worst-case guarantees are the priority" is the judgment criterion for a professional engineer's answer.

5. Advanced: Modern Hash Tables and Security

Since the 2000s, the classic hash table has evolved greatly to meet demands for worst-case guarantees and multicore and security. The first current is advanced open addressing that drives worst-case performance down to a constant. Cuckoo hashing keeps two or more hash functions and tables so that each key resides in only "one of the two slots," and when a slot is full it evicts the existing element to another table (like a cuckoo stealing a nest) and relocates it, thereby achieving worst-case lookup O(1) (a constant number of checks). Robin Hood hashing relocates elements to "yield the spot to an element with a long (poor) probe distance," reducing the variance of probe distance and improving tail latency, and hopscotch hashing gathers elements within a neighborhood near their original bucket, aiming for cache efficiency and worst-case guarantees simultaneously. These are products of the modern concern "the average is already fast, so let's tackle the worst case and latency variance."

The second current is the concurrent hash table. On multicore, protecting the entire table with one giant lock kills parallelism, so Java's ConcurrentHashMap finely splits locks per bucket (or segment) (see [[process-synchronization]]) and mixes in lock-free operations like CAS to minimize contention even when dozens of threads access it concurrently. In particular, through techniques such as having multiple threads share the rehashing or handling reads without locks (through volatile visibility alone), it attains nearly linear scalability on read-centric workloads. This shows that the hash table has extended beyond a single-threaded data structure to a foundation of high-performance parallel systems.

The third current is security. When an attacker sends a mass of keys that all map to the same bucket, the hash table degenerates to O(n) and exhausts the CPU—a HashDoS (hash-flooding) attack that became real in several web frameworks in 2011. At the time, most web stacks—PHP, Java, Python, Ruby, ASP.NET, etc.—placed HTTP POST parameters into a hash table (associative array), and an attacker sending just one request containing tens of thousands of colliding keys could make the server consume tens of seconds of CPU to parse that single request, paralyzing the service with only a handful of requests (CVE-2011-4815, etc.). This event impressed that the security principle "do not trust input" must apply even to a data structure's distribution assumptions. As a defense, SipHash, a keyed hash that mixes the hash with a secret key per process, became standard, preventing attackers from predicting or inducing collisions. Python, Rust, Ruby, and others adopting SipHash or its variants as the default hash is representative, and Java HashMap's treeification is a mitigation in the same vein. That "a performance data structure's distribution assumption" can itself become a security surface is an important advanced topic showing that hash table design borders on the realm of security engineering beyond algorithms.

Finally, the applications of the hash table go beyond the data structure. A database's hash join builds a hash table from the small table and joins by scanning the large table once; Bloom filters ([[bloom-filter]]), Count-Min sketch ([[count-min-sketch]]), and HyperLogLog ([[hyperloglog]]) extend hashing into probabilistic data structures to dramatically reduce memory; and consistent hashing ([[consistent-hashing]]) minimizes relocation on node changes in distributed caches and sharding. At the root of all these techniques lies the hash table's core idea of "mapping a key to a location by computation." That is, the hash table is not only the most widely used data structure in itself but also the common foundation of countless advanced techniques reaching into probabilistic data structures, distributed systems, and database engines—so it should be understood as a design principle far beyond the scope of a single data structure.

6. Considerations and Implications

When carrying the principles, techniques, and evolution examined so far into real system design, a professional engineer must judge hash function, collision resolution, load factor, security, and concurrency comprehensively in order to actually achieve the textbook performance of "average O(1)." The following are the key considerations.

  • Verify the hash function's distribution quality against data characteristics. Since average O(1) stands on the assumption that "keys are evenly distributed," one must measure whether the hash function yields a uniform distribution for actual key patterns (consecutive IDs, common prefixes, skewed distributions). Monitor metrics such as bucket occupancy, maximum chain length, and collision rate, and if the distribution is poor, consider adopting a hash function (MurmurHash, xxHash, etc.) or universal hashing to exclude latent performance defects that slow down only for specific inputs.

  • Choose the collision-resolution method by workload and hardware. If deletions are frequent, a high load factor is used, and elements are large, chaining is advantageous; if it is lookup-centric and cache efficiency and low latency matter, open addressing (especially linear probing, SwissTable) is advantageous. Even with the same theoretical complexity, cache behavior decides measured performance, so decide by confirming the target CPU, element size, and deletion frequency through benchmarks.

  • Manage latency through the load-factor threshold and rehashing strategy. Setting the load factor low is fast but wastes memory; setting it high is dense but increases collisions (around 0.7 is the inflection point for open addressing). In low-latency systems where the O(n) latency spike of rehashing is a problem, flatten tail latency with Redis-style incremental rehashing or pre-sizing, and design to guarantee average O(1) through amortized analysis.

  • Defend against the security threat (HashDoS) by default. Every hash table that takes external input as keys (HTTP parameter, JSON, header parsing, etc.) can be degenerated to O(n) by an attacker inducing collisions, so use a keyed hash like SipHash by default and cap the number of elements per bucket (treeification, rehashing) to limit the worst case to constant or logarithmic. Reflect at the design outset the view that a performance data structure's distribution assumption is itself an attack surface.

  • When order/range requirements exist, run alternative data structures in parallel. A hash table is optimal for equality lookup but cannot support range queries, sorted traversal, or min-value lookup. When such requirements are mixed in, use a B+tree or skip list ([[skip-list]]) together, or in a database select between a hash index and a B+tree index by query type, combining data structures to handle each operation at appropriate complexity.

  • In concurrent environments, apply lock splitting and lock-free design. On multicore, protecting the table with one global lock kills parallelism, so reduce contention with per-bucket/segment lock splitting or CAS-based lock-free operations (ConcurrentHashMap, etc.), and choose a design that guarantees the consistency (visibility, atomicity) of concurrent access during rehashing, securing scalability for read-centric workloads.

  • Eliminate initial cost through pre-sizing that reflects the expected scale. If the number of elements to hold can be gauged, specify the capacity at creation as "expected element count ÷ target load factor" to eliminate repeated rehashing during growth; conversely, if the scale is uncertain, start conservatively to avoid wasting memory. On batch/initialization paths where bulk loading is expected, this one-line capacity hint greatly governs overall throughput, so make it a basic checklist item of performance design.

In summary, the hash table is the most widely used data structure in computing, providing average-O(1) dictionary operations with the simple idea of "mapping a key to a location by computation." But that constant time is realized only when the engineering conditions of a good hash function, appropriate collision resolution, and load-factor management are in place, and it easily collapses if the real-world variables of worst case, rehashing latency, HashDoS, and concurrency are not handled. The professional engineer must diagnose data characteristics and workload to design the hash function and collision-resolution and rehashing policies, combine with a tree when order is required, and with comprehensive design competence encompassing security and concurrency, turn "conditional constant time" into "actual constant time."

References


In one line: A hash table maps a key to an array index via a hash function to perform insertion, lookup, and deletion in average O(1); it resolves collisions through chaining or open addressing, keeps the load factor below a threshold, and preserves amortized O(1) through rehashing—but only by engineering the conditions of the hash function's distribution quality, the worst case, rehashing latency, HashDoS, and concurrency does "conditional constant time" become "actual constant time."