> Because there's an assumption that the O(1) of a hashtable always beats the O(N) of a linear search. Except that that's really not always the case anymore on a modern arch, with things properly vectorized, etc.
It was never universally true. I remember reading about compiler design in the 1970s; I think it was somewhere in Wirth where he pointed out that, for local symbolic lookups, it was more efficient to use a simple loop over an array because the average number of symbols was so low that the constant management overhead from any more advanced data structure was more expensive than a linear scan.
It was never universally true. I remember reading about compiler design in the 1970s; I think it was somewhere in Wirth where he pointed out that, for local symbolic lookups, it was more efficient to use a simple loop over an array because the average number of symbols was so low that the constant management overhead from any more advanced data structure was more expensive than a linear scan.