Re: glib hash memory footprint

 --- "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!

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]