A hash table stores data in an associative manner, arranging values in an array format where each data value has its own unique index. Hashing is the process of converting a given key into a numeric value that is then used as that index. When two different keys hash to the same index, a collision occurs. Collisions are commonly resolved in two broad ways: chaining, which stores a linked list of all colliding entries at that index, and open addressing, which probes for another available slot using linear probing, quadratic probing, or double hashing. Beyond standard hash tables, consistent hashing is a technique that minimizes the number of keys that must be remapped when a hash table is resized, making it especially valuable in distributed systems where servers may be added or removed dynamically. Universally Unique Identifiers (UUIDs) and Globally Unique Identifiers (GUIDs) are 128-bit labels that, in the context of data structures and algorithms, are used as keys where collision probability must be negligible even without central coordination.
Several data structures extend hashing into the realm of probabilistic answers, where absolute accuracy is traded for significant savings in space or query time. A Bloom filter is a space-efficient probabilistic structure that tests set membership: false positive matches are possible, but false negatives are not, so if the filter reports that an element is not in the set, it definitely is not. A cuckoo filter is a related probabilistic structure that supports dynamic addition and removal of items and achieves higher space efficiency than a Bloom filter. A skip list is a probabilistic alternative to balanced trees that provides \(O(\log n)\) search and insertion within an ordered sequence by using multiple levels of linked lists with random promotion. A disjoint set, also called a union-find or DSU, is a data structure that tracks elements partitioned into disjoint subsets, providing near-constant-time operations (bounded by the inverse Ackermann function) for adding sets, merging them, and testing whether two elements are in the same set, with Find determining the subset of an element and Union joining two subsets.
More specialized probabilistic structures support streaming, similarity, and spatial computations. HyperLogLog is an algorithm that approximates the number of distinct elements in a multiset using very little memory, making it a workhorse for count-distinct problems in big data. Count-Min Sketch is a probabilistic frequency table of events in a stream that uses hash functions to map events to frequencies; because multiple events may collide, it can overestimate counts. MinHash is a technique for quickly estimating the Jaccard similarity coefficient between two sets. Geohashing is a public domain geocode system that encodes a geographic location into a short hierarchical string of letters and digits; compared to a quadtree, a geohash effectively linearizes the 2D grid into a string and is often implemented using Z-order curves, which are related to quadtree decomposition. To support efficient range updates, a difference array allows range updates in \(O(1)\) time, with the actual array reconstructed via a prefix sum. For range queries on static arrays, a sparse table answers queries like Range Minimum Query in \(O(1)\) after \(O(n \log n)\) preprocessing. Square root decomposition divides an array into blocks of size \(\sqrt{n}\) to reduce query time to \(O(\sqrt{n})\), and Mo's algorithm extends this idea to offline range queries by sorting queries to minimize pointer movement. Heavy-light decomposition and centroid decomposition are two complementary techniques for decomposing a tree into paths or recursively splitting it at centroids to enable efficient path and subtree queries.