Qual è un esempio di implementazione Hashtable in C #?
https://stackoverflow.com/questions/625947
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
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 sono necessariamente alla ricerca di un'implementazione completa, ma solo un esempio delle funzionalità principali di una tabella hash (ovvero aggiungi, rimuovi, trova per chiave).
Soluzione
Esiste ovviamente anche la versione Mono delle librerie di classi:
Altri suggerimenti
Molto dopo che la domanda è stata posta, quindi non mi aspetto di guadagnare molto rappresentante. Comunque ho deciso che sarebbe stato divertente 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 implementazione, ma funziona per Aggiungi, Rimuovi e Trova. Utilizza concatenamento e un semplice algoritmo modulo per trovare il bucket appropriato.
Hai guardato le collezioni C5 ? Puoi scaricare la fonte che include una tabella hash.
Puoi vedere come viene implementato .NET Hashtable (ad esempio in C #) usando reflector
Puoi visualizzare una semplice hashtable 'solo per coltivazione' qui , che dovrebbe darti un'idea di una semplice implementazione.
Disclaimer: probabilmente ci sono alcuni bug nel codice, ma il principio è lo stesso :)
Puoi anche dare un'occhiata all'implementazione di Hashtable da Mono qui:
