A hash cons a számítógép-programozásban, különösen a funkcionális programozásban egy módszer szerkezetileg egyenlő értékek megosztására. Az elnevezést a Lisp implementációk adták, amelyek cons cellákat használtak fel újra ahhoz, hogy adminisztrációs költségeket spóroljanak meg. Leggyakoribb megvalósítása gyenge referenciákat tároló hashtáblák, amiket a szemétszedő összegyűjthet, ha kívülről nincs rájuk referencia. Mind térben, mind időben sokat javít a szimbolikus és a dinamikus algoritmusokon. Érdekes tulajdonsága, hogy két szerkezet egyenlősége konstans időben eldönthető, ami feljavítja az oszd meg és uralkodj algoritmusok hatékonyságát, ha az adathalmazok átfedő blokkokat tartalmaznak.
Ez a minta rokon a könnyűsúlyúval. Stringekre alkalmazva ezt a technikát string bekebelezésnek nevezik.
Példa Az alábbi Scheme nyelvű példa egyszerű, de nem túlságosan hatékony megvalósítása egy emlékező struktúrának hash táblával és gyenge referenciákkal:
;; 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))))) Jegyzetek
Fordítás
További olvasmányok Merkle tree
Jean Goubault. Implementing Functional Languages with Fast Equality, Sets and Maps: an Exercise in Hash Consing. In Journées Francophones des Langages Applicatifs (JFLA’93), pages 222–238, Annecy, February 1993.
Kategória:Programtervezési minták