Differences

This shows you the differences between two versions of the page.

--- hash-map [June 11, 2026 at 09:44] – created - external edit 127.0.0.1
+++ hash-map [June 11, 2026 at 09:58] (current) – Ivan Janevski
@@ Line 1: / Line 1: @@
 # Hash map
-A **hash map** (also called a hash table) is a data structure that maps arbitrary keys to values in O(1) average time. A **hash function** converts a key to an integer index into a backing [[array]] of buckets. The ideal hash function distributes keys uniformly so that each bucket holds roughly one entry; when two keys hash to the same bucket, that is a **collision** and must be resolved.
+A **hash map** (also called a hash table) is a data structure that maps arbitrary keys to values in O(1) average time.
+A **hash function** converts a key to an integer index into a backing [[array]] of buckets. The ideal hash function distributes keys uniformly so that each bucket holds roughly one entry; when two keys hash to the same bucket, that is a **collision** and must be resolved.
 The two main collision resolution strategies are **chaining** and **open addressing**. In chaining, each bucket holds a [[linked-list]] of entries that hashed to it; lookup traverses the list. In open addressing, all entries live in the backing array and a collision is resolved by probing adjacent slots (linear probing, quadratic probing, double hashing) until an empty one is found.