Re: glib hash memory footprint

Around 15 o'clock on Aug 31, "Alan M. Evans" wrote:

> For a bonus, if the array is kept sorted, then chained lookups can be
> binary searches.

For this complexity, you should throw away the hash table and just use a 
O(log n) data structure from the start (skip list, binary tree, etc).

> I don't know about it being non-trivial. The array solution seems pretty
> trivial to me. You may be right about fragmentation, but I'm not certain
> that it's an insurmountable problem.

An array solution eliminates the performance advantages of hash tables on 
insert or delete; you have to shuffle elements around, making them O(n) 
worst case, and > O(log n) best case.

> I suppose that this is just my personal bias, but I don't think that
> closed hashing is a good general purpose solution, given the requirement
> to allocate a table larger than your data.

Depends on what you want to do; open addressing with non-linear re-probing 
yields good average case performance with minimal overhead -- consider a 
binary tree has significant overhead in pointers and colors, and arrays do 
not offer O(log n) insert/delete.  What it doesn't offer is O(log n) worst 
case performance, but using better reprobing reduces the odds of 
worst-case performance dramatically.

I use open addressing with resizable hash tables in approximately power of
two sizes using prime pairs (where P and P-2 are both prime) for hash and
rehash respectively.  Using prime pairs ensures that any input value will
eventually hit every hash table bucket (for our worst-case O(n) 

Resizing at power-of-two intervals yields an amortized constant overhead, 
so the overall performance of the hash table is O(log n) in the average 
case.  Worst case (O(n)) performance occurs with a vanishingly small 
amount of the time (I think it's something like 1/p**n), assuming the 
table is kept fairly empty (like 50% utilization).  At 50% occupancy, the 
overhead for this hash table is essentially identical to a binary tree.

(couldn't help myself, I always like a good data structures and algorithms 


Attachment: pgp5iqqCzxUq9.pgp
Description: PGP signature

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