On Tue, 21 Jun 2005 21:42:19 +0200 (CEST) [EMAIL PROTECTED] (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 _______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
