En informática , particularmente en programación funcional , el hash consing es una técnica utilizada para compartir valores que son estructuralmente iguales. Cuando se construye un valor, como una celda cons , la técnica verifica si dicho valor se ha construido antes y, de ser así, reutiliza el valor anterior, evitando una nueva asignación de memoria . Una propiedad útil del hash consing es que se puede probar la igualdad de dos estructuras en tiempo constante a través de la igualdad de punteros, lo que a su vez puede mejorar la eficiencia de los algoritmos de divide y vencerás cuando los conjuntos de datos contienen bloques superpuestos. [1] Se ha demostrado que el hash consing brinda mejoras dramáticas en el rendimiento, tanto en espacio como en tiempo, para algoritmos de programación simbólica y dinámica . [ cita requerida ]
La conversión de hash se implementa más comúnmente con tablas hash que almacenan referencias débiles que pueden recolectarse como basura cuando los datos almacenados en ellas no contienen referencias externas a la tabla. [2] [3]
Simple, no muy eficiente, pero adecuado para demostrar la implementación del concepto de un memorizador por medio de una tabla hash y referencias débiles en Scheme :
;; hashes débiles ;; ( requiere 'tabla hash ') ( define ( crea-tabla-débil . args ) ( aplica crea-tabla-hash args )) ( define ( conjunto-de-tabla-débil! clave- de-tabla datos ) ( let (( w ( referencia-de-tabla-hash clave - de-tabla #f ))) ( if w ( conjunto-de-vectores! w 0 datos ) ( let (( w ( crear-vector-débil 1 ))) ( conjunto-de-vectores! w 0 datos ) ( conjunto-de-tabla-hash! clave- de-tabla w ))))) ( define ( clave de tabla de referencia de tabla débil ) ( deja (( w ( clave de tabla de referencia de tabla hash #f ))) ( si w ( referencia de vector w 0 ) #f ))) ;; fábrica de memorizadores: para un procedimiento dado (sin efectos secundarios), ;; devuelve un procedimiento que hace lo mismo memorizando algunos de los resultados ;; en el sentido de ¿igual? en toda la lista de argumentos ;; ( define ( make-weak-memoizer proc ) ( let (( cache ( make-weak-table equal? ))) ( lambda args ( let (( x ( weak-table-ref cache args ))) ( if ( bwp-object? x ) ( let (( r ( apply proc args ))) ( weak-table-set! cache args r ) r ) x ))))) AP Ershov presentó una técnica de compilación de hash consing en 1958. [4] [5] El término "hash consing" se origina a partir de implementaciones en el contexto de Lisp en la década de 1970. [6] [7]