Re: van Emde Boas hash.

[Stefan Monnier]

> As far as I understand, the algorthm is so:

> oblookup ( obarray, sym )

>  ;; hash is an integer, the index of a bucket that may contain sym
>  hash = hash_string (sym)
>  ;; bucket is a vector. obarray is a vector of many buckets
>  bucket = obarray [hash]
>  ;; search sym in its bucket using a naive search
>  FOR every symbol S in bucket, check whether S has the same name
>  as sym. If so, return S. If no symbol matches, returns the hash.


> Even if it is very unlikely that we can find many symbols into
> a bucket, the algorithm does not require constant time for
> every search.

Yes, it's a very simple hashing algorithm.  I'm sure we can come up with
something more efficient.  Then again, I haven't seen any indication
that this is a performance problem.


        Stefan