parrot-dev Digest, Vol 24, Issue 11

[Paul C. Anagnostopoulos]

At 8/10/2010 08:00 AM, parrot-dev-request at lists.parrot.org wrote:

>Date: Tue, 10 Aug 2010 01:01:42 +0300
>From: luben karavelov <luben at unixsol.org>
>
>When we look for the bucket to put/get a key we use something like this:
>
>bucket_index = (hash_fn(key)) & hash->mask
>
>Alternative approach that supports arbitrary values for M will be:
>
>bicket_index = (hash_fn(key)) % M
>
>The claim why it is like that (masking and power of 2 buckets) is that 
>this makes hash table expanding cheaper.  A am not so sure that this is 
>true because I have not solid understanding of the current expand/resize 
>algorithm.

I'm not sure why it would help with expansion, but it does help with the bucket index calculation, since it avoids a division. I don't know if that's worth worrying about. If we did go to an arbitrary-size bucket vector, we could easily detect whether the size is a power of two (at expansion time) and then AND the hash value; otherwise we would do a modulus.

~~ Paul


----------------------------------------------------------------
Windfall               Paul C. Anagnostopoulos 
      ----------------------------------------------------------
   Software             978 371-2316 
                             www.windfall.com
----------------------------------------------------------------
Metaphorical invocations ... often suffer from the
weakness of giving such satisfaction to the human
mind that they tend to be mistaken for incisive and
illuminating observations. ---Torkel Franzen 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.parrot.org/pipermail/parrot-dev/attachments/20100810/942aa71b/attachment.html>