Tabela Hash

Em ciência da computação, uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.

Fonte: http://pt.wikipedia.org/wiki/Tabela_hash

Código da classe HashTable:

Código:

using System;
using System.Collections.Generic;
using System.Text;


namespace HashTable
{
    class HashTable
    {
        private const double MAX_ALPHA = 0.75;
        private class Node
        {
            public int value;
            public Node next;

            public Node(int value, Node next)
            {
                this.value = value;
                this.next = next;
            }
        }

        private Node [] tab;
        private int numElements;
        int pos;

        public HashTable(int size)
        {
            tab = new Node[size]; 
        }

        private bool contains(int x)
        {
            pos = hashCode(x);
            Node aux = tab[pos];
            while (aux != null && aux.value !=(x))
                aux = aux.next;
            return aux != null;

        }

        public void insert(int x)
        {
            if ((numElements + 1) > MAX_ALPHA * tab.Length)
                grow();
            pos = hashCode(x);
            Node L = tab[pos];
            tab[pos] = new Node(x,L);
            numElements++;
        }
       
        private void grow()
        {
          Node [] oldt = tab;
            tab = new Node[2*oldt.Length];
            numElements = 0;


            foreach (Node L in oldt)
            {
                Node aux = L;
                while (aux != null)
                {
                    insert(aux.value);
                    aux = aux.next;
                }
            }
        }
       
       
        private int hashCode(int x)
        {
            return x % tab.Length;
        }

        public void remove(int x)
        {
            pos = hashCode(x);
            Node L = tab[pos];
            if (L != null)
            {
                if (L.value == x)
                    tab[pos] = L.next;
                else
                    while (L.next != null && L.next.value != x)
                        L = L.next;
                if (L.next != null)
                    L.next = L.next.next;
            }
        }

        public string toString()
        {
            bool first = true;
            StringBuilder sb = new StringBuilder("[");
            for (int i = 0; i < tab.Length; i++)
                first = appendList(first, sb, i);
            sb.Append("]");
            return sb.ToString();
        }

        private bool appendList(bool first, StringBuilder sb, int i)
        {
            Node aux = tab[i];
            while (aux != null)
            {
                if (first)
                    first = false;
                else
                    sb.Append(",");
                sb.Append(aux.value);
                aux = aux.next;
            }
            return first;
        }




        static void Main(string[] args)
        {
            HashTable table = new HashTable(131);
            table.insert(89);
            table.insert(19);
            table.insert(34);
            table.insert(66);
            string s = table.toString();
          Console.WriteLine(s);

        }
    }
}

Até a próxima.