Re: Better Hash Tables?

[Jenda]

Fullness can be described in terms of an overall percentage — this table is 50% full, that one’s 90% — but researchers often deal with much fuller tables. So instead, they may use a whole number, denoted by x, to specify how close the hash table is to 100% full. If x is 100, then the table is 99% full. If x is 1,000, the table is 99.9% full. This measure of fullness offers a convenient way to evaluate how long it should take to perform actions like queries or insertions.

Seems once again researchers are researching exactly the wrong thing. I mean if the table is 99% full, you should have increased its size a long long time ago. If it's even more full, you are an ... you are clearly not interested in doing anything practical, but rather seem to be working towards a degree in theoretical something or other.

While it's possible that there's something of some practical use in that paper (so far I only read the article), I would not hold my breath. If the topic was an already pathologically overstuffed hashes, then there might be something for the sanely proportioned ones too, but...

[jo37]

Seems once again researchers are researching exactly the wrong thing.

You haven't read the linked paper, have you?

[Jenda]

If you read my comment, you can see me stating openly that I only react to the article, not to the paper. :-)

I'm not through the paper yet and I admit I would prefer if they stated the algorithm (also) using (pseudo)code rather than (just) by a mix of english and maths, but so far I really do not think we will see this in perl any time soon. The algorithm looks fairly complicated and while I have no reason to dispute the asymptotic behavior, I would expect the real world performance for hashes that are not excessively full to be rather bad and I do believe that for real world applications it will be better to allocate more memory for the table than to complicate the code.

[jo37]

I do believe that for real world applications it will be better to allocate more memory for the table than to complicate the code.

You are missing the point. In a hash table that is filled to a certain degree, there is some effort required to add a new element (or search for an existing one). Seems there was consensus over some decades that a specific algorithm was optimal (but which had not been proved), that was disproved in the paper.

A non-optimal algorithm - even on an enlarged table - is slower than the optimal one. Just because there is a measure that can easily express a 99.999% filled table does not mean you should use it. The "asymptotic behavior" is asymptotic with the table's size for any given "fillness".

Would you state there is no point in making an engine more efficient just because you can enlarge the fuel tank?