> For the complete documentation index, see [llms.txt](https://tanias-workspace.gitbook.io/tanias-little-corner/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tanias-workspace.gitbook.io/tanias-little-corner/data-structures/hashmap.md).

# HashMap

{% hint style="info" %}
A **hash map** (also known as a hash table) is a data structure that allows you to store and retrieve values efficiently using keys. It is widely used due to its fast average-case performance for insertions, deletions, and lookups.
{% endhint %}

## **Key Concepts of Hash Map**

1. **Hash Function**
   * **Description:** A hash function takes a key and computes an index in an array where the value associated with that key will be stored.
   * **Purpose:** The goal is to distribute keys uniformly across the array to minimize collisions.
2. **Buckets**
   * **Description:** An array of "buckets" or "slots" where data is stored. Each bucket can be a linked list or another data structure to handle collisions.
   * **Purpose:** Buckets store values for different keys that hash to the same index.
3. **Collisions**
   * **Description:** Occur when two or more keys hash to the same index.
   * **Handling:** Collisions are handled using techniques such as chaining (linked lists) or open addressing (probing).
4. **Load Factor**
   * **Description:** The ratio of the number of elements to the number of buckets.
   * **Purpose:** Helps in resizing the hash map to maintain performance. A high load factor can lead to more collisions.
5. **Resizing**
   * **Description:** Involves increasing the number of buckets and rehashing existing keys to maintain performance as the hash map grows.

<figure><img src="/files/zm177KBuJTU7sqTICUvu" alt=""><figcaption></figcaption></figure>

#### **Example in C++**

Here's a basic example using `std::unordered_map` from the C++ Standard Library:

<figure><img src="/files/JkwMcOAhTtxW2b3glJXw" alt=""><figcaption><p>HashMap</p></figcaption></figure>

* **1. Insert (Put)**
  * **Description:** Adds a key-value pair to the hash map.
  * **Operation:** Calculate the hash of the key to determine the bucket, then insert the key-value pair into the appropriate bucket.
* **2. Retrieve (Get)**
  * **Description:** Retrieves the value associated with a given key.
  * **Operation:** Calculate the hash of the key, find the bucket, and look up the key within the bucket.
* **3. Delete (Erase)**
  * **Description:** Removes a key-value pair from the hash map.
  * **Operation:** Calculate the hash of the key, find the bucket, and remove the key-value pair from the bucket.
* **4. Check Existence (Find)**
  * **Description:** Checks if a key exists in the hash map.
  * **Operation:** Calculate the hash of the key, find the bucket, and check if the key is in the bucket.