6.6 Hash Tables

Bigloo offers hash tables with support for weak pointers. Here are described functions which define and use them.

bigloo procedure: make-hashtable [bucket-len] [max-bucket-len] [eqtest] [hash] [weak-keys] [weak-data]

bigloo procedure: create-hashtable [:size] [:max-bucket-len] [:eqtest] [:hash] [:weak] [:max-length] [:bucket-expansion]

Defines an hash table for which the number of buckets is size. The variable max-bucket-len specify when the table should be resized. If provided, these two values have to be exact integers greater or equal to 1. Normally you could ignore size and max-bucket-len arguments and call make-hashtable with no argument at all. The argument eqtest enables the specification of a comparison function. The first argument of this function is the keys contained in the table. The second argument is the searched key. By default hash tables rely on hashtable-equal?, which is defined as:

(define (hashtable-equal? obj1 obj2)
   (or (eq? obj1 obj2)
       (and (string? obj1)
            (string? obj2)
            (string=? obj1 obj2))))

The argument hash specifies an hashing function. It defaults to get-hashnumber. The arguments weak-keys, weak-data, and weak-both specify respectively whether the hash table should use weak pointers to store the keys and/or the data. By default a hash table uses strong pointers for both keys and data. Each optional arguments size, max-bucket-len, eqtest, hash, weak-keys, and weak-data can be bound to the Bigloo value #unspecified which forces its default.

The argument max-length specifies a maximum length (in number of buckets) for this hashtable. It defaults to 16384. If during the execution, the hashtable tries to expand itself more than max-length, an exception is raised. This feature helps debugging incorrect hashtable uses because excessive expansion is generally the signs of an incorrect behavior. Excessive expansions, cause the garbage collector to crash at some point. This debugging feature can be disabled by specifying a negative max length, in which case, no check is performed at runtime.

The argument bucket-expansion controls how max-bucket-len is expanded each time the table grows. This is a floating point number that is a multiplicative coefficient. It defaults to 1.2.

The function create-hashtable is equivalent to make-hashtable but it uses a keyword interface. The keyword argument weak can either be none, data, or keys.

bigloo procedure: hashtable? obj

Returns #t if obj is an hash table, constructed by make-hashtable.

bigloo procedure: hashtable-weak-keys? table

Returns #t if table is a hash table with weakly pointed keys.

bigloo procedure: hashtable-weak-data? table

Returns #t if table is a hash table with weakly pointed data.

bigloo procedure: hashtable-size table

Returns the number of entries contained in table. Note that for a weak hash table the size does not guarantee the real size, since keys and/or data can dissapear before the next call to the hash table.

bigloo procedure: hashtable-contains? table key

Returns the boolean #t if it exists at least one entry whose key is key in table. If not entry is found #f is returned. Note that for a weak hash table, the fact this procedure returns #t does not guarantee that the key (or its associated data) will not dissapear before the next call to the hash table.

bigloo procedure: hashtable-get table key

Returns the entry whose key is key in table. If no entry is found, or if the key and/or value is weakly pointed to and has dissapeard, #f is returned.

bigloo procedure: hashtable-put! table key obj

Puts obj in table under the key key. This function returns the object bound in the table. If there was an object obj-old already in the table with the same key as obj, this function returns obj-old; otherwise it returns obj.

bigloo procedure: hashtable-remove! table key

Removes the object associated to key from table, returning #t if such object was bound in table and #f otherwise.

bigloo procedure: hashtable-add! table key update-fun obj init-value

If key is already in table, the new value is calculated by (update-fun obj current-value). Otherwise the table is extended by an entry linking key and (update-fun obj init-value).

deprecated bigloo procedure: hashtable-update! table key update-fun init-value

If key is already in table, the new value is calculated by (update-fun current-value). Otherwise the table is extended by an entry linking key and init-value.

bigloo procedure: hashtable->vector table

bigloo procedure: hashtable->list table

Returns the hash table table’s data as a vector (respectively a list). If the hash table is weak, the result will consist only of the data which haven’t dissapeared yet and whose keys haven’t dissapeared either.

bigloo procedure: hashtable-key-list table

Returns the list of keys used in the table. If the hash table is weak, the result will consist only of the keys which haven’t dissapeared yet and whose data haven’t dissapeared either.

bigloo procedure: hashtable-map table fun

Returns a list whose elements are the result of applying fun to each of the keys and elements of table (no order is specified). In consequence, fun must be a procedure of two arguments. The first one is a key and the second one, an associated object. If the hash table is weak, fun will only be mapped on sets of key/datum which haven’t dissapeared yet.

bigloo procedure: hashtable-for-each table fun

Applies fun to each of the keys and elements of table (no order is specified). In consequence, fun must be a procedure of two arguments. The first one is a key and the second one, an associated object. If the hash table is weak, fun will only be called on sets of key/datum which haven’t dissapeared yet.

bigloo procedure: hashtable-filter! table fun

Filter out elements from table according to predicate fun. If the hash table is weak, fun will only be called on sets of key/datum which haven’t dissapeared yet.

Here is an example of hash table.

(define *table* (make-hashtable))

(hashtable-put! *table* "toto" "tutu")
(hashtable-put! *table* "tata" "titi")
(hashtable-put! *table* "titi" 5)
(hashtable-put! *table* "tutu" 'tutu)
(hashtable-put! *table* 'foo 'foo)

(print (hashtable-get *table* "toto"))
   -| "tutu"
(print (hashtable-get *table* 'foo))
   -| 'foo
(print (hashtable-get *table* 'bar))
   -| #f

(hashtable-for-each *table* (lambda (key obj) (print (cons key obj))))
   -| ("toto" . "tutu")
      ("tata" . "titi")
      ("titi" . 5)
      ("tutu" . TUTU)
      (foo . foo)

bigloo generic: object-hashnumber object

This generic function computes a hash number of the instance object.

Example:

(define-method (object-hashnumber pt::point)
   (with-access::point pt (x y)
      (+fx (*fx x 10) y)))

bigloo procedure: string-hash string [start 0] [len (string-length string)]

Compute a hash value for string, starting at index start, ending at length len.

This document was generated on March 31, 2014 using texi2html 5.0.