Hash tables

Hash tables

[Nick Roberts]

I am trying to using alists to store information (to display watched expressions
under gdb with the speedbar). I have expressions like:

(dolist (var gdb-var-list)
     (let ((var-list))
       some operation on var...
     (push var var-list))
(setq gdb-var-list (nreverse var-list)))

where var is a list like (varnum a b c d)

Update of the speedbar for arrays and structures is too slow, so I thought
hash tables might speed things up. I want to replace the above with something
like:

(maphash gdb-var-operation gdb-var-table)

The manual says that gdb-var-operation, should accept two arguments KEY and
VALUE.

but I want to pass some arguments to gdb-var-operation. I plan to change
maphash to:

(maphash FUNCTION TABLE &optional ARGS)

so that FUNCTION gets called with KEY, VALUE and ARGS.

This won't be an easy task for me so I'd like some reassurance that its
a) desirable and b) do-able.


Nick

Re: Hash tables

[Miles Bader]

On Thu, Sep 11, 2003 at 11:12:38PM +0100, Nick Roberts wrote:
> but I want to pass some arguments to gdb-var-operation. I plan to change
> maphash to:
> 
> (maphash FUNCTION TABLE &optional ARGS)
> 
> so that FUNCTION gets called with KEY, VALUE and ARGS.
> 
> This won't be an easy task for me so I'd like some reassurance that its
> a) desirable and b) do-able.

The traditional way of doing this sort of thing in lisp is to bind variables
around the call to maphash, which your function can read (or write), e.g.:

   (let ((extra-info ...)
	 (total sum 0))
     (maphash
      (lambda (key val) 
	(setq total (+ total (calculate-stuff key val extra-info))))
      some-hash-table))

-Miles
-- 
We have met the enemy, and he is us.  -- Pogo

Re: Hash tables

[Stefan Monnier]

> but I want to pass some arguments to gdb-var-operation. I plan to change
> maphash to:
> (maphash FUNCTION TABLE &optional ARGS)
> so that FUNCTION gets called with KEY, VALUE and ARGS.

That is not necessary.  You can just use

  (maphash `(lambda (key value) (fun key value ',arg)) table)

instead.  And in most cases the above can even be simplified to

  (maphash (lambda (key value) (fun key value arg)) table)


        Stefan

hash tables

[David Roderick]

7.3 Defining Hash Comparisons
=============================

You can define new methods of key lookup by means of
`define-hash-table-test'.  In order to use this feature, you need to
understand how hash tables work, and what a "hash code" means.

   You can think of a hash table conceptually as a large array of many
slots, each capable of holding one association.  To look up a key,
`gethash' first computes an integer, the hash code, from the key.  It
reduces this integer modulo the length of the array, to produce an
index in the array.  Then it looks in that slot, and if necessary in
other nearby slots, to see if it has found the key being sought.

   Thus, to define a new method of key lookup, you need to specify both
a function to compute the hash code from a key, and a function to
compare two keys directly.


" It
reduces this integer modulo the length of the array,"

So does this mean that the integer must be times greater than the length
of the array, otherwise the integer is returned?

What happens if the hash table increases in size and this happens?
-- 
from 
David Roderick

Re: hash tables

[Barry Margolin]

In article <uiqz8w7db.fsf@tiscali.co.uk>,
 David Roderick <angel_ov_north@tiscali.co.uk> wrote:

> 7.3 Defining Hash Comparisons
> =============================
> 
> You can define new methods of key lookup by means of
> `define-hash-table-test'.  In order to use this feature, you need to
> understand how hash tables work, and what a "hash code" means.
> 
>    You can think of a hash table conceptually as a large array of many
> slots, each capable of holding one association.  To look up a key,
> `gethash' first computes an integer, the hash code, from the key.  It
> reduces this integer modulo the length of the array, to produce an
> index in the array.  Then it looks in that slot, and if necessary in
> other nearby slots, to see if it has found the key being sought.
> 
>    Thus, to define a new method of key lookup, you need to specify both
> a function to compute the hash code from a key, and a function to
> compare two keys directly.
> 
> 
> " It
> reduces this integer modulo the length of the array,"
> 
> So does this mean that the integer must be times greater than the length
> of the array, otherwise the integer is returned?

Yes.  Hash codes should generally be very large integers.

> What happens if the hash table increases in size and this happens?

When a hash table changes size, all the elements have to be rehashed and 
moved to the new locations.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE don't copy me on replies, I'll read them in the group ***