A flow assignment module identifies different network flows' characteristics and the characteristics of the signatures for the different network flows. Based on the identified characteristics, the flow assignment module assigns a network flow to a hash table among a small set of hash tables for storing signatures for that network flow. The flow assignment module assigns the network flow in such a way to minimize the likelihood that a signature for the network flow is hashed to a table entry that frequently occurs in a different network flow assigned to the same hash table. The flow assignment module identifies a hash table for the network flow where there is the least overlap between a signature for that network flow and a frequent byte in another network flow.