[fpc-devel] Generic Programming Units
dezobec at tin.it
Tue Jun 21 21:57:28 CEST 2005
Michael Van Canneyt 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))
>But I assume that calculating the hash becomes harder for 'better' hashes ?
Not always, it depends on the type of the input, different hash
functions have to be used for different key types, a hash function good
for numerical keys will be different from the hash function used for the
string keys. My idea is to add to the hash table a method for
"statistical" data about the table: number of collisions, i.e. length of
the chains and the number of void buckets in the hash array, to be able
to choose the right hash function and the right dimension for the hash
array in the specific case.
Of course speed comes always at an expense: memory usage, the trick is
to find a good compromise.
More information about the fpc-devel