Re: glib hash memory footprint

[Sander Vesik <sander_traveling yahoo co uk>]

 --- "Alan M. Evans" <ame1 extratech com> wrote: 
> 
> Also, linear probing has a hideous worst-case. The nominal-case
> collision can be mitigated somewhat by using instead quadratic probing
> or double hashing to avoid clustering, but the worst-case remains very
> bad.

The worst case for chaining is actually worse than for linear probing in 
practice considering that you are doing pointer chasing instead of array 
access with linear probing. 

> 
> If table size is really a problem (and I agree that it can be, as for
> example, in your case), wouldn't switching from linked lists to dynamic
> arrays be a better solution in the general case?
> 

yes, that would be nice but also a non-trivial problem and can give you 
memory fragmentation quite easily

> -- 
> Alan M. Evans <ame1 extratech com>
> 


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


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