wisconsin
Hashing

Hashing

Curated by Last modified: 3 min read

Hash Functions

A hash function is a function that takes an input and produces a deterministic hash value; distinct keys may collide. It is used to map data of arbitrary size to fixed-size values. Hash functions are commonly used in data structures like hash tables, where they help in efficiently storing and retrieving data.

A good hash function should have the following properties:

  • Deterministic: The same input should always produce the same output.
  • Uniform distribution: The output should be uniformly distributed across the output space to minimize collisions.
  • Fast computation: The hash function should be fast to compute for all possible inputs.

Hash Tables

A hash table is a data structure that uses a hash function to map keys to values. It allows for efficient insertion, deletion, and lookup operations.

Structure

A hash table consists of an array of buckets, where each bucket can store one or more key-value pairs. The hash function is used to compute the index of the bucket for a given key.

Buckets

This computation is done using the following formula:

int index = Math.floorMod(key.hashCode(), size);

Where hash(key) is the hash function applied to the key, and size is the number of buckets in the hash table.

Collisions

In the event of a collision (when two keys hash to the same index), there are several strategies to handle it:

  • Chaining: Each bucket contains a linked list of key-value pairs. When a collision occurs, the new key-value pair is added to the linked list at that index.
  • Open addressing: When a collision occurs, the algorithm searches for the next available bucket in the array to store the new key-value pair. This can be done with the following methods:
    • Linear probing: The algorithm checks the next bucket in a linear (consecutive) manner.
    • Quadratic probing: The algorithm checks buckets at increasing intervals (1, 4, 9, etc.).
    • Double hashing: A second hash function is used to compute the step size for probing.

Load Factor

The load factor of a hash table is defined as the ratio of the number of elements in the table to the number of buckets. It is used to determine when to resize the hash table.

Growth

When the load factor exceeds a certain threshold, the hash table is resized to maintain efficient performance. This typically involves creating a new array with a larger size and rehashing all existing key-value pairs into the new array.

The growth factor is the factor by which the hash table is resized. A common growth factor is 2, meaning the size of the hash table is doubled when it is resized.

Tip

A common load factor threshold is 0.75. When the load factor exceeds this threshold, the hash table is resized (usually doubled) to maintain efficient performance.

Connections

Obvious technical and formatting errors repaired.

Linked to this page