4 ms·
I think I'm missing something conceptually as to why perfect hashing is even needed in this case. Since postgres only has only about 450 or so keywords, shouldn
by krackers 8y ago
I think I'm missing something conceptually as to why perfect hashing is even needed in this case. Since postgres only has only about 450 or so keywords, shouldn't it suffice to just use a standard string hashing algorithm like:
int Hash(string x)
{
unsigned int h = 31;
for(int i = 0; i < x.length(); i++)
{
h = (h * 76991) ^ (x[i] * 77003);
}
return h;
}
Which I tested and seems to work fine with no collisions for the ~440 tokens postgres has. It's definitely not as theoretically fulfilling as a constructive way to generate perfect hashes, but unless they plan to add hundreds of new keywords in the future shouldn't standard hash functions work (after tweaking the constants to ensure that no collisions occur for their particular set of words)?
- nroets 8y agoYour function returns 32 bit values, which is far from minimal. CHM92 can generate a minimal function i.e. the numbers are all between 0 and 441. Furthermore, if you have a function for each keyword, you can create a CHM92 function that returns the address of the correct function to be called. (NB: This approach assumes the input does not contain invalid keywords) Alternatively, you can order your keywords according to some kind of priority and number them from 0 to 439. So you generate a CHM92 function that generates those numbers. When you parse the input, you apply the hash function. You then look up the number in a table of keywords and do a strcmp() check that it's valid. Then you can compare the priority of it with any other keyword without any further lookups.
- asdfaoeu 8y agoBecause theirs both only returns a number between 0 and max_keywords - 1. Yours would require a 4gb lookup table.