Che cos'è un esempio di implementazione di Hashtable in C#?

Question

Mi rendo conto che C# e .NET in generale hanno già le classi Hashtable e Dictionary.

Qualcuno può dimostrare in C# un'implementazione di un Hashtable?

Aggiornamento: Per chiarire, non sto ncessarily alla ricerca di una completa implementazione, solo un esempio delle caratteristiche fondamentali di una tabella hash (cioè aggiungere, rimuovere, trovare a chiave).

Answer 1

Ci è anche la versione Mono delle librerie di classi, naturalmente:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 2

Hai guardato il C5 collections? È possibile download the source che include una tabella hash.

Answer 3

Si può vedere come la Hashtable .NET è implementata (per esempio in C#) con riflettore

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

Answer 4

È possibile visualizzare un semplice 'crescere solo' tabella hash here, che dovrebbe dare un'idea di una semplice implementazione.

Disclaimer: C'è probabilmente qualche bug nel codice, ma il principio è lo stesso :)

Answer 5

Si potrebbe anche guardare l'attuazione Hashtable da Mono qui:

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

Answer 6

Molto tempo dopo la domanda è stato chiesto, quindi non mi aspetto di guadagnare molto rep. Comunque ho deciso che sarebbe stato divertente per scrivere il mio esempio molto semplice (in meno di 90 righe di codice):

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

Ecco una piccola applicazione di prova:

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

Non è la migliore realizzazione, ma funziona per Aggiungi, Rimuovi e Trova. Utilizza chaining e un semplice algoritmo modulo per trovare il bucket appropriato.