# Hash Table

A **hash table** is a data structure used to store data in key-value pairs. The table itself is usually implemented as an array.

Hash tables are often useful for searching in *O(1)* time with high probability.

## Common Uses

Implementation of associative arrays

Database indexing

Spell checking

Compilers and interpreter environments

Network routing

Substring searching

File and directory synchronization

Cryptography

Caching

Object representation in OOP languages

## Basics

The simple approach to implementing a hash table is creating a large array to hold all available data, indexed by keys. This is called a **direct access table**.

There are two major problems with this approach:

It assumes that keys are always integers, which is often not the case.

It is not memory-efficient.

The first issue can be addressed by *prehashing*, while the second is handled by *hashing*.

## Prehashing

**Prehashing** is the process of mapping keys to non-negative integers. This allows us to uniquely identify an object from a group of similar objects. For example, an employee might be assigned a unique ID number that is used to look up certain information about them.

In theory keys would be finite and descrete, where `h(x) = h(y) <=> x = y`

(where h is some function and x and y are arbitrary keys). This is usually not the case.

## Hashing

**Hashing** is the process of reducing a universe `U`

of all keys down to a reasonable size `m`

. This is done using a *hash function*.

A **hash function** is any function that maps a data set of arbitrary size (our universe `U`

) to a data set of fixed size (that array size `m`

). This allows us to store an arbitrary amount of information into a hash table's fixed-size array.

Good hash functions often have the following properties:

Easy to compute

Prioritize uniform distribution

Minimize the possible number of collisions

Hashing generally works as follows:

Ideally `m`

would be close to `n`

, where `n`

is the number of keys in the hash table. That way the space used is proportional to the table size and less memory is wasted.

### Common Hash Function Methods

#### Division Method

One of the most common types of hash functions uses simple division to generate an index:

where `k`

is the value obtained from the prehash and `m`

is the size of the hash table array.

#### Multiplication Method

Here we multiply some pseudo-random integers and do some bit shifting:

where `w`

is the word size of the computer, `m = 2^r`

, and `a`

is some odd number that is not close to a power of 2.

#### Universal Hashing

This method is very effective due to the amount of randomness generated:

where `a`

, `k`

, and `b`

are random numbers between 0 and `p-1`

, and `p`

is some prime number > `U`

.

## Collision Resolution

A **collision** occurs when two or more keys have the same hash, and thus need to be stored in the same place in the table. Collisions are very likely, so maintaining performance of a hash table is heavily dependent on how they are handled.

There are various methods used for handling collisions.

### Chaining (Open Hashing)

Chaining is a commonly-used technique for dealing with collisions.

Here, each index of the hash table's array is filled with a linked list. The actual data being stored is then inserted into the list at whatever index results from hashing. If an element needs to be stored in an occupied slot of the table, it is added to the end of the respective linked list.

The expected length of a chain for `n`

keys and `m`

slots is `n/m`

. This is called the **load factor**. This value is used to determine when to increase the size of the hash table's underlying array.

The worst case for chaining is the situation in which all the data is stored in the same list. In this case, searching is *O(n)*. This usually doesn't happen because good hash functions try to achieve uniform distribution.

### Linear Probing (Open Addressing)

Linear probing is usually used when data is stored in the table array directly. If a value needs to be inserted into an occupied slot, we probe the array until an empty space is found. In this case, that means iterating over the array one slot at a time.

### Quadradic Probing

Quadradic probing is similar to linear probing, except the interval between probes is a polynomial instead of an integer.

### Double Hashing

Double hashing is similar to linear probing, except the interval between probes is defined by a second hash function.

## Links

Last updated