1. A method, in a firewall device, for performing an operation on a received data packet, the method comprising: receiving a data packet at a network interface of the firewall device, wherein the data packet has a plurality of header field values and wherein each header field value has a different header field value type and each header field value type is associated with a different hash table within a plurality of hash tables; performing, by the firewall device, a plurality of hash operations on the plurality of header field values to generate a plurality of hash values; performing, by the firewall device, a plurality of lookup operations in the plurality of hash tables based on the plurality of hash values to identify a plurality of hash table entries; retrieving, from a rule set storage of the firewall device, a bit string associated with each of the plurality of hash table entries, wherein each bit in the bit string corresponds to a class of rules of a rule set of a firewall and specifies a list of fallback sets of rules thereby generating a plurality of lists of fallback sets of rules; identifying an intersection of the plurality of lists of fallback sets of rules; searching, by the firewall device, search trees of fallback sets of rules present in the intersection; and performing, by the firewall device, an operation on the data packet based on one or more rules resulting from searching the search trees of fallback sets of rules present in the intersection.