3 ms·

When targeting hard real time you want strong worst-case guarantees, not weak probabilistic arguments like "we hope the hashes are distributed well enough to ac

When targeting hard real time you want strong worst-case guarantees, not weak probabilistic arguments like "we hope the hashes are distributed well enough to achieve O(1) in practice". The malicious version of this is hash DoS, where an attacker chooses the values inserted into the hash table so they have the same hash (or at least same bucket). Randomized hashing using a secure hash mitigates this somewhat, but the attack is still possible to some degree, especially if the hash secret is long lived. Another issue is that inserting into hash tables is usually only amortized O(1), with the collection growing exponentially when it's full. So most insert operations are cheap, but occasionally you get an O(n) insertion. However it doesn't sound like this is what the article is talking about.

cb321 4y ago
While I agree with all you said, one can expand a bit on it. There are concrete max search depth expectations for well randomizing hash functions such as: https://www.sciencedirect.com/science/article/abs/pii/019667748790040X which is notably logarithmic - not unlike a B-Tree. When these expectations are exceeded you can at least detect a DoS attack. If you wait until such are seen, you can activate a "more random" mitigation on the fly at about the same cost as "the next resize/re-org/whatnot". All you need to do is instrument your search to track the depth. There is some example such strategy in Nim at https://github.com/c-blake/adix https://github.com/c-blake/adix for simple Robin-Hood Linear Probed tables and a formula based one from that above paper inside https://github.com/c-blake/suggest https://github.com/c-blake/suggest This is all more about the "attack" scenario than the "truly hard" real-time scenario, of course.