¿Qué es un ejemplo de una implementación Hashtable en C #?
https://stackoverflow.com/questions/625947
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Comprendo que C # y .NET en general ya tienen las clases Hashtable y Dictionary.
¿Puede alguien demostrar en C # una implementación de un Hashtable?
Actualización: Para aclarar, no estoy buscando necesariamente una implementación completa, solo un ejemplo de las funciones principales de una tabla hash (es decir, agregar, eliminar, buscar por clave).
Solución
También existe la versión Mono de las bibliotecas de clases, por supuesto:
Otros consejos
Mucho después de que se haya formulado la pregunta, no espero ganar muchas repeticiones. Sin embargo, decidí que sería divertido escribir mi propio ejemplo muy básico (en menos de 90 líneas de código):
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;
}
}
Aquí hay una pequeña aplicación de prueba:
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();
}
No es la mejor implementación, pero funciona para Agregar, Eliminar y Buscar. Utiliza encadenamiento y un algoritmo de módulo simple para encontrar el grupo apropiado.
¿Ha consultado las colecciones de C5 ? Puede descargar la fuente que incluye una tabla hash.
Puede ver cómo se implementa .NET Hashtable (por ejemplo, en C #) utilizando el reflector
Puede ver una tabla hash 'solo de crecimiento' simple here , que debería darle una idea de una implementación simple.
Descargo de responsabilidad: probablemente haya algunos errores en el código, pero el principio es el mismo :)
También puede consultar la implementación de Hashtable desde Mono aquí:
