---
type: slide
---

# Maps (HashTables)


---

A map is an abstract data type designed to efficiently store and retrieve values based upon a uniquely identifying search key for each.

---

- A map stores key-value pairs (k,v), which we call entries, where k is the key and v is its corresponding value.
- Keys are required to be unique, so that the association of keys to values defines a mapping.

---


---

## HashTable

---

**Hashing** is a way to distribute records or values across an array of buckets.

---

Hash Table
- Is the most efficient **map implementation**, and it’s the most used structure in practical life.

- Hash Tables as maps could be represented by Libraries in real life, but they have a more efficient way by using Hash-Functions.

- Each key will be mapped into a specific index using the Hash Function.

---

Hash Tables use an array of buckets, each bucket has an index indicating its place. Each bucket could contain several records.


---

<!-- .slide: style="font-size: 30px;" -->

Hash Table Structure
- **Lookup Table**: this table is represented by an array.
- **Bucket**: A list of records that can be accessed from array index.
- **Key**: the passed key for hash function to be mapped to a value.
- **Record “Value”**: The value that is mapped by specific key.
- **Hash Function**: A function that convert keys into some sort of index.
- **Hash Code**: An integer represent the key of a record.

---

**Hash Function** is an algorithm that takes a key as a parameter, and convert it to a special form of integer.

Hash Functions may produce the same hash code for different keys, which lead us to store different values in the same index. This case called **Collision**.

---


---

How we determine if a Hash Function is good or not?

---

We say it’s a good function If the function produces a zero or a low number of collisions, fast and easy.

---

Handling collisions

---

before we get into collisions see [this video](https://www.youtube.com/watch?v=tjtFkT97Xmc)

---

There are several methods to deal with collisions:
- Linear Probing (Open Addressing)
- Separate Chain

---

Linear Probing (Open Addressing)


---

- The idea behind this method is to find the proper index, if it’s not empty, then check the next index, and it goes on.

- Inserting entry e(k1, v1) means that we will look for the index that hash function gives us, then check if index is empty, store the value, else check the next index.

---

Separate Chain


---

- The idea behind this method is to use an array of records, then a pointer for a linkedlist in each array index.

- Inserting entry e(k1, v1) means that we will look for the index that hash functions gives us, then check if index is empty, store the value, else add this value to the list that index points to.

---

built-in implementations for Maps in javascript:
- [Object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object)
- [Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map)
- [WeakMap](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakMap)

---

How to Implement HashTable in js ?

to try that go throw [this](https://github.com/rithmschool/javascript_computer_science_exercises/tree/master/hash_tables_exercise) Exercise

---

check [this link](https://leetcode.com/tag/hash-table/) to solve problems with hashtable.

I suggest to start with these:

- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)
- [Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/)
- [Two Sum](https://leetcode.com/problems/two-sum/
)