apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Francois PESCE <f.pe...@wanadoo.fr>
Subject Use of expand_array in apr_hash.c
Date Mon, 24 May 2004 20:49:15 GMT
I read the hash table implementation of libapr and I'm not sure of the
efficiency of the collision problem resolution.

I'm not convinced that the expand situation is the best... it only
occurs when the number of elements in the hash table is greater than the
number of buckets, if I understand correctly. The point is that it
implies a well-done distribution, ie: 
if the hash function distribution is really bad for a special case (say
the worst) we can theoretically have a bucket with ht->max element in
it, reducing dramatically the performance of the hash structure.
A better implementation would be to expand the hash table when the
bucket we are filling got a number of elements greater than a fixed size

This implementation can be done by keeping the "list" point of view, or
by using arrays (as we know that a bucket won't contain more than N
element, because if so, we expand the table).

An other solution (or feature :> ) will be to provide a _create function
in the API that will take as argument a hash function, for people who
already know the nature of the keys that will be hashed.

What do you think of it ?


Francois PESCE

<noob quote>
PS: I hope you did'nt receive this message 2 times, I just subscribe
this list and it seems the first time it was not sent.
</noob quote>


View raw message