[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: van Emde Boas hash.
From: |
David Kastrup |
Subject: |
Re: van Emde Boas hash. |
Date: |
Mon, 23 Nov 2009 17:57:27 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux) |
Stefan Monnier <address@hidden> 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
- Re: van Emde Boas hash., (continued)