[fpc-devel] Generic Programming Units
Michael Van Canneyt
michael at freepascal.org
Tue Jun 21 21:40:59 CEST 2005
On Tue, 21 Jun 2005, Florian Klaempfl wrote:
> Michael Van Canneyt wrote:
> > On Tue, 21 Jun 2005, Florian Klaempfl wrote:
> >>Dean Zobec wrote:
> >>>As the project looks like a long term one and I think that fpc urgently
> >>>needs a optimized hash table I'll also work on a streamlined hash table
> >>>with a chaining technique as a collision resolution scheme and a paging
> >>>for the allocation of the nodes in the chains, to have an associative
> >>>container that would easily beat the TStringList in search speed when
> >>>the number of items added is more than 100.000 (the IndexOf() function
> >>>in an unordered TStringList does a linear search).
> >>A good hash class is even a candidate for the classes unit imo.
> > I would make that the contnrs unit. I think it belongs more together with
> > objects such as a stack and queue...
> > What is the performance difference between a hash() and a binary search on
> > an ordered list ? I've also been working with an 'associative' stringlist, but
> > I was using an ordered stringlist to keep the data, so a binary search is done.
> 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))
But I assume that calculating the hash becomes harder for 'better' hashes ?
More information about the fpc-devel