Combined cache-overflow memory structure

A method of storing cache and overflow values, the method comprising:

• receiving a network packet over a network connection;
• generating a hash key using a hash function on at least a portion of the network packet;
• using the hash key to check whether a connection state associated with the network packet is in a combined cache-and-overflow memory;
• based on at least the hash key, determining whether an overflow condition exists for storing the connection state in a main memory, wherein an overflow condition exists when a hash collision occurs;
• if no overflow condition exists, storing the connection state in a combined cache-and-overflow memory as a cache entry, wherein the combined cache-and-overflow memory includes intermingled cache entries and overflow entries;
• if an overflow condition exists, determining whether the combined cache-and-overflow memory is full;
• if the overflow condition exists, for storing the connection state in the main memory, and the combined cache-and-overflow memory is not full, storing the connection state in the combined cache-and-overflow memory as an overflow entry;
• if the overflow condition exists and the combined cache-and-overflow memory is full, evicting a cache entry and storing the connection state in the combined cache-and-overflow memory as an overflow entry in a location where the cache entry was evicted so as to give priority to overflow entries over cache entries in the combined cache-and-overflow memory;
• and
• for a future network packet received over the network connection, generating the hash key using at least a portion of the future network packet and using the hash key to retrieve the connection state from the combined cache-and-overflow memory.