php - resolucion - tablas hash en java

Tablas Hash VS matrices asociativas

Question

Recientemente, he leído sobre hash-tables en un libro muy famoso " Introducción a los algoritmos ". Todavía no los he usado en ninguna aplicación real, pero quiero hacerlo. Pero no sé cómo comenzar.
¿Alguien puede darme algunas muestras de su uso, por ejemplo, cómo realizar una aplicación de diccionario (como ABBYY Lingvo) usando hash-tables?
Y finalmente me gustaría saber cuál es la diferencia entre las tablas hash y las matrices asociativas en PHP, me refiero a qué tecnología debo usar y en qué situaciones?
Si estoy equivocado (perdón), corrígeme, porque en realidad estoy comenzando con hash-tables y solo tengo conocimientos básicos (teóricos) sobre ellos.
Muchas gracias.

Answer 1

En PHP, las matrices asociativas se implementan como tablas hash, con un poco de funcionalidad adicional.

Sin embargo, técnicamente hablando, una matriz asociativa no es idéntica a una tabla hash, simplemente se implementa en parte con una tabla hash detrás de las escenas. Debido a que la mayor parte de su implementación es una tabla hash, puede hacer todo lo que puede hacer una tabla hash, pero también puede hacer más.

Por ejemplo, puede recorrer una matriz asociativa utilizando un bucle for, que no puede hacer con una tabla hash.

Entonces, si bien son similares, una matriz asociativa puede hacer un superconjunto de lo que una tabla hash puede hacer, por lo que no son exactamente lo mismo. Piense en ello como hashtables más funcionalidad adicional.

Ejemplos de código:

Usar una matriz asociativa como una tabla hash :

$favoriteColor = array();
$favoriteColor[''bob'']=''blue'';
$favoriteColor[''Peter'']=''red'';
$favoriteColor[''Sally'']=''pink'';
echo ''bob likes: ''.$favoriteColor[''bob'']."/n";
echo ''Sally likes: ''.$favoriteColor[''Sally'']."/n";
//output: bob likes blue
//        Sally likes pink

Looping a través de una matriz asociativa :

$idTable=array();
$idTable[''Tyler'']=1;
$idTable[''Bill'']=20;
$idTable[''Marc'']=4;
//up until here, we''re using the array as a hashtable.

//now we loop through the array - you can''t do this with a hashtable:
foreach($idTable as $person=>$id)
    echo ''id: ''.$id.'' | person: ''.$person."/n";

//output: id: 1 | person: Tyler
//        id: 20 | person: Bill
//        id: 4 | person: Marc

Tenga en cuenta especialmente cómo en el segundo ejemplo, el orden de cada elemento se mantiene (Tyler, Bill Marc) en función del orden en que se ingresaron en la matriz. Esta es una gran diferencia entre las matrices asociativas y las tablas hash. Una tabla hash no mantiene conexión entre los elementos que contiene, mientras que una matriz asociativa PHP sí (incluso puede ordenar una matriz asociativa PHP).

Answer 2

La diferencia entre una matriz asociativa y una tabla hash es que una matriz asociativa es un tipo de datos, mientras que una tabla hash es una implementación de datos. Obviamente, el tipo de matriz asociativa es muy importante en muchos lenguajes de programación actuales: Perl, Python, PHP, etc. Una tabla hash es la principal forma de implementar una matriz asociativa, pero no del todo la única. Y las matrices asociativas son el uso principal de las tablas hash, pero no del todo el único uso. Entonces no es que sean iguales, pero si ya tienes matrices asociativas, entonces no deberías preocuparte por la diferencia.

Por motivos de rendimiento, puede ser importante saber que las matrices asociativas en su idioma favorito se implementan como hash. Y puede ser importante tener una idea del costo general de esa implementación. Las tablas hash son más lentas y usan más memoria que las matrices lineales como las ves en C.

Perl agrupa los dos conceptos llamando a los conjuntos asociativos "hashes". Al igual que una serie de características de Perl, no está del todo mal, pero es descuidado.

Answer 3

Una matriz asociativa es una matriz en la que no se accede a los elementos por un índice, sino por una clave. Cómo funciona esto internamente es específico de la implementación (no hay ninguna regla sobre cómo debe funcionar). Una matriz asociativa podría implementarse mediante una tabla hash (la mayoría de las implementaciones lo harán), pero también podría implementarse mediante algún tipo de estructura jerárquica o una lista de omisiones o el algoritmo simplemente itera sobre todos los elementos en la matriz y busca una clave eso coincide (esto sería terriblemente lento, pero funciona).

Una tabla hash es una forma de almacenar datos donde los valores están asociados a las claves y donde tiene la intención de encontrar valores para las claves dentro de un tiempo (generalmente casi) constante. Esto suena exactamente como lo que espera de una matriz asociativa, es por eso que la mayoría de las veces las tablas hash se utilizan para implementar esas matrices, pero eso no es obligatorio.

Answer 4

Una matriz en PHP es en realidad un mapa ordenado, no hashtable. La principal diferencia entre el mapa y la tabla hash consiste en la incapacidad de recordar el orden en el que se han agregado los elementos. Por otro lado, las tablas hash son mucho más rápidas que los mapas. La complejidad de obtener un elemento del mapa es O (nlogn) y de hashtable es O (1).

Answer 5

arreglos php SON básicamente tablas hash