## Things to be discussed

Introduction (Previous Article)

Hash Table (Previous Article)

Hash Function (Previous Article)

Strengths (Previous Article)

Weaknesses (Previous Article)

Collision Problem

Dynamic Array Resizing

Applications

Implementation

Practice Problems

### Collision problem

Let’s just take a quick pause to think about hash functions for a second - since we’re converting data of any length *x* into data of fixed size *y*, dataset *x* will be way larger than dataset *y*. There are infinite entries in dataset *x*, but limited ones in dataset *y* because all the numbers must be a certain size or length. In other words, there could be two or more pieces of data in dataset *x* that will hash to the same integer in dataset *y*.

This is called the collision problem, and here are some ways to deal with it:

Separate Chaining

Linear probing

Quadratic Probing

Double Hashing

- Separate Chaining

When two or more data *collide *and hash to the same index, we could simply link the data up into a linked list at that index of the array, as you can see above.

Of course, this is the kind of situation we’re going to want to avoid because instead of using constant time `O(1)`

to find a key and its corresponding information in the array, we end up needing `O(n)`

time to walk through the linked lists to find our actual values.

- Linear Probing

Another way to deal with collisions is to walk down the array from the collided index one by one until you get to the next free slot.

*Quadratic Probing*

Quadratic probing is like linear probing and the only difference is instead of going one by one we follow an arbitrary polynomial to get to the next unoccupied index.

*Double hashing*

Double hashing is like linear probing and the only difference is the interval between successive jumps. Here, the interval between jumps is computed by using two hash functions.

### Dynamic array resizing

Suppose we keep adding more items to our hash map. As the number of keys and values in our hash map exceeds the number of indices in the underlying array, hash collisions become inevitable.

To mitigate this, we could expand our underlying array whenever things start to get crowded. That requires allocating a larger array and rehashing all our existing keys to figure out their new position in `O(n)`

time.

### Applications

Hash tables are implemented where

Constant time lookup and insertion is required.

Cryptographic applications are used.

Indexing data is required.

For example,

*Associative arrays*: Hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays (arrays whose indices are arbitrary strings or other complicated objects).*Database indexing*: Hash tables may also be used as disk-based data structures and database indices (such as in DBM).*Caches*: Hash tables can be used to implement caches i.e. auxiliary data tables that are used to speed up access to data, which is primarily stored in slower media.*Object representation*: Several dynamic languages, such as Perl, Python, JavaScript, and Ruby use hash tables to implement objects.Hash Functions are used in various algorithms to make their computing faster.

## Implementation in C++

The implementation of Hash Table using separate chaining to resolve collisions is given here,