Re: glib hash memory footprint

[Sander Vesik <sander_traveling yahoo co uk>]

 --- James Henstridge <james jamesh id au> wrote: 
> On 01/09/04 06:08, Alan M. Evans wrote:
> 
> >For a bonus, if the
> >array is kept sorted, then chained lookups can be binary searches. (Even
> >with the linked list, it is possible to reduce the cost of lookups if
> >the list is kept sorted.) This type of optimization is not possible with
> >linear probing.
> >  
> >
> The GHashTable API requires the user to provide a hash function and an 
> equality function.  How would you sort the items in the chain using 
> these operators?  Adding an extra API to specify a comparison function 
> doesn't sound like a good idea, since glib would need to keep the code 
> for programs that don't set a comparison function, and every existing 
> program using GHashTable would need to be modified to take advantage of 
> the optimisation.
> 

If you end up sorting chains, then you probably have too many conflicts 
and should rather consider using a different hashing function. It might 
be that glib should offer an easy way to profile what is hapenning with 
the hash and how efficently its being used (and possibly a way to force 
growth) but I really don't see benefits from adding sorting and complicated 
lookups to the hash. Rehashes also become more expensive this way.

> James.
> 
> -- 
> Email: james jamesh id au
> WWW:   http://www.jamesh.id.au/
> 


=====
Open Source - the religion of doing it right


	
	
		
___________________________________________________________ALL-NEW Yahoo! Messenger - all new features - even more fun!  http://uk.messenger.yahoo.com