Jonathan Morton <[email protected]> writes: >>> "polylog(n)-wise Independent Hash Function". OK, my google-foo fails >>> me: The authors use sha1, would something lighter weight suit? > >> The current favorite in DPDK land seems to be Cuckoo hashing. >> It has better cache behavior than typical chaining. > > That paper describes an improved variant of cuckoo hashing, using a > queue to help resolve collisions with better time complexity. The > proof relies on (among other things) a particular grade of hash > function being used. SHA1 is described as being suitable since it > offers cryptographic-level performance… We actually need two hashes > with independent behaviour on the same input, one for each table. > > If we were to assume table sizes up to 64K, using both halves of a > good 32-bit hash might be suitable. It may be that plain old Jenkins > hash would work in that context. Supplement that with a 64-entry > queue with linear search (in software) or constant-time CAM search (in > hardware).
I was aiming for 2million routes. I gave up trying to wade through it and pinged the authors. fiddling with blake at the moment > > - Jonathan Morton > > _______________________________________________ > Codel mailing list > [email protected] > https://lists.bufferbloat.net/listinfo/codel _______________________________________________ Codel mailing list [email protected] https://lists.bufferbloat.net/listinfo/codel
