wire / wire-format / hash-table
A hash table maps keys to values using a hash function. Structure: array of buckets, each holding a list of entries (chaining) or a single entry (open addressing). Load factor = entries/buckets. Resize when load factor exceeds threshold (typically 0.75). Hash functions: division method (h(k) = k mod m), multiplication method, universal hashing. Collision resolution: chaining (linked lists), open addressing (linear probing, quadratic probing, double hashing, Robin Hood hashing).
aka: Hash table
spec: Hash table
A hash table maps keys to values using a hash function. Structure: array of buckets, each holding a list of entries (chaining) or a single entry (open addressing). Load factor = entries/buckets. Resize when load factor exceeds threshold (typically 0.75). Hash functions: division method (h(k) = k mod m), multiplication method, universal hashing. Collision resolution: chaining (linked lists), open addressing (linear probing, quadratic probing, double hashing, Robin Hood hashing).
| field | size | meaning |
|---|---|---|
| Hash function | function | Maps key to bucket index: h(k) = k mod m (division), or h(k) = floor(m * (k * A mod 1)) (multiplication), or universal hashing. |
| Chaining | collision resolution | Each bucket is a linked list of entries. Simple but has cache-unfriendly pointer chasing. |
| Linear probing | open addressing | On collision, try (h(k)+i) mod m for i=0,1,2,... (primary clustering). |
| Quadratic probing | open addressing | On collision, try (h(k)+i^2) mod m (reduces clustering). |
| Double hashing | open addressing | On collision, try (h1(k) + i*h2(k)) mod m (best distribution). |
| Robin Hood hashing | open addressing | On collision, swap if the new entry has traveled farther than the existing one. Improves worst-case. |
| Load factor | ratio | α = n/m (entries/buckets). Resize when α > threshold (0.75 for chaining, 0.5 for open addressing). |
| Resize | O(n) | Allocate new array (2x), rehash all entries. Amortized O(1) per insert. |
example:
00 00 00 00
Hash table (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/hash-table
or /wire-format/hash-table.json