[fpc-devel] Generic Programming Units
micha at neli.hopto.org
Tue Jun 21 21:50:43 CEST 2005
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).
More information about the fpc-devel