Hash Table
A key-value structure that uses a digest of the key to index an array of buckets.
Hash table maps keys to values by computing a digest of each key with a Hash Function and using it to index an array of buckets. Insert, lookup, and delete are constant time on average, which makes it the default associative container in most languages. Writing the same key and value twice leaves the table unchanged, so writes are naturally idempotent — see Idempotence.
Collisions are unavoidable, since there are more possible keys than buckets. Chaining keeps a list or small tree per bucket: simple, tolerant of a full table, hard on the processor cache. Open addressing probes later slots instead, keeping data contiguous and fast, at the cost of tombstone records for deletion and steep degradation as the table fills.
Load factor — entries divided by buckets — governs growth. Past a threshold, collisions climb, so the table allocates a larger array and rehashes every entry: a linear operation that surfaces as a latency spike, the amortized caveat from Big-O Notation in practice. The worst case, every key in one bucket, is reachable deliberately, so runtimes that accept untrusted keys seed the hash per process, trading Determinism of iteration order for resistance.
A purpose-built map is not a plain object. In JavaScript an object coerces every key to a string, so 1 and "1" collide and any object key becomes "[object Object]"; it inherits entries from its prototype chain, so an unguarded lookup for "constructor" succeeds on an empty object, a reliable Silent Failure; and it iterates integer-like keys first in ascending order regardless of insertion. A Map preserves key identity, holds nothing inherited, and iterates in insertion order.
Hash tables promise no ordering. Where ranges or sorted traversal matter, a sorted array with Binary Search or a B-tree index in a Relational Database is the right shape.
See also3
Least Recently Used Cache
A fixed-capacity cache that evicts whichever entry has gone untouched the longest.
Computation & Algorithms13 connections
Iterator
An object that hands out the elements of a collection or sequence one at a time on request, separating how a sequence is produced from how it's consumed, which lets the same loop walk arrays, trees, files and infinite streams.
Computation & Algorithms7 connections
Top-Level Domain
The last part of a domain name, such as .com or .uk, organized in 1984 into a handful of generic names plus one per country, then opened to over a thousand new names and a source of income for some small nations.
Networks & Distribution7 connections
Linked from18
- Amortized AnalysisComputation & Algorithms
Averaging cost over a sequence of operations so occasional expensive ones don't distort the per-operation bound.
- B-TreeComputation & Algorithms
A self-balancing tree with many children per node, designed to minimize the number of disk reads a lookup costs.
- Big-O NotationComputation & Algorithms
A coarse language for how an algorithm's cost grows as its input grows.
- Binary SearchComputation & Algorithms
Finding a value in a sorted range by repeatedly discarding half of it.
- Bloom FilterComputation & Algorithms
A probabilistic set membership structure that can say "definitely not present" but only "probably present."
- Consistent HashingComputation & Algorithms
A hashing scheme where adding or removing a node remaps only a small fraction of keys, not nearly all of them.
- Database MigrationData & Content
A versioned, ordered change to a database schema, applied once and recorded.
- Denial-of-Service AttackNetworks & Distribution
Making a service unavailable by overwhelming it with traffic or expensive requests, usually from many machines at once, and the layered defenses that absorb or filter the flood.
- GenericsComputation & Algorithms
Writing code once over a type variable so it works for any type, how languages implement it by erasure or by copying, and what constraints on type parameters buy.
- Hash FunctionSystems & Tooling
A function mapping arbitrary input to a fixed-size digest, used for identity, integrity, and addressing.
- ImmutabilityComputation & Algorithms
A value that cannot change after construction, so sharing it never risks a caller seeing another caller's edit.
- IteratorComputation & Algorithms
An object that hands out the elements of a collection or sequence one at a time on request, separating how a sequence is produced from how it's consumed, which lets the same loop walk arrays, trees, files and infinite streams.
- Key-Value StoreData & Content
The simplest kind of database, which stores opaque values under unique keys and supports little more than get, put and delete, trading query power for speed and easy scaling.
- Least Recently Used CacheComputation & Algorithms
A fixed-capacity cache that evicts whichever entry has gone untouched the longest.
- Prototype PollutionWeb Platform
A JavaScript vulnerability where attacker-controlled keys like "__proto__" modify the prototype every object inherits from, silently adding properties everywhere, and how merge utilities and parsers let it in.
- Seed DataData & Content
Initial content created programmatically to make an empty system usable or demonstrable.
- TrieComputation & Algorithms
A tree that stores strings by shared prefix, so each node represents a prefix all its descendants extend.
- Write-Ahead LoggingComputation & Algorithms
Recording the intent of a change durably before applying it, so a crash can be recovered.