Что такое пример реализации Hashtable в C#?

Question

Я понимаю, что C# и .NET вообще уже имеют классы Hashtable и Dictionary.

Может ли кто-нибудь продемонстрировать на C# реализацию Hashtable?

Обновление: Чтобы уточнить, я не нуждаюсь в полной реализации, просто пример основных функций хеш-таблицы (т. Е. Добавление, удаление, поиск по ключу).

Answer 1

Там также версия Mono из библиотек классов конечно:

• System.Collections.Hashtable

• System.Collections.Generic.Dictionary

Answer 2

Вы посмотрели на C5 collections? Вы можете download the source, который включает хеш-таблицу.

Answer 3

Вы можете увидеть, как .NET Hashtable реализован (например, в C#) с помощью отражателя

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

Answer 4

Вы можете просмотреть просто «растут только» Хеш here, который должен дать Вам идею простой реализации.

Отказ от ответственности: Существует, вероятно, несколько ошибок в коде, но принцип тот же :)

Answer 5

Вы также можете посмотреть на Hashtable реализации от Mono здесь:

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

Answer 6

долго после был задан вопрос, так что я не ожидаю, чтобы заработать много респ. Однако я решил, что это было бы интересно написать свой очень простой пример (менее чем 90 строк кода):

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

Вот небольшое тестовое приложение:

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

Это не лучшая реализация, но он работает для добавления, удаления и поиска. Он использует chaining и простой модульный алгоритм для поиска соответствующего ведра.