I have been trying to understand how Mathematica is able to compute the values it does. The core evaluation process is very well documented and can be found online, but they completely lack the internal structure that deals with pattern matching.

For what I've found, some internal functions are used to (1) compare different patterns and arrange the argument matching order in the same function pattern (e.g. F[x_ + 1, x] would first match the second argument (x) and only then try match the first (x_ + 1)), and (2) which rule should be matched first, when multiple rules can be used. These functions are always changing with each version, but it does not matter to the question.

My computer science intuition would tell me to create some sort of prefix tree for the patterns and always try to match from there, though this would instantly go against the (2). Snooping around the documentation, I have found over the "Some Notes on Internal Implementation" that:

Any transformation rule—whether given as x->y or in a definition—is automatically compiled into a form that allows for rapid pattern matching. Many different types of patterns are distinguished and are handled by special code.

A form of hashing that takes account of blanks and other features of patterns is used in pattern matching.

...

When a large number of definitions is given for a particular symbol, a hash table is automatically built using a version of Dispatch so that appropriate rules can quickly be found.

My guess is that they find common patterns in the rules and it does contribute for a special kind of hash they might be using, but this is just speculation. Does anyone knows to what form the patterns are compiled? What the Dispatch is actually doing, or how a hash table is used for pattern matching?