Re: van Emde Boas hash.

[A. Soare]

> > What algorithm uses emacs for hashing the obarrays of symbols ?
> 
> Read the source: C-h f intern RET then click on top right to get to the
> source code, ...
> 
> It's a hash table with simple haqshing into buckets that contain linked
> lists of symbols.

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.

Hashing using van Emde Boas requires in the worst case a time of log_2(N), 
where N is the length of the largest symbol name in obarray.




Alin.



____________________________________________________

Derniers jours pour remporter le séjour au Maroc sur http://www.lesrevoila.fr/