[racket] how hash works

From: YC (yinso.chen at gmail.com)
Date: Mon Nov 8 18:56:02 EST 2010

Hi all -

I have a couple of questions on how hash works.  What I am trying to do is
that I am using a struct as the hash key.  The struct has the following

(define-struct foo (name)) ;; there are other fields but simplified for this

The name field holds a symbol.  Because my actual struct holds quite a bit
of complex structure that my code does not hold elsewhere, instead of trying
to keep another hash that holds the mapping between the name and the struct,
I want to make the name and the struct equivalent from hash's perspective,
so I can pass in the symbol to the hash and it will be mapped to the right
struct that maps to the corresponding value.

After much experimentation, I achieve the above goal with the following:

1 - leverage prop:equal+hash property.  This defines an equal?,
equal-hash-code, and equal-secondary-hash-code for the struct.  My
definition of foo is updated as follows:

(define-struct foo (name)
  #:property prop:equal+hash
  (let ()
    (define (equal/foo? $s1 $s2 recur)
      (equal? (foo-name $s1) (foo-name $s2)))
    (define (equal-hash-code/foo $s recur)
      (- (equal-hash-code (foo-name $s)) *35*))
    (define (equal-secondary-hash-code/foo $s recur)
      (equal-secondary-hash-code $s))
    (list equal/foo? equal-hash-code/foo equal-secondary-hash-code/foo)))

What's interesting is that I need to adjust the value from equal-hash-code
by 35 in order to get (equal-hash-code 'test) and (equal-hash-code (make-foo
'test)) to be the same.  For equal-secondary-hash-code such adjustment is
not required.  So the first question - why do equal-hash-code require such
adjustment (and why 35)?

Now - I thought that hash-ref simply compares the hash-code of the key, but
that alone does not appear to be enough, as hash-ref seem to also dictate
having the same types for the key, so I have to add one extra struct (called
href below) to wrap around the keys:

(define-struct href (inner)
  #:property prop:equal+hash
  (let ()
    (define (equal/href? $s1 $s2 recur)
      (equal? (equal-hash-code $s1) (equal-hash-code $s2)))
    (define (equal-hash-code/href $s recur)
      (equal-hash-code (href-inner $s)))
    (define (equal-secondary-hash-code/href $s recur)
      (equal-secondary-hash-code (href-inner $s)))
    (list equal/href? equal-hash-code/href equal-secondary-hash-code)))

I did not need to adjust the equal-hash-code for this object (not sure why
here either).  And now I can finally do the following:

(hash-ref (make-immutable-hash (list (cons (make-href (make-foo 'test))
          (make-href 'test) 'we-do-not-have-the-value)
;; => 'we-have-the-value

So it seems that hash-ref by default also checks the type of the key besides
checking their hash-code - unless they have the same type, the keys will not
match even with the same hash-code.  Is that correct?

Any thoughts are appreciated.  Thanks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101108/517af6eb/attachment.html>

Posted on the users mailing list.