[fpc-devel] Generic Programming Units

[Florian Klaempfl]

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))