Dictionaries don't have to use associations (for example MethodDictionary doesn't use them), that's why #pointsTo: works (MethodDictionary also uses it).
But that means a linear scan of the whole collection, even if done primitively, this is not scalable.
Not necessarily. VisualAge had a LookupTable class that was identical to Dictionary except it used two parallel Array's (keys / values) rather than Association objects instaniated by its Dictionary. LookupTable was faster..