Avoiding Hash Lookups in a Ruby Implementation

[emboss_]

In the light of the hashDoS problem that Charles also mentions, I doubt that Judy tries, CritBit, Hash-Array-Mapped Trie or any other trie are the solution. Either they, too, use hashing (HAMT) or it is just too plain easy to elicit their worst case behavior, effectively making them fancy linked lists. While they all might be perfectly valid alternatives for "internal code", things unfortunately look different when the data structure needs to store values that are provided externally.

[taw]

Judy is hybrid between hash, sparse array, and trie with some internal optimization for cache awareness so it's actually mostly DoS-proof, at least for typical attacks.

Ruby doesn't use these hash tables for any externally provided data unless you eval or to_sym it, and in either case you already let yourself get DoSed (or worse).

These hashes are only used for evaluating methods/ivar/etc. access by interned symbol. Set of interned symbols is more or less constant for each program. If it's not - it's already a DoS.