What is a Hash Table?

Click here to display content from YouTube.
Learn more in YouTube’s privacy policy.

Open "Learn Hash Tables in 13 minutes #️⃣" directly
This process allows for constant-time average case access to elements, making hash tables incredibly efficient for storing and retrieving data.

A hash table, also known as a hash map, is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, where the corresponding value can be stored or retrieved quickly.

How Does a Hash Table Work? (Javascript)

class HashTable {
    constructor() {
        this.table = [];
    }

    // Fonction de hachage
    _hash(key) {
        // Implémentez votre propre fonction de hachage ici
        // Elle doit transformer la clé en un indice entier
        // Exemple simplifié :
        return key.length % 10;
    }

    // Méthode pour ajouter une paire clé/valeur
    set(key, value) {
        const index = this._hash(key);
        if (this.table[index]) {
            for (let i = 0; i < this.table[index].length; i++) {
                // Trouvez la paire clé/valeur dans la chaîne
                if (this.table[index][i][0] === key) {
                    this.table[index][i][1] = value;
                    return;
                }
            }
            // Non trouvé, ajoutez une nouvelle paire clé/valeur
            this.table[index].push([key, value]);
        } else {
            // Créez une nouvelle chaîne pour cette clé
            this.table[index] = [[key, value]];
        }
    }

    // Méthode pour récupérer une valeur à partir de la clé
    get(key) {
        const index = this._hash(key);
        if (this.table[index]) {
            for (let i = 0; i < this.table[index].length; i++) {
                if (this.table[index][i][0] === key) {
                    return this.table[index][i][1];
                }
            }
        }
        return undefined; // Clé non trouvée
    }
}

// Exemple d'utilisation
const myHashTable = new HashTable();
myHashTable.set("Nathan", "555-0182");
myHashTable.set("Jane", "315-0322");

console.log(myHashTable.get("Nathan")); // Affiche "555-0182"

When a key-value pair is inserted into a hash table, the hash function calculates the index where the value will be stored based on the key. This index is typically determined by taking the result of the hash function modulo the size of the array, ensuring that it falls within the range of available buckets. If there is a collision, where multiple keys map to the same index, various collision resolution techniques can be employed, such as chaining or open addressing.

Example:

Let’s consider a simple example in Python:

# Creating a hash table using dictionaries
hash_table = {}

# Inserting key-value pairs
hash_table['apple'] = 10
hash_table['banana'] = 20
hash_table['orange'] = 30

# Retrieving values
print(hash_table['banana'])  # Output: 20

In this example, we create a hash table using Python dictionaries. We insert key-value pairs representing fruits and their respective quantities. Finally, we retrieve the quantity of bananas stored in the hash table.

So, we are on a daily routine when practice regularly provide scalable competences and happiness. Let’s coding !

Benefits of Hash Tables:

  • Fast Access: Hash tables offer constant-time average case access to elements, making them ideal for applications requiring quick data retrieval.
  • Flexible Key Types: Hash tables can typically handle a wide range of key types, including strings, integers, and custom objects.
  • Dynamic Sizing: Many implementations of hash tables dynamically resize to accommodate a varying number of elements efficiently.

Conclusion:

A hash table (also known as a hashmap) is a data structure that allows you to create a collection of key-value pairs. It efficiently stores and retrieves values based on their associated keys.

  1. Hashing Function: A hash table uses a function (called a hash function) to transform a key into an integer index. This index determines where the key-value pair is stored in memory.
  2. Array Storage: The hash table revolves around an array, initially empty. Each element in the array has two properties: the data (the value associated with the key) and the key itself. For example, a list of zip codes and corresponding city names would be a key-value association.
  3. Insertion: When you insert a key-value pair, the hash function reduces the key to an index within the array. The data is then stored at that index. If multiple keys map to the same index (collision), the hash table handles it by comparing the actual keys directly.
  4. Retrieval: To retrieve a value, you run the key through the same hash function, get its hash-key, and access the corresponding place in the hash table to retrieve the associated data.

Use Cases:

  • Caching: Hash tables are commonly used for caching. For instance, if you need to hold records for thousands of students in a university, a hash table can efficiently store and retrieve this data.
  • Databases (Indexing): Hash tables are essential for indexing in databases, allowing fast retrieval of data based on keys.

Further Reading: