[fpc-devel] Generic Programming Units

[Micha Nelissen]

On Tue, 21 Jun 2005 21:42:19 +0200 (CEST)
marcov at stack.nl (Marco van de Voort) wrote:

> > Depends how the hash is parametrized. If you've a big hash array and a
> > good hash function accessing has a complexity of O(1)
> > while for a binary
> > search it's O(log(n))
> 
> This is no fair comparison, since you compare an unsafe way (hash) with a 
> safe one (bintree). 
> 
> So this only if you have a number of buckets close to the number of elements
> and a perfect hash. Otherwise you need log(n1/nbuckets) extra comparisons.
> (assuming you do conflict resolving using bintree)

There is also dynamic hashing, where the number of buckets grow/shrink dynamically with addnig items. Then it stays O(1), but the constant involved may be so large that it's practically slower than binary tree, until using a lot of items, a million say (for example).

Micha