Jaki jest przykład implementacji Hashtable w języku C#?

Question

Zdaję sobie sprawę, że C# i .NET w ogóle ma już klasy Hashtable i Dictionary.

Czy ktoś może wykazać w języku C# implementację HashTable?

Aktualizacja: W celu wyjaśnienia, nie jestem ncessarily szuka pełnej realizacji, tylko przykład podstawowe funkcje hashtable (tj dodawać, usuwać znaleźć przez klucz).

Answer 1

Tam jest także wersja Mono bibliotek klasy przedmiotu:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 2

Czy obejrzałeś C5 collections? Możesz download the source, który zawiera tabelę mieszającą.

Answer 3

Można zobaczyć jak .NET HashTable jest realizowane (na przykład w języku C#) przy użyciu reflektor

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

Answer 4

Można zobaczyć proste „rosną tylko” hashtable here, co powinno dać wyobrażenie prostej implementacji.

Zastrzeżenie: Jest prawdopodobnie kilka błędów w kodzie, ale zasada jest taka sama :)

Answer 5

Można również spojrzeć na Hashtable realizacji od Mono tutaj:

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

Answer 6

Długo po pytanie zostało zadane, więc nie należy się spodziewać, aby zarobić dużo rep. Jednak zdecydowałem, że byłoby fajnie napisać własny bardzo prosty przykład (w czasie krótszym niż 90 linii kodu):

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

Oto mała aplikacja Test:

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

To nie jest najlepsza realizacja, ale działa dla Dodaj, Usuń i Znajdź. Używa on chaining i prostego algorytmu modulo do znalezienia odpowiedniego zasobnika.