Re: van Emde Boas hash.

[David Kastrup <dak@gnu.org>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> 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.

I should think that it makes up a sizeable portion of byte-recompiling
and autoloading, both of which are not often benchmarked.  But it isn't
something which you commonly do on data sets in a loop.  Scanning files
is done just once usually.

-- 
David Kastrup