[fpc-devel] Generic Programming Units

[Michael Van Canneyt]

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 ?

Michael.