httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Stein <gst...@lyra.org>
Subject Re: [PATCH] simple hash table implementation
Date Wed, 26 Apr 2000 11:19:13 GMT
On Wed, 26 Apr 2000, Tony Finch wrote:
> rbb@covalent.net wrote:
> >Do we want these functions to return an ap_status_t to match the rest of
> >APR?  I don't have a real opinion yet, but I would like to hear other
> >peoples.
> 
> It's designed to fit in with the pools and tables stuff, hence the
> lack of status return codes. The opportunity for failure isn't very
> broad either.

Yah, I saw nothing beyond memory allocation failure. BUT: you should at
least have a way to signal that.

The code seems fine although I'd want to have get/set forms where I can
pass my own hash value. That allows me to optimize the hashing algorithm
for the domain of my key values.


I'm not up on my hash table theory, but it seems that your closed hash
table will have more collisions than an open table. True?

For example, let's say that you have a table of 100 slots and you want to
fill it with 100 items. Let's say those items have a 75% chance of
conflict when applying the size-modulus to their raw hash value. This
means you have 75 unique hash values, and 25 collisions.
(the 101th insertion grows the table)

With an open scheme, the 100 items would be going into a table of 200
slots (assuming 50% fill). The 75% chance of conflict applied against the
200 implies the use of 150 slots (for the 100 items), which means an
expected value of zero collisions.


Since conflicts in a hash table move you away from O(1) towards O(N), a
hash table design should attempt to reduce conflicts if at all possible.

I'd recommend an open hashing table instead :-)

Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/



Mime
View raw message