alt Hacker NewsThis code is very simple but I still don't really get it. Why is the hashing needed and how is it faster than a regex? Can someone smarter than me explain?
Replies
> Why is the hashing needed and how is it faster than a regex? Can someone smarter than me explain?
It's a perfect hash (i.e. no collisions) that hash to an entry in a 32-element array.
Very similar to how we usually do quick lookups of strings for `switch()` statements: https://github.com/lelanthran/libxtree/blob/878cb4fc11ffd617...
You need a hashtable to check whether this character is part of a given set. And the perfect hashing-based implementation is the most efficient form of a hashtable since you only need a lookup and an equality check. I included a small visualisation in the article that illustrates how it works, so if you try clicking on the elements, it will show you how the calculations are made.
No branching (if statements), no heavy CPU operations, just a multiplication by a constant, a shift and a lookup in a small table that will get cached fast