Hashtables - Tabelas de Dispersão

As hashtables são, nas linguagens de programação modernas, uma das estruturas mais úteis para armazenar grandes quantidades de informação.

As suas principais características são:

• Não são ordenadas, ou seja um ciclo de pesquisa sequencial pode obter os dados por qualquer ordem;
• São muito eficientes nas pesquisas, na maior parte das situações basta uma comparação para obter o valor a pesquisar, independentemente do número de elementos na tabela;
• Internamente cada elemento representa uma lista ligada;
• Ao inserir um elemento deve ser indicada uma chave da qual é calculado o código hash que servirá para indexar o elemento na tabela, muito importante, o código hash é obtido a partir da chave e não dos valores armazenados;
• Caso existe um elemento com a mesma chave o novo elemento inserido substitui o antigo;
• Para obter um elemento basta indicar a chave associada;
• A principal desvantagem é o espaço em memória que a tabela necessita.

A plataforma .NET implementa dois tipos de hashtables:

• Dictionary: para utilização genérica;
• Hashtable: para utilizar referências a objetos;

Para aprendermos a utilizar as hashtables vamos criar um pequeno programa para guardar nomes e números de telefone.



Assim declaramos a nossa hashtable:
     Dictionary listaTelefonica<string,int> = new Dictionary();


Ao fazermos a declaração desta forma indicamos que vamos armazenar um inteiro e utilizar uma chave do tipo string.


Para adicionar um elemento basta escrever:
    listaTelefonica["joaquim"]=919191919;


A pesquisa é conseguida da seguinte forma:
    int numTelefone=listaTelefonica["joaquim"];


Neste caso se a chave indicada não existir é lançada uma excepção do tipo KeyNotFoundException.


Outra forma de pesquisar:
   int numTelefone;
   if(listaTelefonica.TryGetValue("joaquim",out numTelefone)
        Console.WriteLine("{0}",numTelefone);
   else 
        Console.WriteLine("Nome não foi encontrado!");

Para remover um elemento basta executar a linha:
    listaTelefonica.Remove("joaquim");

Listar toda a hastable:
    foreach (KeyValuePair elemento in listaTelefonica) 
         Console.WriteLine("{0} - {1}", elemento.Key, elemento.Value);


Para terminar temos a função clear que permite limpar a hashtable toda:
    listaTelefonica.Clear();


A principal vantagem da hashtable é a sua excepcional capacidade de pesquisar elementos sem tempos de espera, literalmente 0 (zero) milissegundos de espera, para provar esta potencialidade comparei os tempos de execução de uma hashtable com um vector de duas dimensões, uma tabela tradicional.

Como se pode ver tanto na inserção de dados como na pequisa a hashtable é mais rápida.
Enquanto que na tabela a pesquisa é linear e por isso depende da posição do elemento a encontrar na hashtable o tempo de pesquisa é sempre o mesmo.


O seguinte código corresponde ao programa que criado para executar este teste.
O projeto está aqui.



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;


namespace tabelahash
{
    class Program
    {
        const int MAX = 10000000;


        static void Main(string[] args)
        {
            Dictionary<string, int> listaTelefonica = new Dictionary<string, int>();
            string[,] listaTelefonicas= new string[MAX,2];
            
            Console.WriteLine("Numero de elementos: {0}", MAX);
            var sw = new Stopwatch();
            //preencher a tabela de hash
            sw.Start();
            for (int i = 0; i < MAX; i++)
            {
                listaTelefonica["joaquim"+i]=i;
            }
            sw.Stop();
            Console.WriteLine("Tempo necessário para preencher a hashtable {0} milissegundos", sw.ElapsedMilliseconds);
            //preencher a tabela de strings
            sw.Reset();
            sw.Start();
            for (int i = 0; i < MAX; i++)
            {
                listaTelefonicas[i, 0] = "joaquim" + i;
                listaTelefonicas[i, 1] = i.ToString();
            }
            sw.Stop();
            Console.WriteLine("Tempo necessário para preencher a hashtable {0} milissegundos", sw.ElapsedMilliseconds);


            string nome;
            Console.Write("Nome a pesquisar:");
            nome=Console.ReadLine();
            sw.Reset();
            sw.Start();
            try{
                int telefone = listaTelefonica[nome];
                sw.Stop();
                Console.WriteLine("{0} - {1}", nome, telefone);
            }
            catch(KeyNotFoundException erro){
                Console.WriteLine("Elemento não encontrado: {0}",erro.Message);
            }
            Console.WriteLine("Tempo necessário para pesquisar a hashtable {0} milissegundos", sw.ElapsedMilliseconds);


            Console.ReadLine();
            sw.Reset();
            sw.Start();
            for (int i = 0; i < MAX; i++)
            {
                if (listaTelefonicas[i,0] == nome)
                {
                    sw.Stop();
                    Console.WriteLine("{0} - {1}", nome, listaTelefonicas[i, 1]);
                    break;
                }
            }
            Console.WriteLine("Tempo necessário para pesquisar a hashtable {0} milissegundos", sw.ElapsedMilliseconds);


            Console.ReadLine();
                //listar todos
            sw.Reset();
            sw.Start();
            foreach (KeyValuePair<string, int> elemento in listaTelefonica)
                Console.WriteLine("{0} - {1}", elemento.Key, elemento.Value);
            sw.Stop();
            Console.WriteLine("Tempo necessário para listar a hashtable {0} milissegundos", sw.ElapsedMilliseconds);


            Console.Read();
        }
    }
}