Avançar para o conteúdo principal

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();
        }
    }
}

Comentários

Mensagens populares deste blogue

Upgrade do Windows Home para Pro sem formatar

 Há algum tempo que tentava fazer o upgrade do meu Windows 10 da versão Home para a versão Pro, mas chegava sempre a um ponto em que me era solicitado para formatar o sistema e não estava para isso. Finalmente conseguinte seguindo estes passos: - seguinte estes passos  utilizei uma das chaves genéricas para o Windows 10 Pro e fui a Settings > Update & Security > Activation > Change the product key; - após inserir uma das chaves o Windows instala as funcionalidades Pro e pede para reiniciar; - agora tem o Windows Pro mas não está ativado, assim fui ao site urcdkeys  onde comprei uma chave para o Windows Pro por menos de €20; - com essa chave voltei a funcionalidade Change the product key e ativei o Windows; - e pronto, Windows Pro ativado sem formatar ou reinstalar. Importante : eu não tenho nada a ver com o site urcdkeys por isso a vossa experiência pode correr de forma diferente da minha.

Vamos fazer um carro com o Unity 3D

Neste artigo vamos fazer um carro, simples, com o Unity 3D. A ideia é utilizar o motor de física do Unity 3D para simular o comportamento do carro. Os passos a seguir são: [1] - Criar um projeto novo

Tem troco

Para hoje um pequeno programa que dá troco, bem dar não dá mas calcula o troco a dar em função das moedas disponíveis. Neste projeto vamos utilizar o novo Visual Studio 2012. Como era de se esperar vamos iniciar um projeto novo: Agora adicionamos os seguintes elementos:  - um botão para calcular as moedas a dar de troco  - um botão para repor o número de moedas iniciais disponíveis  - uma textbox para introduzir o valor a pagar  - uma textbox para introduzir o valor entregue  - umas labels para informar o utilizador do que deve introduzir e outra para mostrar o troco  - por fim uma grelha para mostrar os valores das moedas e as quantidades disponíveis de cada uma. A janela principal do programa fica assim: Agora o código, primeiro o evento load do formulário, neste vamos definir os valores das moedas e as respetivas quantidades Para guardar estes valores vamos necessitar de uma variável definida ao nível do formulário, logo abaixo da definição da class: Public Class Form1     Public mo