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. _______________________________________________ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel