5 – Hash Tables

Hash Table é uma estrutura de dados que armazena pares de chave-valor, permitindo o acesso eficiente aos valores associando-os a uma chave única. Ela é frequentemente utilizada quando precisamos de uma busca rápida e de inserção e remoção eficientes, geralmente com tempo de complexidade O(1), ou seja, tempo constante.

As principais operações em uma hash table são:

1. Inserção: Calcula-se o índice da chave com a função hash e, se não houver colisão, o valor é armazenado diretamente nesse índice. Caso haja colisão, utiliza-se a estratégia escolhida (encadeamento ou endereçamento aberto).
2. Busca: A chave é passada pela função hash, e o valor associado a essa chave é retornado, se existir. Caso haja colisão, é realizada uma busca adicional no bucket ou nas posições subsequentes (dependendo da técnica de resolução de colisão).
3. Remoção: Similar à busca, mas após encontrar o valor, ele é removido da tabela.

Exemplo:

Exemplo de implementação:

using System;
using System.Collections.Generic;

public class HashTable<K, V>
{
    private const int DefaultSize = 16; // Tamanho inicial da tabela
    private List<KeyValuePair<K, V>>[] table; // Array de listas encadeadas para resolução de colisões

    public HashTable(int size = DefaultSize)
    {
        table = new List<KeyValuePair<K, V>>[size];
        for (int i = 0; i < size; i++)
        {
            table[i] = new List<KeyValuePair<K, V>>(); // Inicializa cada bucket com uma lista
        }
    }

    // Função Hash simples baseada na chave
    private int GetHashCode(K key)
    {
        return key.GetHashCode() % table.Length;
    }

    // Inserção de um par chave-valor
    public void Put(K key, V value)
    {
        int index = GetHashCode(key);
        var bucket = table[index];

        // Verifica se já existe a chave
        foreach (var pair in bucket)
        {
            if (EqualityComparer<K>.Default.Equals(pair.Key, key))
            {
                // Se já existe, atualiza o valor
                bucket.Remove(pair);
                break;
            }
        }

        // Adiciona o novo par chave-valor
        bucket.Add(new KeyValuePair<K, V>(key, value));
    }

    // Busca pelo valor associado a uma chave
    public V Get(K key)
    {
        int index = GetHashCode(key);
        var bucket = table[index];

        foreach (var pair in bucket)
        {
            if (EqualityComparer<K>.Default.Equals(pair.Key, key))
            {
                return pair.Value; // Retorna o valor se a chave for encontrada
            }
        }

        throw new KeyNotFoundException("Chave não encontrada");
    }

    // Remover um par chave-valor
    public bool Remove(K key)
    {
        int index = GetHashCode(key);
        var bucket = table[index];

        for (int i = 0; i < bucket.Count; i++)
        {
            if (EqualityComparer<K>.Default.Equals(bucket[i].Key, key))
            {
                bucket.RemoveAt(i); // Remove o item
                return true;
            }
        }

        return false; // Retorna falso se a chave não foi encontrada
    }

    // Verificar se a chave existe
    public bool ContainsKey(K key)
    {
        int index = GetHashCode(key);
        var bucket = table[index];

        foreach (var pair in bucket)
        {
            if (EqualityComparer<K>.Default.Equals(pair.Key, key))
            {
                return true;
            }
        }

        return false;
    }

    // Exibir todos os pares chave-valor
    public void PrintAll()
    {
        for (int i = 0; i < table.Length; i++)
        {
            var bucket = table[i];
            foreach (var pair in bucket)
            {
                Console.WriteLine($"Chave: {pair.Key}, Valor: {pair.Value}");
            }
        }
    }
}

class Program
{
    static void Main()
    {
        var hashTable = new HashTable<string, string>();

        // Inserindo elementos
        hashTable.Put("nome", "João");
        hashTable.Put("cidade", "São Paulo");
        hashTable.Put("profissão", "Engenheiro de Software");

        // Obtendo valores
        Console.WriteLine("Nome: " + hashTable.Get("nome"));
        Console.WriteLine("Cidade: " + hashTable.Get("cidade"));

        // Verificando se uma chave existe
        Console.WriteLine("Contém chave 'profissão': " + hashTable.ContainsKey("profissão"));
        Console.WriteLine("Contém chave 'idade': " + hashTable.ContainsKey("idade"));

        // Removendo um item
        hashTable.Remove("cidade");
        Console.WriteLine("Cidade após remoção: " + hashTable.ContainsKey("cidade"));

        // Exibindo todos os pares
        Console.WriteLine("\nTodos os pares:");
        hashTable.PrintAll();
    }
}

[]’s
Otávio

Item Anterior:

4 – Filas

Próximo Item: NULL