LISP - Tabla hash

La estructura de datos de la tabla hash representa una colección de key-and-valuepares que se organizan en función del código hash de la clave. Utiliza la clave para acceder a los elementos de la colección.

Se utiliza una tabla hash cuando necesita acceder a elementos mediante una clave y puede identificar un valor clave útil. Cada elemento de la tabla hash tiene un par clave / valor. La clave se utiliza para acceder a los elementos de la colección.

Crear tabla hash en LISP

En Common LISP, la tabla hash es una colección de uso general. Puede utilizar objetos arbitrarios como clave o índices.

Cuando almacena un valor en una tabla hash, crea un par clave-valor y lo almacena bajo esa clave. Más tarde, puede recuperar el valor de la tabla hash utilizando la misma clave. Cada clave se asigna a un valor único, aunque puede almacenar un nuevo valor en una clave.

Las tablas hash, en LISP, se pueden clasificar en tres tipos, según la forma en que se pueden comparar las claves: eq, eql o igual. Si la tabla hash tiene un hash en los objetos LISP, las claves se comparan con eq o eql. Si el hash de la tabla hash en la estructura del árbol, entonces se compararía usando igual.

los make-hash-tableLa función se utiliza para crear una tabla hash. La sintaxis de esta función es:

make-hash-table &key :test :size :rehash-size :rehash-threshold

Donde -

los key argumento proporciona la clave.
los :testEl argumento determina cómo se comparan las claves: debe tener uno de los tres valores # 'eq, #' eql o # 'igual, o uno de los tres símbolos eq, eql o igual. Si no se especifica, se asume eql.
los :sizeEl argumento establece el tamaño inicial de la tabla hash. Debe ser un número entero mayor que cero.
los :rehash-sizeEl argumento especifica cuánto aumentar el tamaño de la tabla hash cuando se llena. Puede ser un número entero mayor que cero, que es el número de entradas a agregar, o puede ser un número de punto flotante mayor que 1, que es la relación entre el tamaño nuevo y el tamaño anterior. El valor predeterminado de este argumento depende de la implementación.
los :rehash-thresholdEl argumento especifica qué tan llena puede estar la tabla hash antes de que deba crecer. Puede ser un número entero mayor que cero y menor que: rehash-size (en cuyo caso se escalará cada vez que la tabla crezca), o puede ser un número de punto flotante entre cero y 1. El valor predeterminado para esto El argumento depende de la implementación.

También puede llamar a la función make-hash-table sin argumentos.

Recuperar elementos de y agregar elementos a la tabla hash

los gethashLa función recupera un elemento de la tabla hash buscando su clave. Si no encuentra la clave, devuelve nil.

Tiene la siguiente sintaxis:

gethash key hash-table &optional default

donde -

clave: es la clave asociada
tabla hash: es la tabla hash que se buscará
predeterminado: es el valor que se devolverá, si no se encuentra la entrada, que es nulo, si no se especifica.

los gethash La función en realidad devuelve dos valores, el segundo es un valor de predicado que es verdadero si se encontró una entrada y falso si no se encontró ninguna entrada.

Para agregar un elemento a la tabla hash, puede usar el setf función junto con el gethash función.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList))

Cuando ejecuta el código, devuelve el siguiente resultado:

(CHARLIE BROWN)
(FREDDIE SEAL)

Eliminar una entrada

los remhashLa función elimina cualquier entrada para una clave específica en la tabla hash. Este es un predicado que es verdadero si hubo una entrada o falso si no la hubo.

La sintaxis de esta función es:

remhash key hash-table

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList)) 
(terpri)
(write (gethash '003 empList))  
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))

Cuando ejecuta el código, devuelve el siguiente resultado:

(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NIL

La función maphash

los maphash función le permite aplicar una función específica en cada par clave-valor en una tabla hash.

Toma dos argumentos: la función y una tabla hash, e invoca la función una vez para cada par clave / valor en la tabla hash.

Ejemplo

Cree un nuevo archivo de código fuente llamado main.lisp y escriba el siguiente código en él.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

Cuando ejecuta el código, devuelve el siguiente resultado:

3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)