¿Cuáles son las aplicaciones de las tablas hash?

Las tablas hash acechan en objetos de C #

En el mundo de C # donde ahora vivo y trabajo, la “tabla hash” es una definición que es utilizada por o es integral para varios tipos. El más utilizado es el tipo Diccionario.

Hay un tipo Hashtable en el marco .NET, pero no puedo recordar un momento en que usé esa clase específica en una aplicación. La razón es bastante simple: el Hashtable almacena los tipos de Objeto, lo que obliga al programador a encajonar y desempaquetar las claves y los valores almacenados. Es mucho más fácil usar un Dictonary , donde puede declarar los tipos para las claves y los valores, imponiendo así algunas restricciones de tiempo de compilación y haciendo que su uso sea bastante claro en el resto del código.

Los diferentes tipos de Diccionarios y Listas tienen todas sus claves hash, por lo que utilizan efectivamente tablas hash para minimizar los tiempos de búsqueda.

Pero, en el mundo Microsoft C #, los programadores se preocupan poco por lo interno de sus Diccionarios y Listas (en su mayor parte, pocos proyectos exigen ajustes de rendimiento a este nivel). Funcionan de manera muy eficiente y tienden a hacer que muchas funciones de las aplicaciones funcionen bien.

Aplicaciones del mundo real

Utilizo los tipos List y Dictionary con bastante frecuencia. Para los cuadros de lista, a menudo los asocio a diccionarios. Al organizar los datos que muestro en las páginas web, normalmente creo una Lista o Diccionario para impulsar la construcción de la página. En una aplicación web reciente, creé un Diccionario de Listas que usé para construir una matriz de valores en una página. Estos valores eran editables y, en una devolución de datos, pude obtener los datos editados, en función de los valores clave que incrusté tanto en HTML como en JavaScript (bueno, JSON, en realidad …).

La conclusión aquí es que las Listas y los Diccionarios organizan los datos y se usan de la misma manera que las tablas en las bases de datos: contienen datos modificables a los que se debe acceder.

Las tablas hash son una clase importante en el kit de herramientas de cada programador.

Casi en cualquier momento que desee asignar claves a valores con tiempo constante para buscar / agregar / eliminar. Si se encuentra recorriendo una lista para encontrar un elemento, piense si hay una manera de almacenar los elementos con claves en una tabla hash (también conocido como mapa hash, también conocido como diccionario) (o además).

Por ejemplo, en lugar de:

Contactos de clase {
Lista contactos = nueva ArrayList ();

void addContact (Persona p) {
contactos.add (p);
}

// A tiempo
Person getContact (String phoneNumber) {
para (Persona p: contactos) {
if (p.getPhoneNumber (). equals (phoneNumber)) devuelve p;
}
volver nulo;
}

…
}

getContact () podría hacerse más rápido si almacenó un mapa hash en paralelo:

Contactos de clase {
Lista contactos = nueva ArrayList ();
Map phoneNumberToPerson = new HashMap ();

void addContact (Persona p) {
contactos.add (p); // asumiendo que esta lista todavía se necesita en otro lugar
phoneNumberToPerson.put (p.getPhoneNumber (), p);
}

// O (1) tiempo!
Person getContact (String phoneNumber) {
return phoneNumberToPerson.get (phoneNumber);
}

…
}

Las tablas hash tienen un propósito tan general que incluso puede usarlas para, de hecho, “agregar” nuevos campos a objetos a cuya clase no tiene acceso o no desea modificar, creando una tabla hash que se mapee desde un objeto para valorarlo y almacenarlo en algún lugar fuera de la clase. Cuando desee buscar o modificar el valor de ese “campo”, simplemente busque ese objeto en esa tabla hash.

Por ejemplo:

import some.external.library.Character;

arena de clase {
List gladiators = new ArrayList ();
Mapa gladiatorsWeapons = new HashMap ();

equipo nulo (Personaje c, Arma w) {
gladiatorsWeapons.put (c, w);
}

getWeapon booleano (Carácter c) {
return gladiatorsWeapons.get (c);
}

…
}

Es como si hubieras agregado un campo Arma a la clase Personaje, solo accesible desde la clase Arena.

Incluso sin tener en cuenta la limitación causada por el Carácter que proviene de una biblioteca externa, este diseño puede ser deseable ya que quizás no todos los Personajes deberían poder manejar armas, solo gladiadores, por ejemplo, o más, solo gladiadores en Arenas. Una alternativa es subclasificar el personaje (si la clase de personaje es extensible), llámelo Gladiador y dele un campo de Arma. Pero es una buena regla general evitar crear jerarquías de clases si no es necesario. Entonces, a menos que los Gladiadores vayan a sacar sus Armas de la Arena, tal vez este diseño sea el más limpio.

Un último ejemplo es el lenguaje de programación Python. Almacena sus campos internamente como un diccionario que asigna del nombre del campo al valor.

Por ejemplo:

clase MyClass:
x = 2

imprimir MyClass.x # salidas “2”
imprima MyClass .__ dict __ [“x”] # salidas “2”

(En Python, los corchetes se usan para buscar una clave en un diccionario).

Si escribe código en Python, entonces casi todo son tablas hash:

• Los diccionarios y conjuntos son tablas hash que hacen que la búsqueda, la inserción y la eliminación sean muy rápidas.
• Python mantiene una lista de los módulos que se importan, es decir, un diccionario, por lo tanto, una tabla hash.
• Dentro de cada módulo, los atributos, clases y funciones de nivel de módulo se mantienen como diccionarios, de ahí una tabla hash
• Dentro de cada clase, el conjunto de atributos y métodos dentro de esa clase se mantienen como diccionarios, es decir, una tabla hash

Muchos lenguajes de programación dinámicos los usan como objetos livianos; de esta manera, puede agregar y eliminar propiedades a voluntad, mientras conserva un tiempo de acceso constante (porque las búsquedas de tablas hash toman tiempo constante).

Tablas de transposición para programas de juego.

Si puede crear una buena función hash para su estado de juego, las tablas de transposición le permiten ahorrar mucho esfuerzo en la búsqueda de estados que se han visto antes.

Esta publicación en mi blog podría ser útil para el hash en general:

Sistemas distribuidos Parte 1: ¡Un vistazo al hashing constante! por Pawan Bhadauria sobre Amor por la programación