2 ms·
> lookups becoming O(n) on average. If you're using a central dictionary then it should be worst case O(log n), but the price you pay for that is attacker con
by akira2501 2y ago
> lookups becoming O(n) on average.
If you're using a central dictionary then it should be worst case O(log n), but the price you pay for that is attacker controlled allocated memory growth.
- knome 2y agothere are various ways to structure dictionaries. one was to essentially create an array with each entry pointing into a list of values. you hash the key, then add the key/value to the list in that slot. the hash attacks would ensure everything hashed to the same slot, forcing the dict to become effectively become an alist. it would do similar to implementations that keep jumping X slots mod size looking for an open slot, using the hash as the start slot. since everything hashed to the same value, everything you stuck in the dict would have to walk over every slot that had been stuck in the dict, again effectively making the dict into an overly complex association list for all practical reasons.