Hash consing

Inom datavetenskap , särskilt inom funktionell programmering , är hash consing en teknik som används för att dela värden som är strukturellt lika. Termen hash consing härstammar från implementeringar av Lisp som försöker återanvända cons- celler som har konstruerats tidigare, och undviker straffet med minnesallokering . Hash consing implementeras oftast med hashtabeller som lagrar svaga referenser som kan samlas in som skräp när data som lagras däri inte innehåller några referenser utanför tabellen. Hash consing har visat sig ge dramatiska prestandaförbättringar – både utrymme och tid – för symboliska och dynamiska programmeringsalgoritmer . En intressant egenskap hos hash consing är att två strukturer kan testas för likhet i konstant tid, vilket i sin tur kan förbättra effektiviteten av divide and conquer- algoritmer när datamängder innehåller överlappande block.

Exempel

Enkel, inte särskilt effektiv, men lämplig för demonstration av konceptimplementeringen av en memoizer med hjälp av hashtabell och svaga referenser i Schema :

 

  
   

   
      
    
         0 
        
         0 
           

  
      
    
         0
      





 
    
    
         
         
              
                 
              
           ;; svaga hash   ;;  (  kräver  'hash-table  )  (  definiera  (  make  -weak-table  .  args  )  (  tillämpa  make  -hash-table  args  ))  (  definiera  (  weak-table-set!  tabellnyckeldata  )  (  låt  ((  w  (  hash-table) -ref  tabellnyckel  #f  )))  (  if  w  (  vektoruppsättning!  w  data  )  (  låt  ((  w  (  gör-svag-vektor  1  )))  (  vektoruppsättning!  w  data  )  (  hash  -tabelluppsättning!  tabellnyckel  w  )))))  (  definiera  (  svag-tabell-ref-  tabellnyckel  )  (  låt  (  (  w  ( hash-   tabell  -ref-  tabellnyckel  #f  )  ))  (  om  w  (  vektorref  w  )  #f  )) )  ;; memoizer factory: för given (biverkningsfri) procedur,   ;; returnera en procedur som gör samma sak genom att memorera några av resultaten   ;; i betydelsen lika?  på hela listan över argument   ;;  (  definiera  (  make-weak-memoizer  proc  )  (  låt  ((  cache  (  make-weak-table  lika?  )))  (  lambda  args  (  låt  ((  x  (  svag-tabell-ref  cache  args  )))  (  if  (  bwp- objekt?  x  )  (  låt  ((  r  (  tillämpa  proc  args  )))  (  svag-tabell-uppsättning!  cache  args  r  )  r  )  x  ))))) 

Se även

• String interning
• Flugviktsmönster
• Merkle träd
• Hashlife
• Praktikant

Vidare läsning

•   Ershov, AP (1958). "Om programmering av aritmetiska operationer" . Kommunikation från ACM . 1 (8): 3–6. doi : 10.1145/368892.368907 . S2CID 15986378 .
• Jean Goubault. Implementera funktionella språk med snabb likhet, uppsättningar och kartor: en övning i Hash Consing. I Journées Francophones des Langages Applicatifs (JFLA'93), sidorna 222–238, Annecy, februari 1993.