Tablas hash VS matrices asociativas

Question

Recientemente he leído sobre hash-tables en un libro muy famoso "Introduction to Algorithms". Todavía no los he usado en ninguna aplicación real, pero quiero hacerlo. Pero no sé cómo comenzar.
¿Alguien me puede dar 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 tengo conocimientos básicos (teóricos) sobre ellos.
Muchas gracias.

Answer 1

En PHP, 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 - es simplemente implementado 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 se puede hacer con una tabla hash.

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

Ejemplos de código:

Uso de 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 

bucle 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 

Observe especialmente la manera en el segundo ejemplo , se mantiene el orden de cada elemento (Tyler, Bill Marc) basado en el orden en que fueron ingresados ​​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

matrices de PHP son básicamente las tablas hash

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 cómo 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

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 ve en C.

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

Answer 5

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).