3 ms·
The point I'm making is that a specially optimized hashing function would probably blow away any trie traversal. When you know the data being hashed before hand
by mightyham 2y ago
The point I'm making is that a specially optimized hashing function would probably blow away any trie traversal. When you know the data being hashed before hand it is possible to make custom hash functions that are as simple as a few bitwise operations on the first, middle and last character of the string (just an example).
- dividuum 2y agoRight. Out of curiosity I looked into what code gperf generates and it seems it would end up O(1) for misses (it's always three lookups into a generated table) and O(L) for hits, as a potential hit has to be confirmed by essentially a strcmp. Not sure how something like https://github.com/rust-phf/rust-phf https://github.com/rust-phf/rust-phf would work, but probably similar?
- treis 2y agoIsn't the sticky wicket collisions with external to CF defined headers?
- Denvercoder9 2y agoThey don't know all the data that's being hashed, though. They know everything that's in the map, but not all the keys they're trying to lookup.
- dathinab 2y agoif all your internal headers start with cf- and most non-internal headers don't (but not all) and most headers are non-internal a trie might be hard to beat