Quel est un exemple d'implémentation de Hashtable en C #?
https://stackoverflow.com/questions/625947
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je réalise que C # et .NET en général ont déjà les classes Hashtable et Dictionary.
Quelqu'un peut-il démontrer en C # l'implémentation d'une table de hachage?
Mise à jour: Pour clarifier, je ne recherche pas nécessairement une implémentation complète, mais juste un exemple des fonctionnalités essentielles d'une table de hachage (c'est-à-dire ajouter, supprimer, rechercher par clé).
La solution
Il existe également la version Mono des bibliothèques de classes:
Autres conseils
Bien après que la question ait été posée, je ne m'attends donc pas à gagner beaucoup de représentants. Cependant, j’ai décidé que ce serait amusant d’écrire mon propre exemple très basique (en moins de 90 lignes de 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;
}
}
Voici une petite application de 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();
}
Ce n'est pas la meilleure implémentation, mais cela fonctionne pour Ajouter, Supprimer et Rechercher. Il utilise l'enchaînement et un algorithme simple modulo pour trouver le compartiment approprié.
Avez-vous consulté les collections C5 ? Vous pouvez télécharger le code source , qui inclut une table de hachage.
Vous pouvez voir comment le tableau de hachage .NET est implémenté (par exemple en C #) à l'aide d'un réflecteur
Vous pouvez afficher une simple table de hachage "à développement uniquement" ici , ce qui devrait vous donner une idée d'une implémentation simple.
Avertissement: Il y a probablement quelques bugs dans le code, mais le principe est le même:)
Vous pouvez également consulter la mise en œuvre de Hashtable à partir de Mono ici:
