The flow cache of a network flow processor (NFP) stores flow lookup information in cache lines. Some cache lines are stored in external bulk memory and others are cached in cache memory on the NFP. A cache line includes several lock/hash entry slots. Each slot can store a CAM entry hash value, associated exclusive lock status, and associated shared lock status. The head of a linked list of keys associated with the first slot is implicitly pointed to. For the other lock/entry slots, the cache line stores a head pointer that explicitly points to the head. Due to this architecture, multiple threads can simultaneously process packets of the same flow, obtain lookup information, and update statistics in a fast and memory-efficient manner. Flow entries can be added and deleted while the flow cache is handling packets without the recording of erroneous statistics and timestamp information.