[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Efficiency and flexibility of hash-tables

From: Joris van der Hoeven
Subject: Re: Efficiency and flexibility of hash-tables
Date: Tue, 11 Feb 2003 12:14:33 +0100 (MET)

> > So does there exist an adaptive-number-of-slots solution in guile?
> No.  We'd be happy to include adaptation in the standard Guile
> hash-tables, though.  Would it be possible for you to contribute a
> patch?

I don't have much knowledge about how to write low-level guile functions.
In the meantime, you might want to use the following code.
I only use the equal?-based access methods, but it would be easy
to add the eq?- and eqv?-based methods.

The 'adaptive hash tables' are stored as a pair with a usual hashtable and
its number of entries. I have tested the code a bit and it seems to work.
If you find any bugs, then please let me know.

Best wishes, Joris

Joris van der Hoeven <address@hidden> GNU TeXmacs scientific text editor personal homepage

;; MODULE      : ahash-table.scm (part of GNU TeXmacs)
;; DESCRIPTION : adaptive hash tables
;; COPYRIGHT   : (C) 2003  Joris van der Hoeven
;; This software falls under the GNU general public license and comes WITHOUT
;; If you don't have this file, write to the Free Software Foundation, Inc.,
;; 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

;; Adaptive hash tables

(define (make-ahash-table)
  (cons (make-hash-table 1) 0))

(define (ahash-ref h key)
  (hash-ref (car h) key))

(define (ahash-size h)
  (cdr h))

(define (ahash-slots! h new-size)
  (let ((new-h (make-hash-table new-size)))
    (hash-fold (lambda (key value dummy) (hash-set! new-h key value))
               #f (car h))
    (set-car! h new-h)))

(define (ahash-set! h key value)
  (if (hash-ref (car h) key)
      (hash-set! (car h) key value)
        (if (>= (cdr h) (vector-length (car h)))
            (ahash-slots! h (+ (* 2 (vector-length (car h))) 1)))
        (set-cdr! h (+ (cdr h) 1))
        (hash-set! (car h) key value))))

(define (ahash-remove! h key)
  (let ((removed (hash-remove! (car h) key)))
    (if removed
          (set-cdr! h (- (cdr h) 1))
          (if (< (+ (* 4 (cdr h)) 1) (vector-length (car h)))
              (ahash-slots! h (quotient (vector-length (car h)) 2)))))

(define (ahash-fold h)
  (hash-fold (car h)))

reply via email to

[Prev in Thread] Current Thread [Next in Thread]