¿Qué es un ejemplo de implementación de Hashtable en C#?

Question

Me doy cuenta de que C# y .NET en general ya tienen las clases Hashtable y Dictionary.

¿Alguien puede demostrar en C# una implementación de una Hashtable?

Actualización: Para aclarar, no estoy ncessarily en busca de una aplicación completa, sólo un ejemplo de las características principales de una tabla hash (es decir, añadir, eliminar encuentran por tecla).

Answer 1

Hay es también la versión Mono de las bibliotecas de clases de golf:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 2

¿Has mirado el C5 collections? Puede download the source que incluye una tabla hash.

Answer 3

Se puede ver cómo se implementa el .NET Hashtable (por ejemplo en C#) con reflector

http://www.red-gate.com/products/reflector/

Answer 4

Puede ver un simple 'crecer sólo' tabla hash here, que debe dar una idea de una implementación simple.

responsabilidad: Probablemente hay algunos errores en el código, pero el principio es el mismo :)

Answer 5

También podría mirar a la puesta en práctica de Hashtable Mono aquí:

http://anonsvn.mono-project.com/viewvc/trunk/mcs/class/corlib/System.Collections/Hashtable.cs?revision=111788&view=markup

Answer 6

Mucho después de que la pregunta se ha hecho, por lo que no se puede esperar a ganar mucho rep. Sin embargo, decidí que sería divertido escribir mi propio ejemplo muy básico (en menos de 90 líneas de código):

public struct KeyValue<K, V> 
    { 
     public K Key { get; set; } 
     public V Value { get; set; } 
    } 

    public class FixedSizeGenericHashTable<K,V> 
    { 
     private readonly int size; 
     private readonly LinkedList<KeyValue<K,V>>[] items; 

     public FixedSizeGenericHashTable(int size) 
     { 
      this.size = size; 
      items = new LinkedList<KeyValue<K,V>>[size]; 
     } 

     protected int GetArrayPosition(K key) 
     { 
      int position = key.GetHashCode() % size; 
      return Math.Abs(position); 
     } 

     public V Find(K key) 
     { 
      int position = GetArrayPosition(key); 
      LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position); 
      foreach (KeyValue<K,V> item in linkedList) 
      { 
       if (item.Key.Equals(key)) 
       { 
        return item.Value; 
       } 
      } 

      return default(V); 
     } 

     public void Add(K key, V value) 
     { 
      int position = GetArrayPosition(key); 
      LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position); 
      KeyValue<K, V> item = new KeyValue<K, V>() { Key = key, Value = value }; 
      linkedList.AddLast(item); 
     } 

     public void Remove(K key) 
     { 
      int position = GetArrayPosition(key); 
      LinkedList<KeyValue<K, V>> linkedList = GetLinkedList(position); 
      bool itemFound = false; 
      KeyValue<K, V> foundItem = default(KeyValue<K, V>); 
      foreach (KeyValue<K,V> item in linkedList) 
      { 
       if (item.Key.Equals(key)) 
       { 
        itemFound = true; 
        foundItem = item; 
       } 
      } 

      if (itemFound) 
      { 
       linkedList.Remove(foundItem); 
      } 
     } 

     protected LinkedList<KeyValue<K, V>> GetLinkedList(int position) 
     { 
      LinkedList<KeyValue<K, V>> linkedList = items[position]; 
      if (linkedList == null) 
      { 
       linkedList = new LinkedList<KeyValue<K, V>>(); 
       items[position] = linkedList; 
      } 

      return linkedList; 
     } 
    } 

He aquí una pequeña aplicación de prueba:

static void Main(string[] args) 
     { 
      FixedSizeGenericHashTable<string, string> hash = new FixedSizeGenericHashTable<string, string>(20); 

      hash.Add("1", "item 1"); 
      hash.Add("2", "item 2"); 
      hash.Add("dsfdsdsd", "sadsadsadsad"); 

      string one = hash.Find("1"); 
      string two = hash.Find("2"); 
      string dsfdsdsd = hash.Find("dsfdsdsd"); 
      hash.Remove("1"); 
      Console.ReadLine(); 
     } 

No es la mejor aplicación, pero funciona para Agregar, Eliminar y Buscar. Utiliza chaining y un algoritmo de módulo simple para encontrar el depósito apropiado.