# What is the principle behind Dispatch?

I want to know what Dispatch actually does to rule the list. Why is it so fast?

The documentation says

Dispatch generates a dispatch table which uses hash codes to specify which sets of rules need actually be scanned for a particular input expression.

What is a hash table? How does it specify which sets of rules need actually be scanned for a particular input expression?

What about DeleteCases? Since it is fast too, Does it use hash table too?

-
I think this question is likely off-topic as it is about a common data structure. See hash table – Mr.Wizard Nov 22 '13 at 11:42
@Mr.Wizard You are right, but I think this question could attract good answers about Mma internals. Let's see. – Dr. belisarius Nov 22 '13 at 12:11
@Mr.Wizard Yeah, I admit it is a little off-topic. And I was wondering if DeleteCases also use hash table? Because it is fast too. – matheorem Nov 22 '13 at 13:14
@rm-rf For the case where the r.h.s. of DeleteCases is an alternative pattern (Alternatives[elems]), and when elems do not contain patterns, since V8 DeleteCases has been optimized to work really fast, even for the large number of elems. I strongly suspect that a hash table was used internally in this case. And this may well be what the OP means here, since I do recall some comments by the OP related to this particular issue. – Leonid Shifrin Nov 22 '13 at 15:18
As @LeonidShifrin (and the original poster and maybe others) surmise, that special case of DeleteCases uses a hash table. Cases likewise. – Daniel Lichtblau Nov 22 '13 at 19:17