Hash-based Structure Variants

Hash-based Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Hash Table	Key–value storage	O(1) average lookup	Dictionaries	Key-based	Bucket-based	Collision handling needed
Double Hashing	Collision resolution	Two hash functions	Open addressing	Key-based	Contiguous	Reduces clustering
Dynamic Perfect Hash Table	Collision-free hashing	Rehash on growth	Static key sets	Key-based	Bucket-based	Guaranteed O(1)
Hash List	List of hashed entries	Simple chaining	Small maps	Sequential	Pointer-based	Easy implementation
Hash Tree	Tree of hashes	Integrity verification	Blockchains	Path-based	Tree-based	Merkle variant
Hash Array Mapped Trie	Trie + hashing	Persistent map	Functional languages	Key-based	Node-based	Used in Clojure
Ctrie	Concurrent HAMT	Lock-free updates	Concurrent maps	Key-based	Node-based	Thread-safe
Hahs Trie	Hash-based trie	Hybrid structure	Key indexing	Key-based	Node-based	Rare, name varies
Prefix Hash Tree	Prefix-based hashing	Hierarchical hashes	Routing, P2P	Prefix-based	Tree-based	Scalable lookup
Distributed Hash Table	Decentralized hash map	Peer-to-peer routing	P2P networks	Key-based	Distributed	Fault tolerant
Koorde	Ring-based DHT	De Bruijn routing	P2P overlays	Key-based	Distributed	Efficient hops
Approx. Membership Filter	Probabilistic set	False positives allowed	Fast membership test	Hash-based	Compact	No deletions (basic)
Bloom Filter	Bit-based AMQ	Very space efficient	Caches, DBs	Hash-based	Bit array	False positives only
Cuckoo Filter	Fingerprint-based AMQ	Supports deletion	Networking	Hash-based	Compact	Faster than Bloom
Quotient Filter	Compressed AMQ	Cache-friendly	Storage systems	Hash-based	Compact	Bloom alternative
Count-Min Sketch	Frequency estimator	Approx counts	Streaming data	Hash-based	Compact	Overestimates
Rolling Hash	Windowed hashing	Fast recomputation	String search	Sequential	Constant	Used in Rabin–Karp
MinHash	Similarity hashing	Jaccard estimation	Near-duplicate detection	Hash-based	Compact	Probabilistic