Re: hash table freeze is useless

[Kaz Kylheku <kaz ashi footprints net>]

On Fri, 5 Nov 1999, David Benson wrote:
> 
> > I was just noticing that g_hash_table_insert() performs a hash lookup.  
> > This means that if you freeze the hash table, then insert a lot of items,
> > the performance of g_hash_table_insert() will be degenerating into O(n)
> > over time, so your insert-items loop will have O(n^2) performance. Without
> > the freeze, it is basically O(n) (with the hash resizes amortized, and
> > each insertion constant time).
> > 
> > A better solution than freeze/thaw might be a way to set the expected
> > number of items, g_hash_table_resize_for(hash, n_items) which would resize
> > the table in advance to accomodate that number of additional items, saving 
> > n_items re-insertions and perhaps reducing the total number of resizes.
> 
> I believe the intent is so you can freeze a hashtable that is 
> large, delete half the items, insert a bunch of new items
> without resizing the table extraneously.

In Kazlib I have a different approach: there is a special delete function
which does not resize the table. The documented intent is not for performance,
but rather to allow the current item to be deleted during table traversal
without destroying the validity of the iterator.

Also, hash_insert doesn't perform any lookup: the constraint prohibiting
duplicate keys must be validated by the application.  If the app can ensure by
means other than a lookup that keys are unique, it shouldn't have to pay for
a redundant lookup buried in the insertion.