Was ist ein Beispiel für eine Hashtable-Implementierung in C#?

Question

Ich weiß, C# und .NET im Allgemeinen bereits die Hashtable und Dictionary-Klassen.

Kann jemand in C# eine Implementierung einer Hashtable demonstrieren?

Update: Um zu verdeutlichen, bin ich nicht unbedingt auf der Suche nach einer vollständigen Implementierung, nur ein Beispiel für die Kernfunktionen einer Hashtable (d. H. Hinzufügen, entfernen, finden nach Schlüssel).

Answer 1

Es die Mono-Version der Klassenbibliotheken natürlich auch:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 2

Haben Sie sich die C5 collections angesehen? Sie können download the source, die eine Hash-Tabelle enthält.

Answer 3

können Sie sehen, wie die .NET Hashtable implementiert ist (zum Beispiel in C#) mit Reflektor

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

Answer 4

Sie können eine einfache Ansicht 'wachsen-only' hashtable here, die Ihnen eine Idee geben sollte einer einfachen Implementierung.

Haftungsausschluss: Es gibt wahrscheinlich ein paar Fehler im Code, aber das Prinzip ist das gleiche :)

Answer 5

Sie auch an der Hashtable Implementierung von Mono hier aussehen könnte:

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

Answer 6

Lange nachdem die Frage gestellt worden, so erwarte ich nicht viel rep zu verdienen. Allerdings habe ich beschlossen, es würde Spaß machen, mein eigenes sehr einfaches Beispiel (in weniger als 90 Zeilen Code) zu schreiben:

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

Hier ist eine kleine Testanwendung:

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

Es ist nicht die beste Umsetzung, aber es funktioniert für Hinzufügen, Entfernen und Suchen. Es verwendet chaining und einen einfachen Modulo-Algorithmus, um den passenden Bucket zu finden.