Hashing the src/dst addr/port pairs, finding a candidate bucket, and
then reverting to a linked list (simple one level fixed bucket size
hashing) is very easy to do. Routing code used to do this until CIDR
made tree algorithms nessecary due to prefix overlap relationships.
And yes. BSDI already solved this although they did it to boost
performance when many legitimate PCBs were allocated on heavily loaded
HTTP servers. By luck (I think), it happens to also solve the SYN
attack problem (or at least require an attack of 1/3 T1 of SYN traffic).
The fancier algorithms you are talking about avoid the storage costs
of the PCB. They might be marginally faster due to having to allocate
and fill in less data structure. IMO its not worth it.