It's a serial chain for each rule type (-I/-O/-F). Firewall code
serially scans the relevant chain until it finds an entry that matches
or drops off the end and uses the policy setting. The masquerade port
lookup is hashed but the rules are not.
IMHO there is no chance of firewall rules being hashed. The design of
the filter requires that the rules be scanned top to bottom. However
there is hope, "Paul Rusty Russell" <Paul.Russell@rustcorp.com.au> has
written patches (http://www.adelaide.net.au/~rustcorp) to represent the
rules as a tree with user defined structure. Makes rule scanning
faster and it is easier to test new firewall configurations.