wire / wire-format / hash-table

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).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Hash table

wire format

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).

fieldsizemeaning
Hash functionfunctionMaps key to bucket index: h(k) = k mod m (division), or h(k) = floor(m * (k * A mod 1)) (multiplication), or universal hashing.
Chainingcollision resolutionEach bucket is a linked list of entries. Simple but has cache-unfriendly pointer chasing.
Linear probingopen addressingOn collision, try (h(k)+i) mod m for i=0,1,2,... (primary clustering).
Quadratic probingopen addressingOn collision, try (h(k)+i^2) mod m (reduces clustering).
Double hashingopen addressingOn collision, try (h1(k) + i*h2(k)) mod m (best distribution).
Robin Hood hashingopen addressingOn collision, swap if the new entry has traveled farther than the existing one. Improves worst-case.
Load factorratioα = n/m (entries/buckets). Resize when α > threshold (0.75 for chaining, 0.5 for open addressing).
ResizeO(n)Allocate new array (2x), rehash all entries. Amortized O(1) per insert.

example:

00 00 00 00

Hash table (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/hash-table or /wire-format/hash-table.json