Humm... well, you must have some other useful information associated with a flow, that you read/write during processing of each packet anyway. No?
If no, then what's the point of maintaining timestamp just to clean up them later?..
Or perhaps, you do have some other useful information, but it's only read during processing most of the time. And timestamps need to be written, and that causes problems?
Please, provide more detailed info (sizes of objects, workload characteristics, etc).
concurrent_hash_map is currently not documented as safe for concurrent insertion and traversal, though as Anton says, there may be a way to do it.
The new concurrent_unordered_map in the latest open source release is specifically designed to allow concurrent insertion and traversal (but not concurrent erasure). It's inteface is very similar to the C++0x unordered_map.