Re: hash table freeze is useless



On Fri, Nov 05, 1999 at 12:24:19PM -0500, Havoc Pennington 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).

perhaps if a hash table is frozen then insert should not do a lookup, it
would do a lookup only when it's thawed (it would loop over the list of
queued inserts)

George



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