Was ist ein Beispiel für eine Hashtable-Implementierung in C #?
Frage
wird mir klar, C # und .NET in der Regel bereits die Hashtable und Dictionary-Klassen hat.
Kann mir jemand zeigen in C # eine Implementierung einer Hashtable?
Update: Um zu klären, ich bin ncessarily nicht für eine vollständige Implementierung suche, nur ein Beispiel für die Kernfunktionen einer Hash-Tabelle (dh Hinzufügen, Entfernen von Schlüssel finden)
Lösung
Es gibt auch die Mono-Version der Klassenbibliotheken natürlich:
Andere Tipps
Lange nachdem die Frage gestellt worden, so erwarte ich nicht viel rep zu verdienen. Aber ich entschied, dass es Spaß macht mein eigenes sehr einfaches Beispiel zu schreiben (in weniger als 90 Zeilen Code):
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 Finden. Es verwendet Verkettungs und ein einfacher Modulo-Algorithmus den entsprechenden Eimer zu finden.
Haben Sie an den C5 Sammlungen sah ? Sie können die Quelle herunterladen, die eine Hash-Tabelle enthält.
Sie können sehen, wie die .NET Hashtable (zum Beispiel in C #) realisiert wird Reflektor
Sie können eine einfache Ansicht 'wachsen-only' Hashtable hier , die Sie sollten eine Vorstellung von einer einfachen Implementierung geben.
Disclaimer: Es gibt wahrscheinlich ein paar Fehler im Code, aber das Prinzip ist das gleiche:)
Sie können auch an der Hashtable Implementierung aussehen von Mono hier: