hashconsing

Hashconsing is a technique for representing data structures so that identical substructures are stored only once and referenced from all their occurrences. It maintains a global hash-cons table that maps a structural key to a unique, canonical object. When a new node is constructed, the system computes a key from the node’s type and contents, looks up the table, and if an equal structure already exists, returns a reference to that object; otherwise it allocates a new object, inserts it into the table, and returns it.

Mechanically, hashconsing relies on interning: every time a structure is built, its interned form is sought in the table, and the canonical object is reused. This guarantees that structurally equal values share the same memory representation, enabling fast pointer-based equality checks and enabling maximum substructure sharing.

Benefits include reduced memory usage when many identical substructures occur, and the possibility of fast equality tests since structural equality reduces to pointer equality. It also can simplify certain optimizations in compilers, theorem provers, and symbolic computation systems by exposing a canonical representation of terms.

However, hashconsing typically requires immutability or disciplined mutability, because changes to a shared object would affect all references. Implementations must manage the intern table to avoid unbounded growth and may use weak references or garbage collection strategies to reclaim unused terms. The technique introduces overhead for interning during construction, and is most effective when a large amount of structural sharing occurs.

Common use cases include abstract syntax trees in compilers, symbolic expressions, and formal reasoning systems, where many subexpressions recur and fast, equality-based lookup is advantageous.