computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

, particularly in

functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...

, hash consing is a technique used to share values that are structurally equal. The term ''hash consing'' originates from implementations of Lisp that attempt to reuse

cons In computer programming, ( or ) is a fundamental function in most dialects of the Lisp programming language. ''constructs'' memory objects which hold two values or pointers to two values. These objects are referred to as (cons) cells, conses, ...

cells that have been constructed before, avoiding the penalty of

memory allocation Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when ...

. Hash consing is most commonly implemented with

hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...

s storing

weak reference In computer programming, a weak reference is a reference that does not protect the referenced object from collection by a garbage collector, unlike a strong reference. An object referenced ''only'' by weak references – meaning "every chain of ref ...

s that may be garbage-collected when the data stored therein contains no

reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a '' name'' ...

s from outside the table. Hash consing has been shown to give dramatic performance improvements—both space and time—for symbolic and

dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...

algorithms. An interesting property of hash consing is that two structures can be tested for equality in constant time, which in turn can improve efficiency of divide and conquer algorithms when data sets contain overlapping blocks.

Example

Simple, not very efficient, but suitable for demonstration of the concept implementation of a memoizer by means of hash table and weak references in Scheme: ;; weak hashes ;; (require 'hash-table) (define (make-weak-table . args) (apply make-hash-table args)) (define (weak-table-set! table key data) (let ((w (hash-table-ref table key #f))) (if w (vector-set! w 0 data) (let ((w (make-weak-vector 1))) (vector-set! w 0 data) (hash-table-set! table key w))))) (define (weak-table-ref table key) (let ((w (hash-table-ref table key #f))) (if w (vector-ref w 0) #f))) ;; memoizer factory: for given (side-effect-free) procedure, ;; return a procedure which does the same memoizing some of results ;; in the sense of equal? on the whole list of args ;; (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)))))

Example

See also

References

Further reading